Es un accidente gracioso que este mundo tenga solo 1 dimensión de tiempo, pero no tiene que ser así. Es fácil imaginar mundos con 2 o más dimensiones de tiempo, y en esos mundos puedes construir computadoras y ejecutar software en ellas, como en este caso.
El sistema
Aquí hay un sistema para ejecutar programas Brainf * ck en dos dimensiones de tiempo:
Las dos dimensiones de tiempo son x e y. Cada programa Brainf * ck consta de un x medio programa y un medio programa, por ejemplo, un programa
x: +>+
y: [-]
Los dos medios programas tienen cada uno su propio puntero de programa, pero comparten un solo puntero de cinta (es decir, ambos operan en la misma celda de la cinta).
El tiempo es bidimensional, por lo que consiste en una cuadrícula de momentos:
Moviéndose a lo largo de la dimensión x, el medio programa x ejecuta un paso de tiempo. Moviéndose a lo largo de la dimensión y, el medio programa y ejecuta un paso de tiempo.
Entonces, por ejemplo, digamos que la cinta comienza como [0] 0 0( []representa el puntero de la cinta) y los programas x / y son +y ->-. La ejecución de este programa se vería así:
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, a medida que el tiempo se mueve en la dirección y, el medio programa x sigue haciendo lo mismo una y otra vez, porque su tiempo no progresa.
La cinta en cada momento incluye el efecto acumulativo de todas las acciones que lo alimentan (cada acción cuenta una vez). Entonces, por ejemplo, la cinta en el momento (2, 1) contiene el efecto acumulativo de:
- la acción x de (0, 0)
- la acción x de (1, 0)
- la acción x de (0, 1)
- la acción x de (1, 1)
- la acción y de (0, 0)
- la acción y de (1, 0)
- la acción y de (2, 0)
Acumulativo significa:
- Todos los incrementos y decrementos de una celda suman.
- Todos los movimientos a la izquierda (-1) y a la derecha (+1) al puntero de la cinta se suman.
Los punteros de instrucciones no se acumulan. Cada medio programa obtiene su puntero de instrucción del momento anterior en su dimensión. Es decir, los punteros de programa x progresan solo en la dimensión xy los punteros de programa y solo progresan en la dimensión y. Entonces, por ejemplo, en el programa ( [], +) a partir de [0] 0 0, la ejecución sería
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
Algunos momentos más de la simulación anterior ( +, ->-) son:
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
Los operadores Brainf * ck permitidos son los siguientes (tienen su significado estándar):
+,-: incremento, decremento;[,]: Bucle hasta cero (el procesamiento de una[o]realiza una vez a paso, como en la norma Brainf * ck);<,>: mover hacia la izquierda / derecha en la cinta.
Ejemplo complejo
Para el programa ( >, +) que comienza con [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 ( +, -) comenzando con [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
Tenga en cuenta que la cinta termina como [0] 0 0porque cada +y -pasa dos veces, sumando a 0.
Para el programa ( >+, [-]) que comienza con [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 con flechas
El siguiente diagrama muestra cómo calcular las acciones y la cinta:
El rompecabezas
Escriba un programa 2D Brainf * ck (con un x medio programa y un medio programa ay) para ejecutar en una cinta de 3 celdas, que cumpla las dos condiciones siguientes:
- Si la cinta comienza como
[0] 0 0, en el momento (5, 5) tiene una0en la celda cero. - Si la cinta comienza como
[1] 0 0, en el momento (5, 5) tiene una0en la celda cero.
El programa más corto que cumpla los requisitos gana.
+y>? Si es1 1 [0](bastante loco, pero es lo que parece sugerir la especificación), ¿cómo se combinan los punteros de instrucción? Si los dos subprocesos son+y[], entonces, en1 2la cinta de datos sería[3], pero ¿está el segundo puntero de instrucción dentro del bucle ([]+ruta) o fuera ([+]ruta) o incluso ilegal (+[])?+,>) para ver si obtengo el mismo resultado que tú.(1,1)través de cualquiera(1,0)o(0,1), pero uno programa se inicia con>y se empieza con+, entonces seguramente sus asuntos orden relativo?Respuestas:
4 bytes en total: (
[-],>)Yo escribí un bruto forzador para encontrar el más pequeño de estos programas.
Aquí están los diagramas de este programa en acción. Estas cuadrículas están dispuestas de manera similar a la cuadrícula en la especificación, con (0,0) la esquina inferior izquierda, el tiempo x a lo largo del eje xy el tiempo y a lo largo del eje y. La esquina superior derecha contiene el resultado.
Primero, con una cinta de
0 0 0:Ahora con una cinta de
1 0 0:Hubo un par de cosas que no se explicaron claramente en la especificación, como el hecho de que la cinta de 3 celdas se envuelve.
Como beneficio adicional, aquí está la visualización del ejemplo (
>+,[-]):Y uno de los (
>+,+>) ejemplo:Tenga en cuenta que la esquina superior derecha es diferente de lo que ha enumerado, creo que este es un error en su ejemplo porque mi código coincide con todos los demás ejemplos que he probado.
fuente