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ódigox
contanto 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 é código-golfe , 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:
[.]![!.!]
fonte
1
s 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.cat
programa: não parece haver uma instrução para receber sugestões..
- 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!)[0,0,0,0,0,0,0...]
(ou seja, a presença de um!
no início do programa).[.]![!.!]
para imprimir o valor dessa célula para sempreRespostas:
Python 2 , 167 bytes
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.
fonte
2**t
(-6 bytes).JavaScript (Node.js) , 148 bytes
Experimente online!
Está completo
Precisa init como mover alguns lugares certos e iniciar o bit atual e certo do endereço como 1 (
>>>>>>>>^>^<
)Experimente online!
Place
n
in BoolFuck está escrito como(0, 0, ..., 0(n*0), [1], 1, 0, 0, ...)
.Para
>
, fazn
=>n+1
O mesmo de como
<
funcionafonte
!>.
impressões1
em boolfuck mas se traduz em!>^.
que imprime 1 em TwoMega (>
não afeta a fita;^
não afeta a fita desde o referente é 1)+>;
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?!>.
, only>
é um comando válido no boolfuck ...!
inverte o referente, não a célula de fita.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:
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 trecho
!^!
será mantido[0]0
constante e alternado entre0[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.fonte
Python 3 ,
297284274 bytes-10 bytes graças a ovs e Jonathan Allan
Experimente online!
fonte
t.discard(p)
->t-={p}
t
sejaglobal
.f
comof(C,p,t=set())
Pip ,
7571 bytesExperimente online!
Traduz a 2 Ω código em código Pip equivalente e avalia.
Usamos
i
para representar a fita,v
para o ponteiro da fita * el
para o hipercubo. Os dois primeiros vêm pré-inicializados para valores úteis;l
começa como[]
, para o qual pressionamos um0
(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 é:
A tabela de tradução:
l@FBi
é o referente: elemento do hipercubol
no índice (converteri
de binário). Aparece frequentemente, por isso chamamos_
e substituímos_
pelo código real no final.!:_
nega logicamente o referente no local.--viPU0
diminuiv
(movendo o ponteiro da fita para a direita); ele então empurra outro0
para o lado esquerdoi
, para garantir que o ponteiro da fita permaneça dentro dos limites.++v
incrementosv
(sem necessidade de verificação de limites, por OP).W_{
executa um loop enquanto o referente é verdadeiro (ou seja, diferente de zero, ou seja1
).}
fecha o loop.O_
gera o referente sem nova linha.Finalmente, para
^
:fonte