Le problème des crêpes brûlées

23

Ce défi est lié à Flipping Pancakes .

Vous avez peut-être entendu parler du tri des crêpes , où une pile de crêpes est triée par taille en insérant une spatule dans la pile et en retournant toutes les crêpes au-dessus de la spatule, jusqu'à ce que les crêpes soient triées du plus petit au plus grand dans l'assiette. Le problème des crêpes brûlées est légèrement différent. Toutes les crêpes ont désormais un côté qui est brûlé, et le côté brûlé de chaque crêpe doit faire face à la plaque une fois le tri terminé.

Par exemple, étant donné la pile suivante (taille de la crêpe à gauche. 0Signifiant côté brûlé vers le bas et 1signifiant côté brûlé vers le haut à droite):

1 0
3 1
2 1

Vous pouvez retourner la pile entière pour obtenir 20 30 11, retourner les deux premiers pour obtenir 31 21 11et retourner la pile entière pour obtenir 10 20 30, une pile triée de crêpes brûlées. Cette séquence de mouvements, flip 3, flip 2, flip 3, pourrait être représentée par 3 2 3.

Le défi

  • Étant donné un éventail de tailles de crêpes (pas nécessairement uniques) et de leurs orientations, sortez toute séquence de tri de crêpes brûlées valide, c'est-à-dire une séquence de retournements qui conduit à la pile de crêpes triée du plus petit au plus grand avec les côtés brûlés vers le bas.
  • L'entrée et la sortie peuvent être n'importe quel format sain avec des séparateurs, mais veuillez spécifier les formats que vous utilisez et indiquer quelle extrémité de votre format d'entrée est le haut de la pile (TOS).
  • Le retournement de zéro crêpes est autorisé.
  • Le mélange de séparateurs en entrée / sortie est autorisé.

Cas de test

Pour tous les cas de test suivants, l'entrée est une liste et la sortie est une chaîne séparée par des espaces, et TOS est à gauche.

[[1, 0], [3, 1], [2, 1]]
"3 2 3"

[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"

Comme toujours, si quelque chose n'est pas clair ou incorrect, faites-le moi savoir dans les commentaires. Bonne chance et bon golf!

Sherlock9
la source

Réponses:

7

Python 2, 83

L'entrée devrait être la liste des tuples (taille, orientation) avec le haut de la pile à la fin. Le résultat est une liste de tailles à retourner séparées par différents types d'espaces.

a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]
feersum
la source
2
Apparemment, je suis un idiot.
Leaky Nun
La 0liste de sortie est-elle autorisée?
Leaky Nun
19
@LeakyNun Flipping 0 pancakes est éminemment possible. En fait, je le fais en ce moment.
feersum
@daniero Le haut de la pile est sur le côté droit.
Leaky Nun
@LeakyNun oh désolé, ma mauvaise
daniero
3

CJam (37 octets)

q~{__$W>#)_p/(W%\M*2,f.^+(1=p_,)pW%}h

L'entrée est un tableau au format CJam sur stdin; la sortie est une liste de longueurs de bascule séparées par des sauts de ligne sur la sortie standard. Le haut de la pile est à l'index 0; 0indique le côté brûlé vers le haut et 1indique le côté brûlé vers le bas.

Démo en ligne

Dissection

La sortie est toujours 3nflips longue, où nest le nombre de crêpes. D'abord, nous renversons la plus grosse crêpe restante vers le haut; puis si elle est brûlée, nous renversons cette crêpe; puis nous le retournons vers le bas et répétons comme si la pile de crêpes était plus courte.

q~         e# Parse input into array
{          e# Loop...
  __$W>#)  e#   Find 1-based index of largest element in array
  _p       e#   Dup and print
  /(       e#   Split into chunks that long, and pull off the first
  W%       e#   Reverse the first chunk. Note that we don't flip the burnt/unburnt bit
  \M*      e#   Merge the remaining chunks into a single array
  2,f.^    e#   Flip *their* burnt/unburnt bits
  +        e#   Concatenate, prepending the first chunk
  (1=p     e#   Pull off the first (largest) element and print its burnt/unburnt bit
  _,)p     e#   Print the number of remaining elements plus 1 (to account for the largest)
  W%       e#   Reverse. Note that the first chunk has now been flipped twice, which is
           e#   why we have left its burnt/unburnt bit alone
}h         e# ... until we get down to an empty array
Peter Taylor
la source
3

Rubis, 101 95 93 octets

Pas très golfique, je voulais juste faire une variante de type bogo. Il s'agit d'une fonction anonyme qui prend un tableau de tableaux et imprime des retournements aléatoires sur la sortie standard jusqu'à ce que les crêpes soient triées.

->a{(p r=-~rand(a.size)
a[0,r]=a[0,r].reverse.map{|x,b|[x,1-b]})while a!=a.sort||a.rassoc(1)}

Vous pouvez par exemple l'assigner fet diref.call [[1, 0], [3, 1], [2, 1]]

-5 octets de @Jordan avec l'utilisation brillante de rassoc
-2 octets de @ Sherlock9

daniero
la source
1
Vous pouvez enregistrer quelques octets en remplaçant a.all?{...}par !a.rassoc(1).
Jordan
@ Jordan Wow, c'est vraiment génial! Je ne pense pas avoir déjà pensé à utiliser ( r) assocauparavant, mais en y réfléchissant, c'est probablement utile dans beaucoup de problèmes sur ce site - je pense que cela devrait aller dans le post de Ruby Golfing Tips. Quoi qu'il en soit, merci :) J'ai également pu tuer un autre octet grâce à l'application de la loi deMorgans et à son remplacement untilpar while.
daniero
Puisque bn'est que jamais 0ou 1, 1-bfonctionnerait également et économiserait deux octets.
Sherlock9