W tym wyzwaniem, można napisać tłumacza dla 2 ^Ohm (transkrypcji jako TwoMega ), język oparty luźno na brainfuck z nieskończoną-wymiarowej przestrzeni magazynowej.

Język

2 ^Ω zawiera trzy części stanu:

• Tape , która jest nieskończona lista bitów, wszystkie inicjowany na 0. To ma skrajnie lewą element, ale nie skrajny prawy element.

• Pamięci wskaźnik , który jest dodatnią liczbą całkowitą, która ma indeks elementu z taśmy. Wyższy wskaźnik pamięci odnosi się do komórki taśmy po prawej stronie; wskaźnik pamięci 0 oznacza lewy element. Wskaźnik pamięci jest inicjowany na 0.

• Hypercube , który jest koncepcyjnie ∞ wymiarową „skrzynka” komórek, z których każda zawiera nieco zainicjowanym z wartością 0. szerokość hipersześcianu jest związana w każdym wymiarze tylko dwóch komórek, ale nieskończoność rozmiarów oznacza liczbę komórki to niepoliczalne .

indeks do hipersześcianu nieskończona listę bitów odnosi się do komórki w hipersześcianu (w taki sam sposób, jak lista skończonych bitów może być używane w odniesieniu do hipersześcianu skończonych wymiarach). Ponieważ taśma jest nieskończoną listą bitów, cała taśma zawsze odnosi się do elementu Hypercube; element ten nazywa się odnośnikiem .

2 ^Ω nadaje znaczenie 7 różnym znakom:

• < zmniejsza wskaźnik pamięci o 1. Zmniejszenie go poniżej 0 jest niezdefiniowanym zachowaniem, więc nie musisz go obsługiwać.
• > zwiększa wskaźnik pamięci o 1.
• ! odwraca bit w stosunku do odnośnika.
• . wypisuje bit pod odnośnikiem.
• ^zamienia bit w komórce wskazanej przez wskaźnik pamięci na taśmie odwrotnością bitu w odnośniku.
• [x]uruchamia kod, xo ile bit przy odnośniku wynosi 1.

Wyzwanie

Twoim zadaniem jest napisanie programu, który pobiera ciąg znaków jako wejście i wykonuje to wejście jako program o wartości 2 ^Ω .

To jest golf-golf, więc wygrywa najkrótsza poprawna odpowiedź (mierzona w bajtach).

Notatki

• Możesz założyć, że program będzie się składał wyłącznie ze znaków <>!.^[]i że []będzie odpowiednio zagnieżdżony.
• Twój tłumacz powinien być ograniczony tylko dostępną pamięcią w systemie. Powinno być możliwe uruchomienie przykładowych programów w rozsądnym czasie.

Przykładowe programy

Drukuj 1:

!.

Drukuj 010:

.!.!.

Drukuj 0 na zawsze:

![!.!]

Drukuj 0 na zawsze lub 1 na zawsze, jeśli !jest poprzedzony:

[.]![!.!]

Python 2 , 167 bajtów

t=h=I=0
m=1
E=''
for c in input():i='[<>!.^]'.find(c);E+=' '*I+'while+2**t&h: m/=2 m*=2 h^=2**t print+(2**t&h>0) t=t&~m|m*(2**t&h<1) #'.split()[i]+'\n';I-=~-i/5
exec E

Wypróbuj online!

t jest taśmą. t = 6 oznacza, że ​​taśma jest [0 1 1 0 0 0…]

m oznacza 2 do mocy wskaźnika pamięci. Więc m = 8 oznacza, że ​​wskazujemy bit taśmy 3.

h to hipersześcian. h = 80 (ustawione bity 4 i 6) oznaczają bity w [0 0 1 0…] i [0 1 1 0…] są ustawione.

Aby odczytać bit pod odnośnikiem, sprawdzamy 2 ^t & h . Aby to przerzucić, wykonujemy h ^ = 2 ^t .

Tłumaczymy instrukcje na kod Python i wykonujemy wynik. I przechowuje poziom wcięcia pętli while.

JavaScript (Node.js) , 148 bajtów

x=>eval(x.replace(e=/./g,c=>({'<':'u/=2','>':'u*=2','!':'e[v]^=1','.':'alert(+!!e[v])','^':'v=(v|u)^u*e[v]','[':'while(e[v]){'}[c]||'}')+';',v=u=1))

Wypróbuj online!

To wszystko się kończy

BoolFuck TwoMega
< >^>^>[!]^<<<<[!]^>>[!]!^>[!]!^>[!]!^<<<<(>^>^>1<<<<1>>0>0>0<<<<)
> ^<^<[!]^>>>>[!]^<<[!]!^<[!]!^<[!]!^>>>(^<^<1>>>>1<<0<0<0>>>)

Potrzebujesz init jako przesunięcia w prawo o kilka miejsc i zainicjowania bieżącego i prawego jednego bitu adresu jako 1 ( >>>>>>>>^>^<)

Wypróbuj online!

Miejsce nw BoolFuck jest zapisane jako (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Ponieważ >robi n=>n+1

     0 0 0 0 0[1]1 0 0 0 0
^    0 0 0 0 0[x]1 0 0 0 0
<    0 0 0 0[0]x 1 0 0 0 0
^    0 0 0 0[y]x 1 0 0 0 0, yx != 01
<    0 0 0[0]y x 1 0 0 0 0
[!]^ 0 0 0[1]y x 1 0 0 0 0, (0yx10) = 0
>>>> 0 0 0 1 y x 1[0]0 0 0
[!]^ 0 0 0 1 y x 1[1]0 0 0, (1yx10) = 0
<<   0 0 0 1 y[x]1 1 0 0 0
[!]! 0 0 0 1 y[x]1 1 0 0 0, (1yx11) = 1
^    0 0 0 1 y[0]1 1 0 0 0
<    0 0 0 1[y]0 1 1 0 0 0
[!]! 0 0 0 1[y]0 1 1 0 0 0, (1y011) = 1
^    0 0 0 1[0]0 1 1 0 0 0
<    0 0 0[1]0 0 1 1 0 0 0
[!]! 0 0 0[1]0 0 1 1 0 0 0, (10011) = 1
^    0 0 0[0]0 0 1 1 0 0 0
>>>  0 0 0 0 0 0[1]1 0 0 0

To samo, co <działa

Brain-Flak Classic , 816 bajtów

<>(((<(())>)))<>{(([][][])(((({}){}[])({}))({})[]([][](({})(({}())(({}){}{}({}(<()>))<{<>({}<>)}{}>))))))(([]{()(<{}>)}{}){<((<{}>))<>(()(){[](<{}>)}{}<{({}[]<({}<>)<>>)}{}{}>)<>({()<({}<>)<>>}<<>{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(({})<<>{({}[]<({}<>)<>>)}({}<>)<>{({}<>)<>}>)<>>)<>({}<>)<>>}{}([]{()(<{}>)}{}){{}<>({})(<>)}{}([]{()(<{}>)}{}){(<{}<>({}<{((<({}[])>))}{}{((<(())>))}{}>)<>>)}{}([]{()(<{}>)}{}){(<{}<>({}<({}())>)<>>)}{}([]{()(<{}>)}{}){(<{}<>[({})]<>>)}{}([]{()(<{}>)}{})<{((<{}>))<>{}({}<{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(((){[](<{}>)}{})<<>{({}[]<({}<>)<>>)}{}(<>)<>{({}<>)<>}>)<>>)<>({}<>)<>}{}(<>)<>{({}<>)<>}{}>()){((({}[]<>){(<{}({}<>)>)}{}())<{({}<({}<>)<>((((((([][][]){}){}){}()){}){}({})())[][])>{[](<{}>)}{}{()(<{}>)}{})}{}({}<>)>[]){{}(<>)}}{}}

Wypróbuj online!

Ten kod został napisany tylko po to, żeby mieć miejsce na napisanie dowodu kompletności Turinga.

Dowód kompletności Turinga

Pokazujemy redukcję z Boolfuck do TwoMega:

Boolfuck   TwoMega
>          >>
<          <<
.          !^!.!^!
[          !^![!^!
]          !^!]!^!
+          !^[!]^[>!^<[!]!^>[!]!^<]

To tłumaczenie przechowuje stan Boolfuck w parzystych komórkach taśmy w TwoMega. Wszystkie przetłumaczone polecenia zachowają następujące niezmienniki:

• Wskaźnik pamięci znajduje się w parzystej komórce.
• Wszystkie nieparzyste komórki taśm mają zero.
• Dla każdej możliwej taśmy z wszystkimi komórkami nieparzystymi zero odpowiednia wartość w hipersześcianie wynosi zero.

Urywek !^!będzie się utrzymywał na [0]0stałym poziomie i zamieniał pomiędzy 0[0]i[1]1 ( gdzie uwaga jest ograniczona do linii na hipersześcianie, do której można dotrzeć bez poruszania wskaźnikiem pamięci). Jako taki służy do tymczasowego umieszczenia bieżącej wartości taśmy w odnośniku dla poleceń Boolfuck, które się nią zajmują.

Jeśli TwoMega otrzyma polecenie wejściowe ,z oczekiwaną semantyką, polecenie Boolfuck ,przetłumaczy się na >^<,!^>[!]!^<. Ponieważ ,nie jest konieczne udowodnienie, że Boolfuck jest kompletny w Turinga, brak polecenia wejściowego nie wpływa na ten dowód.

Python 3 , 297 284 274 bajtów

-10 bajtów dzięki ovs i Jonathanowi Allanowi

C=input()
h={}
t=set()
def f(C,p):
 c=C[0];r=hash(frozenset(t));v=h.get(r,0)
 p={"<":p-1,">":p+1}.get(c,p)
 if'"'>c:h[r]=not v
 if"."==c:print(int(v))
 if"]"<c:t.discard(p)if v else t.add(p)
 if"["==c:
  while f(C[1:],p):1
 else:return c=="]"and v or C and f(C[1:],p)
f(C,0)

Wypróbuj online!

Pip , 75 71 bajtów

lPB0aR:^"!><[].^_""!:_
--viPU0
++v
W_{
}
O_
i@v:!_LFBilPB0
l@FBi"^n;Vau

Wypróbuj online!

Tłumaczy kod 2 ^Ω na równoważny kod Pip i ocenia go.

Używamy ido reprezentowania taśmy, vwskaźnika taśmy * i lhipersześcianu. Pierwsze dwa są wstępnie zainicjowane do użytecznych wartości; lzaczyna się jako [], do którego naciskamy a 0( lPU0), aby uniknąć problemów z indeksowaniem pustej listy.

^{* W rzeczywistości jest to bitowa negacja wskaźnika taśmy, ponieważ przechowujemy taśmę do tyłu w celu łatwiejszej konwersji na dziesiętną.}

Reszta kodu to:

aR:...;     Do a bunch of replacements in a, translating it into Pip code
       Va   Evaluate a
         u  Suppress output of the final expression that was evaluated

Tabela tłumaczeń:

!  !:_
>  --viPU0
<  ++v
[  W_{
]  }
.  O_
^  i@v:!_LFBilPB0
_  l@FBi

l@FBito odnośnik: element hipersześcianu lw indeksie (konwersja iz pliku binarnego). Pojawia się często, dlatego nazywamy go _i zastępujemy _prawdziwym kodem na końcu.

• !:_ logicznie neguje odniesienie na miejscu.

• --viPU0zmniejszenia v(przesunięcie wskaźnika taśmy w prawo); następnie przesuwa kolejną 0na lewą stronę i, aby upewnić się, że wskaźnik taśmy pozostaje w granicach.

• ++vprzyrosty v(nie ma potrzeby sprawdzania granic, na PO).

• W_{uruchamia pętlę, podczas gdy referencja jest prawdziwa (tzn. niezerowa, tj 1.).

• } zamyka pętlę.

• O_ wyprowadza odnośnik bez znaku nowej linii.

Wreszcie dla ^:

i@v:            Set the current tape cell to
    !_          The logical negation of the referent
                Now, make sure the list representing the hypercube is long enough:
      LFBi      Loop frombinary(i) times:
          lPB0  Push another 0 to the end of l
                This ensures that FBi will always be a valid index into l