Das Problem mit verbrannten Pfannkuchen

23

Diese Herausforderung steht im Zusammenhang mit Flipping Pancakes .

Möglicherweise haben Sie von der Pfannkuchensortierung gehört , bei der ein Stapel Pfannkuchen nach Größe sortiert wird, indem Sie einen Spatel in den Stapel einsetzen und alle Pfannkuchen über dem Spatel umdrehen, bis die Pfannkuchen auf dem Teller nach der Größe sortiert werden. Das Problem der verbrannten Pfannkuchen ist etwas anders. Alle Pfannkuchen haben jetzt eine Seite, die verbrannt ist, und die verbrannte Seite jedes Pfannkuchens muss zum Teller zeigen, sobald die Sortierung abgeschlossen ist.

Zum Beispiel mit dem folgenden Stapel (Größe des Pfannkuchens auf der linken 0Seite bedeutet verbrannte Seite nach unten und 1verbrannte Seite nach oben auf der rechten Seite):

1 0
3 1
2 1

Sie können den ganzen Stapel umdrehen, um zu erhalten 20 30 11, die oberen beiden umdrehen, um zu erhalten, 31 21 11und den ganzen Stapel erneut umdrehen, um 10 20 30einen sortierten Stapel gebrannter Pfannkuchen zu erhalten. Diese Folge von Zügen, Flip 3, Flip 2, Flip 3, könnte dargestellt werden als 3 2 3.

Die Herausforderung

  • Wenn eine Reihe von Pfannkuchengrößen (nicht unbedingt eindeutig) und ihre Ausrichtungen vorgegeben sind, geben Sie eine gültige Sortierfolge für gebrannte Pfannkuchen aus, d.
  • Die Ein- und Ausgabe kann in jedem vernünftigen Format mit Trennzeichen erfolgen. Geben Sie jedoch an, welche Formate Sie verwenden, und geben Sie an, welches Ende Ihres Eingabeformats das oberste Ende des Stapels (TOS) ist.
  • Das Umdrehen von null Pfannkuchen ist erlaubt.
  • Das Mischen von Trennzeichen in der Eingabe / Ausgabe ist zulässig.

Testfälle

In allen folgenden Testfällen ist die Eingabe eine Liste und die Ausgabe eine durch Leerzeichen getrennte Zeichenfolge. Die TOS befindet sich links.

[[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"

Wie immer, wenn etwas unklar oder falsch ist, lassen Sie es mich bitte in den Kommentaren wissen. Viel Glück und gutes Golfen!

Sherlock9
quelle

Antworten:

7

Python 2, 83

Als Eingabe wird die Liste der Tupel (Größe, Ausrichtung) mit der Stapelspitze am Ende erwartet. Die Ausgabe ist eine Liste von Größen, die durch verschiedene Arten von Leerzeichen getrennt werden.

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
quelle
2
Anscheinend bin ich ein Idiot.
Undichte Nonne
Ist 0in der Ausgabeliste erlaubt?
Undichte Nonne
19
@LeakyNun Flipping 0 Pfannkuchen ist hervorragend möglich. Tatsächlich mache ich es gerade.
Feersum
@daniero Die Oberseite des Stapels befindet sich auf der rechten Seite.
Undichte Nonne
@LeakyNun oh sorry, mein schlechtes
daniero
3

CJam (37 Bytes)

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

Input ist ein Array im CJam-Format auf stdin. Die Ausgabe ist eine durch Zeilenumbrüche getrennte Liste der Flip-Längen für stdout. Die Spitze des Stapels befindet sich am Index 0. 0zeigt die verbrannte Seite nach oben und 1die verbrannte Seite nach unten an.

Online-Demo

Präparation

Die Ausgabe ist immer 3nlange Flips, wo nist die Anzahl der Pfannkuchen. Zuerst drehen wir den größten verbleibenden Pfannkuchen nach oben; dann, wenn es mit der verbrannten Seite nach unten ist, drehen wir diesen einen Pfannkuchen um; und dann drehen wir es auf den Boden und wiederholen, als ob der Stapel Pfannkuchen einer kürzer wäre.

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
quelle
3

Ruby, 101 95 93 Bytes

Nicht sehr golfen, ich wollte nur eine bogo-sortierte Variante machen. Es handelt sich um eine anonyme Funktion, die eine Reihe von Arrays aufnimmt und zufällige Spiegelbilder auf stdout druckt, bis die Pfannkuchen sortiert sind.

->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)}

Sie können es zum Beispiel zuweisen fund sagenf.call [[1, 0], [3, 1], [2, 1]]

-5 Bytes von @Jordan mit der brillanten Verwendung von rassoc
-2 Bytes von @ Sherlock9

daniero
quelle
1
Sie können durch das Ersetzen ein paar Bytes speichern a.all?{...}mit !a.rassoc(1).
Jordan
@Jordan Wow, das ist wirklich genial! Ich glaube nicht, dass ich jemals daran gedacht habe, ( r) zu benutzen assoc, aber darüber nachzudenken, ist wahrscheinlich bei vielen Problemen auf dieser Seite nützlich - ich denke, dass es in den Ruby-Golftipps veröffentlicht werden sollte. Wie auch immer, danke :) ich war auch ein weiteres Byte töten kann , obwohl die Anwendung von deMorgans Gesetz und ersetzt untilmit while.
Daniero
Da bgeht immer nur 0oder 1, 1-bwürde auch funktionieren und zwei Bytes einsparen.
Sherlock9