Programowanie w dwóch wymiarach czasowych

17

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:

Siatka czasów 3 x 3, połączenie działaniami xiy

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:

Które akcje zasilają migawkę taśmy, jak podano poniżej

  • 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 0wykonania 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 0ponieważ 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ę:

Schemat ze strzałkami pokazujący, jak obliczane są części programu

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), ma 0w komórce zerowej.
  • Jeśli taśma zaczyna się tak [1] 0 0, jak w momencie (5, 5), ma 0w komórce zerowej.

Wygrywa najkrótszy program spełniający wymagania.

piekarnik
źródło
Wystarczy zweryfikować: jaki jest wynik działania +i >? Jeśli to 1 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 na 1 2taś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 ( +[])?
John Dvorak,
@JanDvorak Ach, myślę, że rozumiem o co pytasz. Zapomniałem dodać, że każdy program otrzymuje wskaźnik instrukcji z przyległego momentu w swoim wymiarze. Zmienię to i spróbuję uruchomić ( +, >), aby zobaczyć, czy otrzymam taki sam wynik jak ty.
Owen
To miłe wyzwanie, ale wymaga obiektywnego kryterium zwycięstwa, aby móc klasyfikować odpowiedzi.
Martin Ender,
3
Wyzwanie wciąż nie jest dla mnie jasne. Jak dokładnie przebiega czas przez siatkę. Zgodnie z twoją grafiką wydaje się, że mogę dojść (1,1)do jednego (1,0)lub (0,1)drugiego, ale jeden program zaczyna się od >drugiego +, a na pewno ich kolejność ma znaczenie?
Martin Ender,

Odpowiedzi:

8

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:

|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|(>)         |(>)         |(>)         |(>)         |(>)         |(>)         
+------------+------------+------------+------------+------------+------------

Teraz z taśmą 1 0 0:

|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|( 1)  0   0 |( 1)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  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:

|( 0)  0   0 |( 0)  0   0 |( 1)  1   0 
|(>)+        |>(+)        |>+          
|[-]         |[-]         |[-(])       
+------------+------------+------------
|( 0)  0   0 |  0   0 ( 0)|  0   1 ( 1)
|(>)+        |>(+)        |>+          
|[-]         |[-]         |[(-)]       
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0 
|(>)+        |>(+)        |>+          
|([)-]       |([)-]       |([)-]       
+------------+------------+------------

I jeden z ( >+, +>) przykład:

|( 1)  0   0 |  1   1 ( 0)|  1   3 ( 1)
|(>)+        |>(+)        |>+          
|+(>)        |+(>)        |+(>)        
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0 
|(>)+        |>(+)        |>+          
|(+)>        |(+)>        |(+)>        
+------------+------------+------------

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.

PhiNotPi
źródło
To jest niesamowite! Być może masz rację co do błędu. Sprawdzę to jeszcze raz.
Owen,