Stackylogic to język programowania, który wymyśliłem w poprzednim wyzwaniu: Uruchom Stackylogic . Przeczytaj ten post, aby uzyskać szczegółowe informacje i przykłady, ale oto, jak to działa sparafrazowane:

Stackylogic wykonuje 0„S 1” a dla wejścia i wyjścia do jednego 0 lub 1po zakończeniu.

Program składa się z wierszy zawierających tylko znaki, 01?a także dokładnie jeden <na końcu jednego z wierszy. Linie nie mogą być puste, a linia z <musi mieć co najmniej jednego 0, 1lub ?przed nim.

Oto przykładowy program, który oblicza NAND dwóch bitów:

1
?<
11
?
0

Każda linia w programie jest uważana za stos , z dolną po lewej stronie i górną po prawej stronie. Domniemany jest pusty stos (tj. Pusta linia) przed pierwszą linią w programie i po ostatniej linii.

<, Nazywa się kursora znaki stos, aby rozpocząć, gdy program jest uruchomiony. Wykonanie przebiega w następujący sposób:

1. Usuń górną postać ze stosu, na który wskazuje obecnie kursor.

   • Jeśli znakiem jest ?, poproś użytkownika o znak a 0lub a 1i postępuj tak, jakby to był znak.
   • Jeśli znak jest 0, przesuń kursor o jeden stos w górę (do linii powyżej bieżącej linii).
   • Jeśli znak jest 1, przesuń kursor o jeden stos w dół (do linii poniżej bieżącej linii).

2. Jeśli stos, do którego przesuwa się kursor, jest pusty, wypisz ostatnią wartość, która została usunięta ze stosu (zawsze a 0lub 1) i zakończ program.

3. W przeciwnym razie, jeśli stos, na który przesuwa się kursor, nie jest pusty, wróć do kroku 1 i powtórz proces.

Kluczową rzeczą do zrealizowania w tym wyzwaniu jest to, że wszystkie programy Stackylogic są zgodne z tabelą prawdy . Wprowadzana jest pewna z góry określona liczba wartości boolowskich, a dokładnie jedna wartość boolowska jest deterministycznie wyprowadzana.

Zatem twoim zadaniem jest stworzenie programu Stackylogic, który spełnia lub symuluje, tj. Ma takie same wyniki jak jakakolwiek podana tabela prawdy. Ale nie jest oczywiste, że Stackylogic może symulować dowolną tabelę prawdy, więc oto dowód indukcyjny :

Podstawa

Dwie tablice prawdy z 0 wejściami to tabele, które zawsze generują 0lub 1. W Stackylogic ekwiwalenty tych tabelach 0<i 1< odpowiednio.

Krok indukcyjny

Załóżmy, że Stackylogic może symulować dowolną tablicę prawdy z N-wejściami. Niech M = N + 1.

Tabela M wejściowy T mogą być wyrażone jako dwa stoły N wejściowych, t ₀ i T ₁ , plus dodatkowy bit wejściowy B. Gdy B oznacza 0, wynik T ₀ używany. Gdy B oznacza 1, wynik T ₁ jest używany.

Na przykład 3-wejściowa tabela prawdy odpowiadająca pseudokodowi

if B:
    result = x OR y
else:
    result = x NAND y

jest

B x y | result
0 0 0 | 1
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

czyli tak naprawdę dwie 2-wejściowe tabele prawdy dla NAND i OR ułożone jeden na drugim z bitem multipleksowania B.

Niech S ₀ i S ₁ będą programami Stackylogic, które spełniają odpowiednio T ₀ i T ₁ (wiemy, że istnieją one na podstawie pierwszego założenia). Program S, który spełnia T, można następnie skonstruować jako:

[lines of S0 excluding the cursor, with 0 appended to all lines below the cursor]
?<
[lines of S1 excluding the cursor, with 1 appended to all lines above the cursor]

Taki układ skutecznie multipleksuje między S ₀ i S _{1 w} oparciu o pierwszy bit wejściowy (z linii ?<). Jeśli tak jest 0, 0kursor przesunie dołączone elementy do pierwotnej pozycji kursora S ₀ , która następnie będzie otoczona górą i dołem pustymi stosami, a zatem będzie przebiegać dokładnie identycznie jak oryginalna S ₀ . Podobnie, jeśli 1zostanie wprowadzone, kursor przesunie się w 1dół do pozycji kursora S ₁ i przystąpi do wykonania go tak, jakby był sam.

Na przykład programami Stackylogic dla OR i NAND są

?
?<

i

1
?<
11
?
0

Można je łączyć w celu symulacji

if B:
    result = x OR y
else:
    result = x NAND y

tak:

1
?
110
?0
00
0
?<
?1
?

Tak więc dowolna tabela prawdy może być symulowana przez program Stackylogic.

Wyzwanie

Napisz program lub funkcję, która przyjmuje tablicę N wejściowej tabeli prawdy (N> 0) w formie listy 2 ^N. wartości logicznych, które reprezentują wyniki tabeli w rosnącym porządku binarnym.

Każdy rozsądny format wejściowy jest w porządku. np. dla tabeli prawdy OR

x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

dowolny z tych stylów wprowadzania byłby w porządku:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Wydrukuj lub zwróć program Stackylogic, który spełnia tabelę prawdy, tzn. Ma dokładnie to samo wyjście przy tych samych danych wejściowych. Każdy skończony program, który spełnia tę tabelę, jest prawidłowym wyjściem. Nie musisz stosować metody konstrukcji opartej na dowodzie indukcyjnym. Programy Stackylogic nie muszą być optymalnie krótkie.

Na przykład, jeśli dane wejściowe byłyby 11100111, jednym prawidłowym wyjściem byłoby

1
?
110
?0
00
0
?<
?1
?

ale jest wiele innych.

Najkrótszy kod w bajtach wygrywa.

Zobacz oryginalne wyzwanie Stackylogic, jeśli potrzebujesz tłumacza.

Pyth, 53 bajty

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<

Wypróbuj online

Jest to dokładna implementacja systemu opisanego w wyzwaniu dotyczącym sposobu implementacji dowolnych tabel prawdy w Stackylogic. Po prostu przecinamy tabelę prawdy na pół, implementujemy ją rekurencyjnie, a następnie dodajemy odpowiednio 0 i 1.

Definiuje to funkcję rekurencyjną, której zwracaną wartością jest [1, ['0', '?', '1']], gdzie pierwsza liczba to lokalizacja wskaźnika, a reszta to program stackylogiczny.

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<
                                                         Q = eval(input())
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hb
L                                                 def y(b): return
 ?tb                                              if b[1:] (base case on false)
                                      ,0]`hb      else: [0, str([0])]
                                                  then:
           c2b                                    Cut the input in half
         yM                                       Map y over the halves
        J                                         Store that in J
    ,leh                                          The cursor position is the length 
                                                  of the body of the first function
                 .e                 J             enum-map, where k is the index
                                                  and b is the value, over J
                   .e             eb              enum-map, Y is the index and
                                                  Z is the value, over body of b
                     +W         Zk                Add to Z (line) k (the overall 
                                                  index, 0 or 1) conditional on
                          -Yhb                    Y (line index) - cursor
                       _Wk                        Negated if k
                      >       0                   > 0
               X0                    \?           Add '?' to the first element
              s                                   Concatenate, giving the body

jXF+yQ\<
    yQ      Call the above on the input
   +  \<    Append a '<'
 XF         Splat the 3 element list into the 'append-at' function,
            adding the curson in the right place
j           Join on newlines and print.

Python 3, 352 208 205 bajtów

To jest nadal bardzo nierozwinięte i postaram się dodać wyjaśnienie później. Po kilku modyfikacjach udało mi się usunąć 144 147 bajtów.

f=lambda x,l=len,r=range:'\n'.join(*x)if l(x)<2 else f([[x[i][j]+['0',''][j<=l(x[i])//2]for j in r(l(x[i]))]+[['?','?<'][l(x)<3]]+[x[i+1][j]+['1',''][j>=l(x[i])//2]for j in r(l(x[i]))]for i in r(0,l(x),2)])

Funkcja, fktóra pobiera wartości z tabeli prawdy jako listę booleanów formularza ['1','1','1','0','0','1'...], gdzie'1' booleanów jest prawdą i '0'falsey, i zwraca program Stackylogic.

Wypróbuj na Ideone

Jeśli chcesz przetestować produkowanego programu, można użyć GamrCorps „s Convex tłumacza tutaj .

Jak to działa

Jest to funkcja rekurencyjna i wykorzystuje metodę indukcyjną opisaną w pytaniu.

Na poziomie rekursji o indeksie zerowym afunkcja tworzy n/2 a+1-input Programy Stackylogic z n aprogramów -input na liście. Odbywa się to poprzez połączenie wszystkich sąsiednich par dwóch programów z listy za pomocą ?; ponieważ kursor zawsze znajduje się w środkowym elemencie każdego programu składowego, wymagane dołączanie 0lub 1można je wykonać przez iterację po każdej linii łączonych programów i dołączanie, jeśli indeks bieżącej linii jest mniejszy lub równy / większy niższy lub równy odpowiednio środkowemu wskaźnikowi. Jeśli lista zawiera tylko dwa programy, następne wywołanie cykliczne da program końcowy; ponieważ wymaga to kursora, zamiast tego następuje połączenie ?<.

Gdy lista ma długość 1, lista musi zawierać tylko jeden element zawierający pełny program. Dlatego wszystkie linie w programie są łączone na nowej linii, a następnie zwracane.

Przykład pomaga to zilustrować:

Take the input ['1', '1', '1', '0', '0', '1', '1', '1'].

Level  Return value

0  [['1', '?', '1'], ['1', '?', '0'], ['0', '?', '1'], ['1', '?', '1']]
1  [['1', '?', '10', '?', '11', '?', '0'], ['0', '?', '10', '?', '11', '?', '1']]
2  [['1', '?', '10', '?', '110', '?0', '00', '?<', '01', '?1', '101', '?', '11', '?', '1']]
3  '1\n?\n10\n?\n110\n?0\n00\n?<\n01\n?1\n101\n?\n11\n?\n1'

which when printed gives:

1
?
10
?
110
?0
00
?<
01
?1
101
?
11
?
1