Befunge es un lenguaje de programación esotérico bidimensional. La idea básica es que los comandos (de un carácter) se colocan en una cuadrícula bidimensional. El flujo de control atraviesa la cuadrícula, ejecuta comandos sobre los que pasa y cambia de dirección cuando golpea una flecha ( >^<v
). Los comandos están basados en pila; ver esta lista . Ver también http://esolangs.org/wiki/Befunge .
La especificación para Befunge-98 está disponible.
Problema
Escriba un programa que transforme un programa Befunge en una representación más compacta. Por ejemplo, se imprime el siguiente programa 0
:
> 0 v
> @ .
^ <
En este caso, se podría compactar sin cambiar el comportamiento del programa eliminando filas de espacios, para dar
>0v
>@.
^ <
Las transformaciones más sofisticadas podrían rotar o reflejar secuencias de comandos y eliminar comandos innecesarios de control de flujo para compactar el programa. Por ejemplo, con este programa:
>12345v
6
v....7<
.
.
.
@
puede meter el final del programa en el agujero:
>12345v
>...@ 6
^....7<
Para el primer ejemplo, el programa más compacto posible es
>0.@
Puede usar cualquier transformación siempre que el programa de salida dé el mismo resultado.
Programas de entrada
Los programas de entrada son programas válidos de Befunge-98.
Puede suponer que el programa de entrada es determinista. Es decir, no utiliza comandos que leen el estado externo: los comandos de entrada del usuario &
y ~
, el aleatorizador ?
, y los comandos de código auto modificables p
y g
.
Puede suponer que el programa de entrada finaliza.
Puntuación
Este no es un código de golf, sino un problema para escribir un programa que realiza código de golf.
La entrada es un conjunto de casos de prueba (programas Befunge que satisfacen las restricciones de entrada anteriores). La puntuación total es la suma de las puntuaciones para los casos de prueba.
Puntuación para cada caso de prueba
El puntaje es el área del casco convexo de las celdas no vacías en el programa de salida, donde cada celda se trata como un cuadrado cuyas cuatro esquinas son puntos reticulares en el plano cartesiano. Por ejemplo, un programa de
> v
@ <
obtiene un puntaje de 9.5.
Si su programa no finaliza en un tiempo y memoria razonables en una entrada en particular, la puntuación es la del programa de entrada. (Esto se debe a que podría agregar trivialmente un contenedor de limitación de tiempo que haga que el programa de entrada no cambie si su programa no termina a tiempo).
Si el programa de caso de prueba tiene un resultado diferente (o no termina) después de procesarlo con su programa, el puntaje es el puntaje del programa de entrada más una penalización de 100 puntos.
fuente
.
significa entero de salida, pero si comienza desde la parte superior izquierda, entonces no hay un entero en la pila para la salida..
genera un número entero. Pero también, cuando no hay suficientes parámetros en la pila, befunge finge que hay una cantidad suficiente de ceros allí. Entonces el segundo ejemplo saldría000
.g
yp
no están permitidos (lo siento, se olvidó de ellos; editado).Respuestas:
Pasé un largo viaje en avión codificando este. He escrito un compilador pseudo befunge que ejecuta el programa befunge, extrae bloques básicos y los presenta en una representación compacta.
Enlace al programa .
Cuando se ejecuta en este programa de 99 botellas:
Genera el siguiente resultado:
En realidad, no es mucho más compacto que la fuente, pero probablemente funcionará mejor en programas más grandes / dispersos.
El programa se presenta con un área de enrutamiento a la izquierda y el contenido del bloque básico a la derecha. Un bloque básico generalmente se presenta en un número par de filas para que la entrada y la salida se unan al área de enrutamiento. Al final de cada bloque básico, el gadget
#^_v
y las variantes, distribuidas de derecha a izquierda, hacen la rama condicional y el flujo de ruta en columnas. Al comienzo de cada bloque básico, estas columnas se enrutan en las filas para el bloque básico de destino.Además, si la salida es corta, solo genera la salida explícitamente, así:
No he hecho nada para optimizar los bloques básicos, solo el diseño. Que hacer.
Entonces, ¿dónde están las pruebas?
fuente
Sed, 5 caracteres
Entonces, incluso si esto no es codegolf, aquí hay una solución que tendrá una relación de longitud de código a puntaje bastante buena, pero no necesariamente una buena puntuación.
Simplemente elimina las líneas en blanco.
fuente
"
). Cada línea en blanco en el camino debe tratarse como un carácter de espacio. Si imprimimos esa cadena, ¡el código que generó no tiene esos espacios en la salida!b a
. Pero después de su reducción, se imprimirába
.