Le crépier

Le crépier psycho-rigide a une manie bien particulière. Lorsqu'il fait un lot de crêpes, chaque crêpe a une taille différente, et toujours exactement une face correctement cuite et une face brûlée. Il pose ses crêpes au fur et à mesure dans une assiette.

Dans un lot de n crêpes, il fait toujours : une crêpe de taille 1, une crêpe de taille 2, ... une crêpe de taille n-1 et une crêpe de taille n, mais il ne les fait pas forcément dans cet ordre.

Nous pouvons imaginer par exemple qu'après avoir fait 4 crêpes, son assiette contient cette pile, décrite à partir de la crêpe du dessus (Figure 1):

  1. crêpe de taile 3, brûlée dessus
  2. crêpe de taile 4, brûlée dessous
  3. crêpe de taile 2, brûlée dessous
  4. crêpe de taile 1, brûlée dessus

Une fois son lot de crêpes terminé, le travail n'est pas fini. Il faut impérativement ranger les crêpes par ordre de taille, la plus grande sur le dessous. Et il faut impérativement que la face brûlée ne soit pas visible (Figure 4).

Pour ranger ses crêpes, le crêpier ne s'autorise qu'une seule opération : prendre un tas de crêpes sur le dessus (autant qu'il veut, de 1 à toutes), et retourner ce tas. Par exemple, dans le cas decrit plus haut, il pourrait décider de retourner les 3 crêpes du dessus (Figure 2). Auquel cas, la configuration de la pile de crêpes serait alors (Figure 3) :

  1. crêpe de taile 2, brûlée dessus
  2. crêpe de taile 4, brûlée dessus
  3. crêpe de taile 3, brûlée dessous
  4. crêpe de taile 1, brûlée dessus

En faisant uniquement ce type d'opérations, plusieurs fois, il veut se retrouver dans cette configuration (Figure 4):

  1. crêpe de taile 1, brûlée dessous
  2. crêpe de taile 2, brûlée dessous
  3. crêpe de taile 3, brûlée dessous
  4. crêpe de taile 4, brûlée dessous

L'entrée du problème est la description du tas de crêpes, sous la forme d'une chaîne de caractères énumérant les crêpes à partir de celle du dessus. Chaque crêpe est décrite en donnant son diamètre (un nombre entier), puis la lettre I ou V, pour indiquer que la face brûlée est respectivement invisible ou visible. Le tas de crêpe initial serait alors décrit ainsi :

3V4I2I1V
Après avoir fait les retournements adéquats, la description de la pile devra être :
1I2I3I4I

Pour valider ce défi, vous devez indiquer au crêpier la liste des retournements de crêpes qu'il doit faire. Si vous pensez, par exemple (ce n'est pas la solution...) qu'il faut retourner les 3 crêpes du dessus, puis les 2 crêpes du dessus, puis les 4 crêpes, puis la crêpe du dessus, vous devez renvoyer la chaîne :

3241
Notez qu'avec ces retournements, la pile ne sera pas correcte, et on obtiendra :
1I3I2I4I

Enfin, la solution que vous proposez devra être la plus courte possible... et il n'y aura pas forcément 4 crêpes (mais il n'y en aura jamais plus de 9).

Vous voulez en savoir plus sur ce crêpier ? Voyez cette vidéo produite par l'Inria.
Pour ce type de défi, vous devez être connecté (accès à une URL donnant l'instance du problème à résoudre)

Tags : récursivité structure de données defiweb