To zabawny wypadek, że ten świat ma tylko jeden wymiar czasu, ale nie musi tak być. Łatwo jest sobie wyobrazić światy o 2 lub więcej wymiarach czasowych, w których można budować komputery i uruchamiać na nich oprogramowanie, tak jak w tym świecie.
System
Oto system do uruchamiania programów Brainf * ck w dwóch wymiarach czasowych:
Dwa wymiary czasowe to xiy. Każdy program Brainf * ck składa się z półprogramu xi półprogramu, np. Program może być
x: +>+
y: [-]
Każdy z dwóch półprogramów ma własny wskaźnik programu, ale mają one wspólny wskaźnik taśmy (to znaczy oba działają na tej samej komórce taśmy).
Czas jest dwuwymiarowy, więc składa się z siatki momentów:
Poruszając się wzdłuż wymiaru x, półprogram x wykonuje jeden krok czasowy. Poruszając się wzdłuż wymiaru y, półprogram y wykonuje jeden krok czasowy.
Powiedzmy na przykład, że taśma zaczyna się jako [0] 0 0
( []
reprezentuje wskaźnik taśmy), a programami x / y są +
i ->-
. Wykonanie tego programu wyglądałoby następująco:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Zauważ, że wraz z upływem czasu w kierunku y półprogram x ciągle robi to samo, ponieważ jego czas nie postępuje.
Taśma w każdym momencie zawiera łączny efekt wszystkich akcji, które się do niej zasilają (każda akcja liczy się raz). Na przykład taśma w momencie (2, 1) zawiera łączny efekt:
- akcja x z (0, 0)
- akcja x z (1, 0)
- akcja x z (0, 1)
- akcja x z (1, 1)
- akcja y z (0, 0)
- akcja y z (1, 0)
- akcja y z (2, 0)
Skumulowane oznacza:
- Wszystkie przyrosty i zmniejszenia sumy komórki razem.
- Wszystkie lewe (-1) i prawe (+1) ruchy do wskaźnika taśmy sumują się razem.
Wskaźniki instrukcji nie kumulują się. Każdy półprogram otrzymuje swój wskaźnik instrukcji z poprzedniego momentu w swoim wymiarze. Oznacza to, że wskaźniki programu x przesuwają się tylko w wymiarze x, a wskaźniki programu y postępują tylko w wymiarze y. Na przykład w programie ( []
, +
) począwszy od [0] 0 0
wykonania byłoby wykonanie
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Jeszcze kilka chwil z powyższej ( +
, ->-
) symulacji to:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Dozwolone są następujące operatory Brainf * ck (mają swoje standardowe znaczenie):
+
,-
: przyrost, spadek;[
,]
: pętla do zera (przetwarzanie a[
lub]
zajmuje jeden krok czasowy, jak w standardowym Brainf * ck);<
,>
: przesuń w lewo / prawo na taśmie.
Złożony przykład
Dla programu ( >
, +
) rozpoczynającego się od [0] 0 0
:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Dla ( +
, -
) zaczynające się od [0] 0 0
:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Zauważ, że taśma kończy się tak, [0] 0 0
ponieważ każdy +
i -
zdarza się dwa razy, sumując do 0.
Dla programu ( >+
, [-]
) rozpoczynającego się od [0] 0 0
:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Schemat ze strzałkami
Poniższy schemat pokazuje, jak obliczyć akcje i taśmę:
Zagadka
Napisz program 2D Brainf * ck (z półprogramem xi ay półprogramem), aby uruchomić na taśmie 3-komórkowej, która spełnia oba następujące warunki:
- Jeśli taśma zaczyna się tak
[0] 0 0
, jak w momencie (5, 5), ma0
w komórce zerowej. - Jeśli taśma zaczyna się tak
[1] 0 0
, jak w momencie (5, 5), ma0
w komórce zerowej.
Wygrywa najkrótszy program spełniający wymagania.
+
i>
? Jeśli to1 1 [0]
(dość szalone, ale wydaje się, że sugeruje to specyfikacja), jak łączą się wskaźniki instrukcji? Jeżeli te dwa wątki są+
a[]
, potem na1 2
taśmie danych będzie[3]
, ale jest drugi wskaźnik instrukcji wewnątrz pętli ([]+
ścieżki) lub na zewnątrz ([+]
ścieżka) lub nawet nielegalne (+[]
)?+
,>
), aby zobaczyć, czy otrzymam taki sam wynik jak ty.(1,1)
do jednego(1,0)
lub(0,1)
drugiego, ale jeden program zaczyna się od>
drugiego+
, a na pewno ich kolejność ma znaczenie?Odpowiedzi:
4 bajty łącznie: (
[-]
,>
)I napisał brute-Forcer znaleźć najmniejszy taki program.
Oto diagramy tego programu w akcji. Te siatki są rozmieszczone w podobny sposób jak siatka w specyfikacji, z (0,0) lewym dolnym rogiem, czas x wzdłuż osi x i czas y wzdłuż osi y. Prawy górny róg zawiera wynik.
Najpierw z taśmą
0 0 0
:Teraz z taśmą
1 0 0
:Było kilka rzeczy, które nie zostały jasno wyjaśnione w specyfikacji, takich jak fakt, że taśma 3-komórkowa się owija.
Jako bonus, oto wizualizacja (
>+
,[-]
) przykładu:I jeden z (
>+
,+>
) przykład:Zauważ, że prawy górny róg różni się od tego, co wymieniłeś, myślę, że jest to błąd w twoim przykładzie, ponieważ mój kod pasuje do każdego innego przykładu, który próbowałem.
źródło