Dans ce défi, vous écrirez un interprète pour 2 ^Ω (transcrit en TwoMega ), un langage basé vaguement sur le brainfuck avec un espace de stockage de dimension infinie.

La langue

2 ^Ω contient trois éléments d'état:

• La bande , qui est une liste infinie de bits, tous initialisés à 0. Elle a un élément le plus à gauche, mais pas d'élément le plus à droite.

• Le pointeur de mémoire , qui est un entier non négatif qui est un index d'un élément de la bande. Un pointeur de mémoire supérieur fait référence à une cellule de bande plus à droite; un pointeur de mémoire de 0 fait référence à l'élément le plus à gauche. Le pointeur de mémoire est initialisé à 0.

• L' Hypercube , qui est une "boîte" de cellules conceptuellement ∞- dimensionnelle, dont chacune contient un bit initialisé à 0. La largeur de l'Hypercube est liée dans chaque dimension à seulement 2 cellules, mais l'infinité des dimensions signifie le nombre de les cellules sont innombrables .

Un index dans l'hypercube est une liste infinie de bits qui fait référence à une cellule de l'hypercube (de la même manière qu'une liste finie de bits pourrait être utilisée pour faire référence à un hypercube de dimension finie). Parce que la bande est une liste infinie de bits, la bande entière se réfère toujours à un élément de l'hypercube; cet élément est appelé référent .

2 ^Ω donne un sens à 7 caractères différents:

• < décrémente le pointeur de mémoire de 1. Le décrémenter en dessous de 0 est un comportement indéfini, vous n'avez donc pas besoin de le gérer.
• > incrémente le pointeur mémoire de 1.
• ! retourne le bit au référent.
• . sort le bit au référent.
• ^remplace le bit de la cellule pointée par le pointeur de mémoire sur la bande par l' inverse du bit du référent.
• [x]exécute le code xtant que le bit au référent est 1.

Le défi

Votre tâche consiste à écrire un programme qui prend une chaîne en entrée et exécute cette entrée en tant que programme 2 ^Ω .

Il s'agit de code-golf , donc la réponse valide la plus courte (mesurée en octets) l'emporte.

Remarques

• Vous pouvez supposer que le programme se composera uniquement des caractères <>!.^[]et qu'il []sera correctement imbriqué.
• Votre interprète ne doit être limité que par la mémoire disponible sur le système. Il doit pouvoir exécuter les exemples de programmes dans un délai raisonnable.

Exemples de programmes

Imprimer 1:

!.

Imprimer 010:

.!.!.

Imprimer 0 pour toujours:

![!.!]

Imprimez 0 pour toujours ou 1 pour toujours si !est ajouté:

[.]![!.!]

Python 2 , 167 octets

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

Essayez-le en ligne!

t est la bande. t = 6 signifie que la bande est [0 1 1 0 0 0…]

m est 2 à la puissance du pointeur mémoire. Donc m = 8 signifie que nous pointons sur le bit de bande 3.

h est l'hypercube. h = 80 (bits 4 et 6 définis) signifie que les bits à [0 0 1 0…] et [0 1 1 0…] sont définis.

Pour lire le bit chez le référent, on vérifie 2 ^t & h . Pour le retourner, nous effectuons h ^ = 2 ^t .

Nous traduisons les instructions en code Python et exécutons le résultat. Je stocke le niveau d'indentation des boucles while.

JavaScript (Node.js) , 148 octets

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))

Essayez-le en ligne!

C'est complet

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

Besoin d'init comme se déplaçant vers la droite à quelques endroits et initialiser le bit actuel et à droite de l'adresse comme 1 ( >>>>>>>>^>^<)

Essayez-le en ligne!

La place ndans BoolFuck s'écrit (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Car >, c'est le cas 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

Comme pour le <travail

Brain-Flak Classic , 816 octets

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

Essayez-le en ligne!

Ce code a été écrit juste pour que j'aie un endroit pour écrire une preuve d'exhaustivité de Turing.

Preuve de complétude de Turing

Nous montrons une réduction de Boolfuck à TwoMega:

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

Cette traduction stocke l'état Boolfuck dans les cellules de bande paires dans TwoMega. Toutes les commandes traduites conserveront les invariants suivants:

• Le pointeur de mémoire se trouve dans une cellule de numéro pair.
• Toutes les cellules de bande impaires sont nulles.
• Pour toute bande possible avec toutes les cellules impaires zéro, la valeur correspondante sur l'hypercube est zéro.

L'extrait !^!restera [0]0constant et échangera entre 0[0]et [1]1(où l'attention est limitée à la ligne sur l'hypercube accessible sans déplacer le pointeur de mémoire). En tant que tel, il est utilisé pour placer temporairement la valeur de bande actuelle dans le référent pour les commandes Boolfuck qui s'en soucient.

Si TwoMega recevait une commande d'entrée ,avec la sémantique attendue, la commande Boolfuck ,se traduirait par >^<,!^>[!]!^<. Puisqu'il ,n'est pas nécessaire de prouver que Boolfuck est Turing-complete, l'absence d'une commande d'entrée n'affecte pas cette preuve.

Python 3 , 297 284 274 octets

-10 octets grâce aux ovs et Jonathan Allan

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)

Essayez-le en ligne!

Pip , 75 71 octets

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

Essayez-le en ligne!

Traduit le code 2 ^{Ω en} code Pip équivalent et l'évalue.

Nous utilisons ipour représenter la bande, vpour le pointeur de bande * et lpour l'hypercube. Les deux premiers sont pré-initialisés à des valeurs utiles; lcommence par [], auquel nous poussons un 0( lPU0) pour éviter les problèmes d'indexation-liste vide.

^{* En fait, c'est la négation au niveau du bit du pointeur de bande, car nous stockons la bande en arrière pour une conversion plus facile en décimal.}

Le reste du code est:

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

La table de traduction:

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

l@FBiest l'élément référent: de l'hypercube là l'index (convertir idu binaire). Il apparaît souvent, nous l'appelons donc _et le remplaçons _par le vrai code à la fin.

• !:_ nie logiquement le référent en place.

• --viPU0décrémentations v(déplacement du pointeur de bande vers la droite); il en pousse ensuite un autre 0vers la gauche ipour s'assurer que le pointeur de bande reste dans les limites.

• ++vincréments v(pas besoin de vérification des limites, par OP).

• W_{exécute une boucle pendant que le référent est véridique (ie non nul, ie 1).

• } ferme la boucle.

• O_ affiche le référent sans nouvelle ligne.

Enfin, pour ^:

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