<#; "#: ={},>
}=}(.);("@
Innym collab z @ MartinBüttner, kto faktycznie zrobił najbardziej prawie wszystkie gry w golfa dla tego jednego. Przebudowując algorytm, udało nam się znacznie zmniejszyć rozmiar programu!
Wypróbuj online!
Wyjaśnienie
Szybki podkład Labrinth:
Labirynt to język 2D oparty na stosie. Istnieją dwa stosy, główny i pomocniczy, a wyskakiwanie z pustego stosu daje zero.
Na każdym skrzyżowaniu, gdzie istnieje wiele ścieżek, w których wskaźnik instrukcji przesuwa się w dół, sprawdzana jest góra głównego stosu, aby zobaczyć, gdzie iść dalej. Negatyw to skręt w lewo, zero to kierunek na wprost, a dodatni to zwrot w prawo.
Dwa stosy liczb całkowitych o dowolnej precyzji nie są zbyt elastyczne pod względem opcji pamięci. Aby wykonać zliczanie, ten program faktycznie używa dwóch stosów jako taśmy, przy czym przesunięcie wartości z jednego stosu na drugi jest podobne do przesunięcia wskaźnika pamięci w lewo / prawo o komórkę. Nie jest to jednak to samo, ponieważ po drodze w górę musimy przeciągnąć licznik pętli.
Po pierwsze, <i >na obu końcach pop offset i obrócić wiersz kodu, który offsetowej z dala od jednego prawej lub lewej strony. Ten mechanizm służy do uruchamiania kodu w pętli -< wyskakuje zero i obraca bieżący wiersz w lewo, umieszczając adres IP po prawej stronie kodu, a >wyskakuje o kolejne zero i naprawia wiersz z powrotem.
Oto, co dzieje się z każdą iteracją, w odniesieniu do powyższego schematu:
[Section 1]
,} Read char of input and shift to aux - the char will be used as a counter
to determine how many elements to shift
[Section 2 - shift loop]
{ Shift counter from aux
" No-op at a junction: turn left to [Section 3] if char was EOF (-1), otherwise
turn right
( Decrement counter; go forward to [Section 4] if zero, otherwise turn right
= Swap tops of main and aux - we've pulled a value from aux and moved the
decremented counter to aux, ready for the next loop iteration
[Section 3]
@ Terminate
[Section 4]
; Pop the zeroed counter
) Increment the top of the main stack, updating the count of the number of times
we've seen the read char
: Copy the count, to determine how many chars to output
[Section 5 - output loop]
#. Output (number of elements on stack) as a char
( Decrement the count of how many chars to output; go forward to [Section 6]
if zero, otherwise turn right
" No-op
[Section 6]
} Shift the zeroed counter to aux
[Section 7a]
This section is meant to shift one element at a time from main to aux until the main
stack is empty, but the first iteration actually traverses the loop the wrong way!
Suppose the stack state is [... a b c | 0 d e ...].
= Swap tops of main and aux [... a b 0 | c d e ...]
} Move top of main to aux [... a b | 0 c d e ...]
#; Push stack depth and pop it (no-op)
= Swap tops of main and aux [... a 0 | b c d e ...]
Top is 0 at a junction - can't move
forwards so we bounce back
; Pop the top 0 [... a | b c d e ... ]
The net result is that we've shifted two chars from main to aux and popped the
extraneous zero. From here the loop is traversed anticlockwise as intended.
[Section 7b - unshift loop]
# Push stack depth; if zero, move forward to the <, else turn left
}= Move to aux and swap main and aux, thus moving the char below (stack depth)
to aux
; Pop the stack depth
