Beschichtung jeden Pfannkuchen

35

Sie haben einen Stapel Pfannkuchen auf einem Teller mit einer Sirupkugel, die so dick ist, dass sie nicht über die Seiten rinnt. Sie werden nicht glücklich sein zu essen, bis beide Gesichter jedes Pfannkuchens mindestens den Sirup berührt haben, aber im Moment hat nur ein Gesicht des oberen Pfannkuchens.

Sie wissen, dass der Sirup nicht einmal einen Pfannkuchen durchtränkt, sondern unbegrenzt durch direkten Kontakt zwischen zwei Pfannkuchen übertragen werden kann. Sobald ein Gesicht eines Pfannkuchens Sirup berührt hat, wird es als für immer mit Sirup überzogen betrachtet, und es wird jedes nicht mit Sirup überzogene Gesicht erzeugt, das auch mit Sirup überzogen ist. Es ist auch möglich, Sirup von und zur Oberseite des Tellers zu befördern.

Sie beschichten jedes Pfannkuchengesicht mit Sirup, indem Sie einen Spatel unter einen oder mehrere Pfannkuchen legen und umdrehen, genau wie beim Sortieren von Pfannkuchen . (Leider ist dieser Spatel sirupbeständig und hilft nicht, den Sirup durch Berühren der Pfannkuchenflächen zu verteilen.) Leider verlieren Sie den Überblick darüber, welche Pfannkuchenflächen Sirup berührt haben, aber Sie erinnern sich an die von Ihnen gemachten Spiegelungen.

Können Sie in Anbetracht Ihrer vergangenen Flips feststellen, ob Ihre Pfannkuchen noch alle mit Sirup überzogen sind?

Herausforderung

Schreiben Sie ein Programm, das eine positive ganze Zahl N für die Anzahl der Pfannkuchen und eine Liste positiver ganzer Zahlen (alle <= N) für die von Ihnen bisher gemachten Flips enthält. Jede Zahl in der Liste steht für die Anzahl der Pfannkuchen, die umgedreht wurden. Geben Sie einen Wahrheitswert aus, wenn die Pfannkuchen überzogen sind, und einen falschen Wert, wenn nicht. ( wahrheitsgemäße / falsche Definition )

Die Eingabe sollte von stdin oder der Befehlszeile kommen und die Ausgabe sollte zu stdout (oder den nächsten Alternativen) gehen. Es ist in Ordnung , wenn Sie Ihre Eingabe ein wenig mehr benötigt Formatierung: zB [1, 1, 2, 2]statt 1 1 2 2für die Liste.

Beispiele

Angenommen, N = 2, so haben wir einen Stapel von zwei Pfannkuchen auf einem Teller, beginnend mit dem Sirup oben.

Wenn die Liste ist 1 1 2 2, bedeutet dies, dass wir ...

  • Drehen Sie den oberen Pfannkuchen um und beschichten Sie die Oberseite des unteren Pfannkuchens
  • Drehen Sie die Oberseite wieder um - beschichten Sie die ursprüngliche Unterseite des oberen Pfannkuchens
  • beide umdrehen - die Platte beschichten
  • Drehen Sie beide wieder um - beschichten Sie die ursprüngliche Unterseite des unteren Pfannkuchens

Da alle vier Flächen beschichtet sind, wäre die Ausgabe so ähnlich wie Trueoder 1.

Wenn die Liste ist 1 2 2 1, bedeutet dies, dass wir ...

  • Drehen Sie den oberen Pfannkuchen um und beschichten Sie die Oberseite des unteren Pfannkuchens
  • beides umdrehen - nichts beschichten
  • beide wieder umdrehen - nichts beschichten
  • Drehen Sie die Oberseite wieder um - beschichten Sie die ursprüngliche Unterseite des oberen Pfannkuchens

Da das die Platte berührende Gesicht noch sirupfrei ist, wäre die Ausgabe so ähnlich wie Falseoder 0.

Anmerkungen

  • Die Klappliste kann beliebig groß und leer sein. In diesem Fall ist die Ausgabe falsch.
  • Die Platte wirkt als Sirupträger, aber es spielt keine Rolle, ob sie beschichtet wird oder nicht. (In der Tat jede Flip - Lösung Willen Beschichtung der Platte , weil die pancake Fläche berührt müssen beschichtet werden, sondern unabhängig.)
  • Die Platte kann nicht gewendet werden.
  • Sie können annehmen, dass diese Pfannkuchen Einheitsscheiben ohne nennenswerte Seiten sind , sondern nur zwei gegenüberliegende Flächen.

Wertung

Das ist Code-Golf. Die kürzeste Lösung in Bytes gewinnt.

Calvins Hobbys
quelle
4
Dies ist eine sehr, sehr schöne Herausforderung. ;)
Soham Chowdhury
Ist eine Funktion, die eine Liste abruft und einen Booleschen Wert zurückgibt, in Ordnung?
stolzer Haskeller
9
Es sollte einen Bonus geben, wenn jemand es in dieser Sprache implementieren kann .
Grc
3
@grc Dafür gibt es jetzt ein Kopfgeld!
Calvins Hobbys
2
Hier ist meine Lösung in Pancake Stack Put syrup on the pancakes!
:;

Antworten:

9

CJam, 32 30 29 Bytes

q~2@#2b\{)/(W%)1$0=|@]s:~}/:&

Probieren Sie es online aus.

Testfälle

$ cjam pancakes.cjam <<< '2 [1 1 2 2]'; echo
1
$ cjam pancakes.cjam <<< '2 [1 2 2 1]'; echo
0

Wie es funktioniert

q~                            " N, L := eval(input())                                     ";
  2@#2b                       " P := base(2 ** N, 2)                                      ";
       \{                }/   " for F in L:                                               ";
         )/                   "   P := split(P, F + 1)                                    ";
           (W%)               "   T, U, V := P[1:], reverse(P[0])[:-1], reverse(P[-1])[0] ";
               1$0=|          "   V |= U[0]                                               ";
                    @]s:~     "   P := map(eval, str([U, V, T]))                          ";
                           :& " print and(P)                                              ";
Dennis
quelle
17
CJam? Eher wie CRup.
Ingo Bürk
12

Haskell, 92 90 86 84 114 110 99 98

Die Forderung nach einem vollen Programm ist so ärgerlich. Ich frage mich, warum jemand dies verlangen würde.

m(n:s)=all(<1)$foldl(\r@(p:s)n->reverse(take n s)++(p*r!!n):drop n s)[0..n]s
main=readLn>>=print.m

Bei dieser Lösung wird der Stapel der Pfannkuchen durch eine Liste der Seiten dargestellt, wenn benachbarte Pfannkuchen dieselbe Seite haben. Jede Seite ist eine Zahl, und eine Seite wird beschichtet, wenn sie den Wert Null hat.

Rennen wie:

*Main> main
[2,1,1,2,2]
True
stolzer haskeller
quelle
1
+1 für nicht mit Python 2;)
Calvins Hobbys
@ Calvin'sHobbies lol
stolzer Haskeller
Ich fürchte, ein vollständiges Programm ist erforderlich ...
John Dvorak
1
@ JanDvorak Ich habe das nicht gesehen ... Ich habe nur gefragt, ob eine Funktion in den Kommentaren der Frage in Ordnung ist. Wenn nicht, werde ich es ändern
stolzer Haskeller
@proudhaskeller jetzt wurde dir von OP explizit gesagt ... ich erwarte bald eine Änderung.
John Dvorak
10

Python, 92 Bytes

Ich denke das funktioniert:

s=[1]+[0,0]*input()
for f in input():x=f*2;s[0]=s[x]=s[0]|s[x];s[:x]=s[x-1::-1]
print all(s)

Es verwendet eine Liste von Pfannkuchen-Gesichtern (Platte eingeschlossen), um sich zu erinnern, welche mit Sirup überzogen sind. Pfannkuchen werden durch Umkehren eines Teils der Liste gewendet, aber jeder Sirup wird zuerst zwischen der Oberseite und dem neu aufgedeckten Gesicht übertragen.

Verwendung:

$ python pancakes.py
2
1, 1, 2, 2
True
grc
quelle
Das ist eine wirklich sehr, sehr clevere Art umzukehren. +1
Soham Chowdhury
Es sieht so aus, als würden Sie den Teller von der Prüfung "Ist alles Sirup?" Ausschließen. Musst du? Wenn alle Pfannkuchenflächen beschichtet sind, berührt die Platte eine sirupartige Pfannkuchenfläche, so dass die Platte auch sirupartig ist.
user2357112 unterstützt Monica
@ user2357112 Ja, du hast recht. Vielen Dank!
Grc
8

Python 2: 75

Eine Vereinfachung der Lösung von grc und feersum.

n,b=input()
s=[1]+[0]*n
for x in b:s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

Das Speichern des Sirupzustands von 2*n+1Pfannkuchenrändern ist überflüssig, da sich berührende Ränder immer gleich sind. Dies erinnert sich stattdessen an den Zustand jeder n+1Pfannkuchenverbindung. Auf diese Weise wird die Sirupübertragung automatisch berücksichtigt.

Das einzige Update, das benötigt wird, ist, den Sirup an der xKreuzung zu konservieren, wenn ein Flip ihn schneidet. Dies geschieht, indem man den Sirup 0nach dem Umdrehen in die Pfanne gibt x.

Die zweimalige Eingabe wirkt sich nicht auf die Anzahl der Zeichen aus.

s=[1]+[0]*input()
for x in input():s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)
xnor
quelle
5

Python 2, 93 Bytes

Zuerst wollte ich meine Antwort posten, aber grc hatte bereits eine Minute zuvor eine sehr ähnliche Antwort gepostet. Also habe ich versucht, ein paar Verbesserungen zu finden. Das Einzige, was ich finden konnte, war, einen lexikografischen Listenvergleich anstelle von zu verwenden all().

Bearbeiten: Ein Fehler wurde behoben, der dadurch verursacht wurde, dass verschiedene Eingabemethoden erfolglos ausprobiert wurden, wodurch die Anzahl der Zeichen nicht geändert wurde.

n,F=input()
L=[1]+2*n*[0]
for f in F:f*=2;L[0]=L[f]=L[0]|L[f];L[:f]=L[~-f::-1]
print[1]*2*n<L

Beispiel Input / Output:

2, [1, 1, 2]

 

False
Feersum
quelle
3

APL, 77

∧/⊃{x[1]+←⍺⌷x←⍵⋄(⌽⍺↑x),⍺↓x}/(⌽1+⎕),⊂1,⎕⍴0
TwiNight
quelle
2

Python 2, 107

d=[1]+[0,0]*input()
for i in input():n=2*i;d[:n]=reversed(d[:n]);d[n]=d[n-1]=d[n]|d[n-1]
print(all(d[:-1]))
Soham Chowdhury
quelle
2

Haskell, 129, 125

t(m:l)=all(any(<1).(\i->foldr(\n->foldr($)[].map(n%))[i]l))[0..m]
n%i|i>n=(i:)|i<n=(n-i:)|1>0=(n:).(0:)
main=readLn>>=print.t

Wahrscheinlich noch nicht vollständig golfen, aber es funktioniert, ohne eine Liste der beschichteten Seiten zu manipulieren. Stattdessen arbeitet es sich rückwärts, um herauszufinden, ob eine bestimmte Seite eines bestimmten Pfannkuchens jemals mit etwas in Kontakt gekommen ist, das zu Beginn die Oberseite war. foldrDurchläuft die Liste der Klappen effektiv rückwärts, daher gibt es keine reverse.

Hier ist also der Algorithmus: Wir ordnen alle relevanten Seiten ( [0..m]) zu und erstellen eine Liste der Seiten, von denen unsere Seite Sirup erbt, beginnend von hinten: Anfangs ist die Liste nur [i], aber mit einem Flip von nPfannkuchen, jeder Eintrag wird [n-i]wenn i<n, [n,0]wenn i==n, und [i]wenn i>n. Die betreffende Seite wurde genau dann beschichtet, wenn die resultierende Liste nach allen Umblättern ein 0( any (<1)) enthält . allerledigt den Rest und mainwandelt alles in ein lauffähiges Programm um.

Das Programm erhält seine Eingabe stdinin Form von [n_pancakes, flip1, flip2, flip3, ...], durch einen Zeilenumbruch abgeschlossenen.

TheSpanishInquisition
quelle
interessanter Ansatz.
stolzer Haskeller
Wie wäre es , wenn Sie nicht Funktionen zum Codieren der Vererbungsliste verwenden, um Listen zu verwenden, n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]sondern stattdessen alle Vererbungen zuordnen und sie verbinden. foldr($)[].map(n%)(=<<).(%)
stolzer Haskeller
Sie haben mir klar gemacht, dass ich mit einem Stapel von [0..]beschichteten Pfannkuchen als 0 beginnen kann, anstatt beschichtete Pfannkuchen ungleich Null herzustellen. Vielen Dank!
stolzer Haskeller