Este es el desafío semanal n. ° 2. Tema: Traducción
Escriba un programa o función que tome el código fuente de un programa en Prelude y genere código para un programa equivalente en Befunge-93 . Para que el programa sea equivalente, debe, para cualquier entrada dada, producir la misma salida que el programa Prelude, y detenerse si y solo si el programa Prelude se detiene.
Idioma de entrada: Preludio
Intérprete de Python:
Un programa Prelude consta de una serie de "voces" que ejecutan instrucciones simultáneamente. Las instrucciones para cada voz están en una línea separada. Cada voz tiene una pila separada, que se inicializa con una cantidad infinita de ceros. La ejecución comienza en la columna más a la izquierda y avanza una columna a la derecha en cada marca, excepto cuando está influenciado por )
o(
instrucciones. El programa finaliza cuando se alcanza la última columna.
Preludio de especificaciones para este desafío:
Digits 0-9 Push onto the stack a number from 0 to 9. Only single-digit
numeric literals can be used.
^ Push onto the stack the top value of the stack of the above
voice.
v Push onto the stack the top value of the stack of the below
voice.
# Remove the top value from the stack.
+ Pop the top two integers from the stack and push their sum.
- Pop the top two integers from the stack, subtract the topmost
from the second, and push the result.
( If the top of the stack is 0, jump to the column after the
matching `)` after the current column executes.
) If the top of the stack is not 0, jump to the column after
the matching `(` after the current column executes.
? Read an integer from STDIN.
! Pop one value from the stack and print it to STDOUT as an
integer.
<space> No-op
Notas
v
y^
actúe cíclicamente, de modo que lav
voz inferior copiará el elemento de pila de la voz superior y^
la voz superior copiará de la voz inferior. Corolario: Ambosv
y^
duplican la parte superior de la pila en un programa de una sola voz.- A
(
y su coincidencia)
pueden ubicarse en diferentes líneas. Sin embargo , a)
siempre mirará la pila de la voz donde(
se colocó la correspondiente , no la pila donde)
se coloca la propia. - Los valores producidos por las instrucciones
^
yv
operan sobre los valores presentes antes de completar cualquier otra operación en la misma columna. ?
y!
funcionan de manera diferente a la especificación que se encuentra en esolangs.org, así que asegúrese de probar con el intérprete ligeramente modificado que se proporciona en esta publicación.
Se garantiza que la entrada tiene:
- Paréntesis coincidentes
- No más de un paréntesis en una columna.
- El mismo número de caracteres en cada línea.
- Al menos una línea
- Ninguna columna con más de una instrucción de E / S (
!
o?
) - Un carácter de salto de línea después de las instrucciones para cada voz.
- No hay caracteres distintos a los mencionados anteriormente.
Idioma de salida: Befunge-93
Befunge es un lenguaje basado en pila cuyo contador de programa (PC; un puntero a la instrucción actual) se mueve libremente en una cuadrícula bidimensional. Comienza en la esquina superior izquierda, moviéndose hacia la derecha. El campo de juego es toroidal, es decir, el movimiento de la PC se envuelve alrededor de ambos bordes. Befunge también tiene una pila que se inicializa a un número infinito de ceros. Befunge tiene las siguientes operaciones:
Puede asumir las siguientes características del compilador / intérprete Befunge-93:
- Los enteros son de precisión ilimitada.
- Permite rejillas de cualquier tamaño.
- Las coordenadas de la cuadrícula (para
g
yp
) están basadas en 0.
Puntuación
Para evitar envíos que simplemente producen un intérprete de Prelude en Befunge y codifican la fuente de Prelude en él, el objetivo será minimizar el tamaño del código fuente de Befunge resultante.
A continuación se proporcionan una serie de programas Preludio. Su traductor se ejecutará en todos estos. Su puntaje es la suma de los tamaños de los programas Befunge, siempre que todos sean válidos.
Su traductor no debe optimizarse específicamente para estos casos de prueba (p. Ej., Codificando programas Befunge escritos a mano para ellos). Si sospecho alguna respuesta al respecto, me reservo el derecho de cambiar las entradas o crear otras adicionales.
Entradas de muestra
Imprimir n-1
abajo para 0
:
?(1-^!)
Lógico Y:
? (0)
?(0 )
1 !
O lógico:
? (0)
? (0)
1 1 !
Verifique la paridad de entrada (es decir, módulo 2) del número no negativo:
?(1-)
^ v
v1-^^-!
Cuadrar la entrada:
^
^+ !
?(1-)
Imprimir el n ésimo número de Fibonacci, donde n = 0
corresponde a 0 y n = 1
corresponde a 1:
0 v+v!
1 ^
?(1-)
Signum:
1) v # - !
vv (##^v^+)
?(# ^ ##
División para entradas no negativas:
1 (# 1) v # - 1+)
vv (##^v^+)
? v-(0 # ^ #
?
1+ 1-!
Por supuesto, su programa debe exhibir el mismo comportamiento para todos los casos, incluso si no se especifica el comportamiento del programa de muestra para números negativos.
Finalmente, su traductor no debe ser excesivamente largo:
- Debe estar contenido dentro de una publicación de Stack Exchange
- Debe procesar las entradas de muestra en menos de 10 minutos en una computadora de escritorio típica.
Tenga en cuenta que una entrada numérica para Prelude o Befunge se proporciona como un signo menos opcional seguido de uno o más dígitos decimales, seguido de una nueva línea. Otra entrada es el comportamiento indefinido.
Puede escribir su traductor en cualquier idioma. El código Befunge traducido más corto gana.
Tabla de clasificación
- Sp3000 : 16430 bytes
1
está dentro de un bucle, por lo que no puede ser empujado. Un 0 puede provenir de la cantidad infinita de 0 que comienzan en las pilas.Respuestas:
Python 3, marcará más tarde
Corre como
py -3 prefunge.py <input filename> <output filename>
.Ha sido una semana lenta para mí, así que finalmente me aburrí lo suficiente como para abordar esta pregunta de seis meses. Preguntaría por qué nadie más lo intentó, pero sigo sintiendo el dolor de la depuración (y probablemente todavía quedan errores por lo que sé).
La pregunta no proporciona un intérprete Befunge-93, así que utilicé este , que es ligeramente diferente de la especificación. Las dos diferencias clave son:
Si un carácter no existe en una fila determinada del programa, entonces no puede escribir en esa fila. Esto significa que deberá presionar Enter varias veces para introducir suficientes líneas nuevas al final . Si ve
NaN
s en la salida, esta es la causa más probable.Las celdas de la cuadrícula no se preinicializan a cero; por conveniencia, he incluido algo de preinicialización en las salidas de Befunge, pero como no es necesario, podría eliminarlo cuando empiece a marcar.
El diseño principal de los programas de salida es este:
El espacio de la pila está fuera del programa, de ahí el comentario de nueva línea Enter-spamming de antes.
La idea central es asignar a cada voz una fila que sirva como pila. Para mantener estas pilas, también tenemos una fila especial de longitud de pila donde la longitud de cada pila se registra en una celda a lo largo de la fila. El programa es entonces un montón de
g
ets yp
uts, por ejemplo, para imprimir el proceso es:y = stack_row[stack], x = stack_length[stack]
.91+,
, es decir, imprimir como entero y luego imprimir una nueva líneastack_length[stack]
Para realizar la evaluación simultánea de una columna, se leen todas las celdas necesarias y sus valores se mantienen en la pila antes de escribir cualquier celda (por ejemplo, para el ejemplo de impresión, puede haber más instrucciones entre el primer y el segundo paso).
`
, que es mayor que, se emplea para asegurarse de que las longitudes de la pila nunca sean negativas y para presionar 0s cuando la pila está vacía. De aquí proviene la ramificación claramente visible, pero tengo una idea que eliminará la ramificación, que debería eliminar una gran cantidad de espacio en blanco de la primera y tercera fila.Para los bucles, dado que los bucles Prelude pueden saltar en ambos sentidos, utilizamos dos filas por bucle en una configuración como esta:
Estos bucles actualmente constituyen la mayoría de los bytes, pero se pueden reducir fácilmente al colocarlos en el cuadro de código con
p
, lo que planeo hacer después de que estoy feliz de que el traductor esté funcionando correctamente.Aquí hay un ejemplo de salida para
?(1-^!)
, es decir, imprimirn-1
a0
:Cuadrado de la entrada:
División (se recomiendan entradas pequeñas):
También hay un montón de otras optimizaciones menores que me vienen a la mente, como reemplazar
07p07g
con:07p
, pero estoy dando este paso a la vez :)fuente
Will score later
2 años y contando! :)