É um acidente engraçado que este mundo tenha apenas uma dimensão de tempo, mas não precisa ser assim. É fácil imaginar mundos com 2 ou mais dimensões de tempo e, nesses mundos, você pode construir computadores e executar software neles, exatamente como neste.
O sistema
Aqui está um sistema para executar programas Brainf * ck em duas dimensões de tempo:
As duas dimensões de tempo são x e y. Cada programa Brainf * ck consiste em um meio programa x e um meio programa, por exemplo, um programa pode ser
x: +>+
y: [-]
Os dois semi-programas têm, cada um, seu próprio ponteiro de programa, mas compartilham um único ponteiro de fita (ou seja, ambos operam na mesma célula da fita).
O tempo é bidimensional, portanto, consiste em uma grade de momentos:
Movendo-se pela dimensão x, o meio programa x executa uma etapa do tempo. Movendo-se ao longo da dimensão y, o meio programa y executa uma etapa do tempo.
Então, por exemplo, digamos que a fita comece como [0] 0 0( []representa o ponteiro da fita) e os programas x / y são +e ->-. A execução deste programa ficaria assim:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Observe que, à medida que o tempo avança na direção y, o semi-programa x continua fazendo a mesma coisa repetidamente, porque seu tempo não progride.
A fita a cada momento inclui o efeito cumulativo de todas as ações que a alimentam (cada ação conta uma vez). Portanto, por exemplo, a fita no momento (2, 1) contém o efeito cumulativo de:
- a ação x de (0, 0)
- a ação x de (1, 0)
- a ação x de (0, 1)
- a ação x de (1, 1)
- a ação y de (0, 0)
- a ação y de (1, 0)
- a ação y de (2, 0)
Meios cumulativos:
- Todos os incrementos e decréscimos para uma célula somam-se.
- Todos os movimentos esquerdo (-1) e direito (+1) no ponteiro da fita somam-se.
Os ponteiros de instruções não se acumulam. Cada meio programa obtém seu ponteiro de instruções do momento anterior em sua dimensão. Ou seja, x ponteiros de programa progridem apenas na dimensão x ey ponteiros de programa progridem apenas na dimensão y. Assim, por exemplo, no programa ( [], +) a partir de [0] 0 0, a execução seria
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Mais alguns momentos da simulação acima ( +, ->-) são:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Os operadores Brainf * ck permitidos são os seguintes (eles têm seu significado padrão):
+,-: incremento, decremento;[,]: loop até zero (processando um[ou]leva um tempo, como no padrão Brainf * ck);<,>: mova para a esquerda / direita na fita.
Exemplo complexo
Para o programa ( >, +) começando com [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Para ( +, -) começando com [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Observe que a fita termina como se [0] 0 0fosse uma +e -acontece duas vezes, somando 0.
Para o programa ( >+, [-]) começando com [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Diagrama com setas
O diagrama abaixo mostra como calcular as ações e a fita:
The Puzzle
Escreva um programa 2D Brainf * ck (com um meio programa x e um meio programa) para executar em uma fita de três células, que atenda às duas condições a seguir:
- Se a fita começa como
[0] 0 0, no momento (5, 5), há uma0na célula zeroth. - Se a fita começa como
[1] 0 0, no momento (5, 5), há uma0na célula zeroth.
O programa mais curto que atende aos requisitos vence.
+e>? Se for1 1 [0](muito louco, mas é o que as especificações parecem sugerir), como os ponteiros de instruções se combinam? Se os dois threads forem+e[], então, na1 2fita de dados seria[3], mas será o segundo ponteiro de instrução dentro do loop ([]+caminho), ou fora ([+]caminho) ou mesmo ilegal (+[])?+,>) para ver se obtive o mesmo resultado que você.(1,1)através de um(1,0)ou de outro(0,1), mas se um programa começa>e outro começa+, certamente a ordem relativa deles é importante?Respostas:
Total de 4 bytes: (
[-],>)I escreveu um bruto-forcer para encontrar o menor tal programa.
Aqui estão os diagramas deste programa em ação. Essas grades são organizadas de maneira semelhante à grade na especificação, com (0,0) o canto inferior esquerdo, tempo x ao longo do eixo xe tempo y ao longo do eixo y. O canto superior direito contém o resultado.
Primeiro, com uma fita de
0 0 0:Agora com uma fita de
1 0 0:Havia algumas coisas que não estavam claramente explicadas nas especificações, como o fato de que a fita de 3 células se enrola.
Como um bônus, aqui está a visualização do exemplo (
>+,[-]):E um dos exemplos (
>+,+>):Observe que o canto superior direito é diferente do que você listou, acho que isso é um erro no seu exemplo porque meu código corresponde a todos os outros exemplos que tentei.
fonte