Interpretar TwoMega

9

Neste desafio, você escreverá um intérprete para 2 Ω (transcrito como TwoMega ), uma linguagem baseada livremente no cérebro, com um espaço de armazenamento de dimensão infinita.

O idioma

2 Ω contém três partes do estado:

  • A fita , que é uma lista infinita de bits, foi inicializada como 0. Ela possui um elemento mais à esquerda, mas nenhum elemento à direita.

  • O ponteiro de memória , que é um número inteiro não negativo que é um índice de um elemento na fita. Um ponteiro de memória mais alto refere-se a uma célula de fita mais à direita; um ponteiro de memória 0 refere-se ao elemento mais à esquerda. O ponteiro de memória é inicializado em 0.

  • O Hipercubo , que é uma "caixa" conceitual ∞- dimensional de células, cada uma das quais contém um bit inicializado como 0. A largura do Hipercubo é vinculada em todas as dimensões a apenas 2 células, mas a infinidade de dimensões significa o número de células. células é incontável .

Um índice no hipercubo é uma lista infinita de bits que se refere a uma célula no hipercubo (da mesma maneira que uma lista finita de bits pode ser usada para se referir a um hipercubo de dimensão finita). Como a fita é uma lista infinita de bits, a fita inteira sempre se refere a um elemento do Hypercube; esse elemento é chamado de referente .

2 Ω dá sentido a 7 caracteres diferentes:

  • < diminui o ponteiro da memória em 1. Decrementá-lo abaixo de 0 é um comportamento indefinido, portanto você não precisa lidar com isso.
  • > aumenta o ponteiro da memória em 1.
  • ! vira o bit no referente.
  • . gera o bit no referente.
  • ^substitui o bit na célula apontada pelo ponteiro de memória na fita pelo inverso do bit no referente.
  • [x]executa o código xcontanto que o bit no referente seja 1.

O desafio

Sua tarefa é escrever um programa que use uma string como entrada e execute essa entrada como um programa de 2 Ω .

Isso é , então a resposta mais curta e válida (medida em bytes) vence.

Notas

  • Você pode assumir que o programa consistirá apenas dos caracteres <>!.^[]e que []será aninhado corretamente.
  • Seu intérprete deve ser limitado apenas pela memória disponível no sistema. Ele deve ser capaz de executar os programas de amostra em um período de tempo razoável.

Programas de exemplo

Impressão 1:

!.

Impressão 010:

.!.!.

Imprimir 0 para sempre:

![!.!]

Imprima 0 para sempre ou 1 para sempre se !for anexado:

[.]![!.!]
Esolanging Fruit
fonte
2
Uma pequena observação: o número de células de armazenamento não é incontável, pois o número de 1s na fita é sempre finito. De fato, existe uma bijeção bastante simples entre os números naturais e os estados da fita (interpreta o conteúdo da fita como um número binário reverso), o que mostra que o Hypercube é basicamente uma matriz 1D infinita, acessada por bits de inversão em um valor de ponteiro inteiro , em vez de diminuir / diminuir como no cérebro.
Lynn
Além disso, re: seu convite para escrever um catprograma: não parece haver uma instrução para receber sugestões.
Lynn
2
Eu acho que deveria haver programas de amostra usando mais do conjunto de instruções. Dois simples: .- imprime um único zero e depois existe; !^!.- imprime uma única e sai. Mais seria bom embora. No momento em que é preciso entender apresentações, a fim de verificar-los (e, portanto, upvote-los!)
Jonathan Allan
@ Lynn A entrada seria dada com um 1 ou um 0 na célula [0,0,0,0,0,0,0...](ou seja, a presença de um !no início do programa).
precisa saber é o seguinte
Então você poderia fazer [.]![!.!]para imprimir o valor dessa célula para sempre
Leo

Respostas:

2

Python 2 , 167 bytes

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

Experimente online!

t é a fita. t = 6 significa que a fita é [0 1 1 0 0 0…]

m é 2 à potência do ponteiro da memória. Então m = 8 significa que estamos apontando para o bit 3 da fita.

h é o hipercubo. h = 80 (bits 4 e 6 configurados) significa que os bits em [0 0 1 0…] e [0 1 1 0…] estão configurados.

Para ler a parte no referente, verificamos 2 t & h . Para inverter, executamos h ^ = 2 t .

Traduzimos as instruções para o código Python e executamos o resultado. I armazena o nível de recuo dos laços tempo.

Lynn
fonte
Ou o seu programa ou o segundo caso de teste está errado
Wastl
@wastl O segundo caso de teste estava errado. ;)
DLosc 20/03/19
Alguns rearranjos, variáveis ​​extras para2**t (-6 bytes).
Erik the Outgolfer 21/03/19
2

JavaScript (Node.js) , 148 bytes

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

Experimente online!

Está completo

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

Precisa init como mover alguns lugares certos e iniciar o bit atual e certo do endereço como 1 ( >>>>>>>>^>^<)

Experimente online!

Place nin BoolFuck está escrito como (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Para >, faz 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

O mesmo de como <funciona

l4m2
fonte
Tem certeza de que esta tradução é válida? !>.impressões 1em boolfuck mas se traduz em !>^.que imprime 1 em TwoMega ( >não afeta a fita; ^não afeta a fita desde o referente é 1)
Esolanging Fruit
@EsolangingFruit +>;do [1]00... 1[0]0...(saída 0), !>^.do (0,0,...)=1, ptr=([0],0,...) (0,0,...)=1, ptr=(0,[0],...) (0,0,...)=1, ptr=(0,[1],...)(saída 0), o que há de errado?
L4m2 29/04/19
@EsolangingFruit for !>., only >é um comando válido no boolfuck ...
ASCII-only
11
@ l4m2 No TwoMega, !inverte o referente, não a célula de fita.
Esolanging Fruit
@EsolangingFruit então o que há de errado aqui?
L4m2
1

Clássico Brain-Flak , 816 bytes

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

Experimente online!

Este código foi escrito apenas para que eu tivesse um lugar para escrever uma prova da integridade de Turing.

Prova de perfeição de Turing

Mostramos uma redução de Boolfuck para TwoMega:

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

Esta tradução armazena o estado Boolfuck nas células de fita com número par no TwoMega. Todos os comandos traduzidos preservarão os seguintes invariantes:

  • O ponteiro de memória está em uma célula de número par.
  • Todas as células de fita com números ímpares são zero.
  • Para qualquer fita possível com todas as células de número ímpar zero, o valor correspondente no hipercubo é zero.

O trecho !^!será mantido [0]0constante e alternado entre 0[0]e [1]1(onde a atenção é limitada à linha do hipercubo acessível sem mover o ponteiro da memória). Como tal, é usado para colocar temporariamente o valor atual da fita no referente aos comandos Boolfuck que se preocupam com isso.

Se o TwoMega recebesse um comando de entrada ,com a semântica esperada, o comando Boolfuck ,seria convertido em >^<,!^>[!]!^<. Como ,não é necessário provar que o Boolfuck está completo com Turing, a falta de um comando de entrada não afeta essa prova.

Nitrodon
fonte
Ele armazena principalmente informações na posição no hipercubo em vez do próprio cubo?
L4m2
@ l4m2 Minha redução do BoolFuck não armazena nenhum dado no próprio cubo. Quaisquer 1s eu fizer no hipercubo estão lá apenas para as células de fita definido como 0.
Nitrodon
0

Python 3 , 297 284 274 bytes

-10 bytes graças a ovs e 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)

Experimente online!

fergusq
fonte
t.discard(p)->t-={p}
shooqie
@shooqie Isso não funciona, a menos que tseja global.
Fergusq
@fergusq Embora eu tenho certeza que ele funciona se você declarar fcomof(C,p,t=set())
shooqie
0

Pip , 75 71 bytes

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

Experimente online!

Traduz a 2 Ω código em código Pip equivalente e avalia.

Usamos ipara representar a fita, vpara o ponteiro da fita * e lpara o hipercubo. Os dois primeiros vêm pré-inicializados para valores úteis; lcomeça como [], para o qual pressionamos um 0( lPU0) para evitar problemas de indexação-lista-vazia.

* Na verdade, é a negação bit a bit do ponteiro da fita, porque estamos armazenando a fita para trás para facilitar a conversão em decimal.

O restante do código é:

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

A tabela de tradução:

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

l@FBié o referente: elemento do hipercubo lno índice (converter ide binário). Aparece frequentemente, por isso chamamos _e substituímos _pelo código real no final.

  • !:_ nega logicamente o referente no local.

  • --viPU0diminui v(movendo o ponteiro da fita para a direita); ele então empurra outro 0para o lado esquerdo i, para garantir que o ponteiro da fita permaneça dentro dos limites.

  • ++vincrementos v(sem necessidade de verificação de limites, por OP).

  • W_{executa um loop enquanto o referente é verdadeiro (ou seja, diferente de zero, ou seja 1).

  • } fecha o loop.

  • O_ gera o referente sem nova linha.

Finalmente, para ^:

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
DLosc
fonte