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
„S1
” a dla wejścia i wyjścia do jednego0
lub1
po 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 jednego0
,1
lub?
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:
Usuń górną postać ze stosu, na który wskazuje obecnie kursor.
- Jeśli znakiem jest
?
, poproś użytkownika o znak a0
lub a1
i 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).Jeśli stos, do którego przesuwa się kursor, jest pusty, wypisz ostatnią wartość, która została usunięta ze stosu (zawsze a
0
lub1
) i zakończ program.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ą
0
lub1
. W Stackylogic ekwiwalenty tych tabelach0<
i1<
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 0 i T 1 , plus dodatkowy bit wejściowy B. Gdy B oznacza 0, wynik T 0 używany. Gdy B oznacza 1, wynik T 1 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 0 i S 1 będą programami Stackylogic, które spełniają odpowiednio T 0 i T 1 (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 0 i S 1 w oparciu o pierwszy bit wejściowy (z linii
?<
). Jeśli tak jest0
,0
kursor przesunie dołączone elementy do pierwotnej pozycji kursora S 0 , 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 0 . Podobnie, jeśli1
zostanie wprowadzone, kursor przesunie się w1
dół do pozycji kursora S 1 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.
źródło
Odpowiedzi:
Pyth, 53 bajty
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.źródło
Python 3,
352208205 bajtówTo jest nadal bardzo nierozwinięte i postaram się dodać wyjaśnienie później.Po kilku modyfikacjach udało mi się usunąć144147 bajtów.Funkcja,
f
któ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
a
funkcja tworzyn/2
a+1
-input Programy Stackylogic zn
a
programó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łączanie0
lub1
moż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ć:
źródło