Problem spalonego naleśnika

23

To wyzwanie jest związane z Flipping Pancakes .

Być może słyszałeś o sortowaniu naleśników , w którym stos naleśników jest sortowany według rozmiaru, wkładając szpachelkę do stosu i przewracając wszystkie naleśniki nad szpachelką, aż naleśniki zostaną posortowane od najmniejszego do największego na talerzu. Problem przypalonego naleśnika jest nieco inny. Wszystkie naleśniki mają teraz jedną stronę, która jest spalona, ​​a strona przypalona każdego naleśnika musi być zwrócona w stronę talerza po zakończeniu sortowania.

Na przykład, biorąc pod uwagę następujący stos (rozmiar naleśnika po lewej stronie. 0Oznacza spaloną stronę w dół i 1oznaczenie spalonej strony w górę):

1 0
3 1
2 1

Możesz przewrócić cały stos, aby uzyskać 20 30 11, przewrócić dwa górne, aby uzyskać, 31 21 11i przerzucić cały stos ponownie, aby uzyskać 10 20 30, posortowany stos przypalonych naleśników. Tę sekwencję ruchów, trzepnięcie 3, trzepnięcie 2, trzepnięcie 3, można przedstawić jako 3 2 3.

Wyzwanie

  • Biorąc pod uwagę tablicę rozmiarów naleśników (niekoniecznie unikatowych) i ich orientację, generuj każdą prawidłową sekwencję sortowania spalonego naleśnika, to znaczy sekwencję przewracania, która prowadzi do sortowania stosu naleśników od najmniejszej do największej ze spalonymi bokami w dół.
  • Dane wejściowe i wyjściowe mogą być dowolnym rozsądnym formatem z separatorami, ale określ, jakich formatów używasz, i określ, który koniec formatu wejściowego to górna część stosu (TOS).
  • Przerzucanie zerowych naleśników jest dozwolone.
  • Dozwolone jest mieszanie separatorów na wejściu / wyjściu.

Przypadki testowe

Dla wszystkich poniższych przypadków testowych wejście to lista, a wyjście to ciąg rozdzielony spacjami, a TOS jest po lewej stronie.

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

Jak zawsze, jeśli coś jest niejasne lub niepoprawne, daj mi znać w komentarzach. Powodzenia i dobrej gry w golfa!

Sherlock9
źródło

Odpowiedzi:

7

Python 2, 83

Dane wejściowe powinny być listą krotek (rozmiar, orientacja) z górą stosu na końcu. Dane wyjściowe to lista rozmiarów, które można przerzucić, oddzielone różnymi rodzajami białych znaków.

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
źródło
2
Najwyraźniej jestem idiotą.
Leaky Nun
Czy 0dozwolona jest lista wyników?
Leaky Nun
19
@LeakyNun Przerzucanie 0 naleśników jest wyjątkowo możliwe. W rzeczywistości robię to teraz.
feersum
@daniero Góra stosu znajduje się po prawej stronie.
Leaky Nun
@LeakyNun oh przepraszam, moje złe
daniero
3

CJam (37 bajtów)

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

Dane wejściowe to tablica w formacie CJam na stdin; wyjście to rozdzielona znakiem nowej linii długość przerzucania na stdout. Górna część stosu znajduje się na indeksie 0; 0wskazuje spaloną stronę do góry i 1wskazuje spaloną stronę w dół.

Demo online

Sekcja

Wyjście zawsze jest 3ndługie, gdzie njest liczba naleśników. Najpierw podrzucamy największy pozostały naleśnik na górę; wtedy, jeśli jest spalony bokiem do dołu, przewracamy ten jeden naleśnik; a następnie przewracamy na dół i powtarzamy, jakby stos naleśników był o jeden krótszy.

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
źródło
3

Ruby, 101 95 93 bajtów

Niezbyt golfowy, chciałem tylko stworzyć wariant bogo. Jest to anonimowa funkcja, która pobiera tablicę tablic i drukuje losowe przerzucenia na standardowe wyjście, aż naleśniki zostaną posortowane.

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

Możesz na przykład przypisać to fi powiedziećf.call [[1, 0], [3, 1], [2, 1]]

-5 bajtów od @Jordan z genialnym wykorzystaniem rassoc
-2 bajtów od @ Sherlock9

daniero
źródło
1
Możesz zapisać kilka bajtów, zastępując a.all?{...}je !a.rassoc(1).
Jordan
@Jordan Wow, to naprawdę genialne! Nie sądzę, żebym kiedykolwiek wcześniej myślał o użyciu ( r) assoc, ale myśląc o tym, jest to prawdopodobnie przydatne w wielu problemach na tej stronie - uważam, że powinien on przejść do postu z ruby ​​dotyczącymi golfa. W każdym razie dzięki :) Udało mi się także zabić kolejny bajt poprzez zastosowanie prawa deMorgansa i zastąpienie untilgo while.
daniero
Ponieważ bjest tylko kiedykolwiek 0lub1 , 1-brównież działałoby i zaoszczędziłoby dwa bajty.
Sherlock9,