Compacta un programa Befunge

17

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 py 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.

Caracol mecánico
fuente
8
¿Qué debe evitar ejecutar el programa hasta su finalización y escribir un programa Befunge que imprima la misma salida?
Keith Randall el
55
¿Se permiten "obtener" y "poner"? Si permite "poner" (código auto modificable), será difícil hacer algo.
Keith Randall el
2
¿De dónde comienza la ejecución? ¿Esquina superior izquierda? Si es así, ¿puede explicar la salida del segundo ejemplo? .significa entero de salida, pero si comienza desde la parte superior izquierda, entonces no hay un entero en la pila para la salida.
elssar
1
@elssar sí, .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ía 000.
daniero
@KeithRandall: escribir un nuevo programa con la misma salida solo funciona para programas con una salida corta. gy pno están permitidos (lo siento, se olvidó de ellos; editado).
Caracol mecánico el

Respuestas:

12

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:

92+9*                           :. v  <
>v"bottles of beer on the wall"+910<
,:
^_ $                             :.v
            >v"bottles of beer"+910<
            ,:
            ^_ $                     v
>v"Take one down, pass it around"+910<
,:
^_ $                           1-v
                                 :
        >v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    >v" no more beer..."+910<
                    ,:
                    ^_ $$ @

Genera el siguiente resultado:

92+9*:.019+"llaw eht no "v
v  _v# :"bottles of beer"<
>    ,:    v
^  _v#     <
    >$:.019+"reeb f"v
 v _  v#:"bottles o"<
 >     ,:  v
 ^ _  v#   <
      >$019+"dnuo"v
     v"pass it ar"<
     >" ,nwod eno"v
 v _    v#:"Take "<
 >       ,:v
 ^ _    v# <
        >$1-:v
 v _      v# <
 >         :.019+"reeb "v
  v_  v#   :"bottles of"<
  >        ,v
  ^_  v#   :<
      >    $019+"llaw"v
           v" on the "<
           >"reeb fo "v
^  _^#      :"bottles"<
          >019+"...r"v
v  _v#:" no more bee"<
>    ,:    v
^  _v#     <
    >$$@    

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í:

"output">:#,_@

No he hecho nada para optimizar los bloques básicos, solo el diseño. Que hacer.

Entonces, ¿dónde están las pruebas?

Keith Randall
fuente
1
el enlace del código fuente parece ser 500 en este momento. ¿Configuración incorrecta del servidor?
John Dvorak
1
@ JanDvorak: de hecho. Fijo.
Keith Randall el
1

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.

/^$/d

Simplemente elimina las líneas en blanco.

daniero
fuente
10
¡Tu código no es correcto! No puede simplemente eliminar líneas en blanco. No puedo escribir un código 2D en el comentario. Pero considere un caso en el que la dirección es hacia abajo, y se inicia una cadena constante ( "). 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!
saeedn
3
Mire el código en ideone.com/BdcRcf Debería imprimirse b a. Pero después de su reducción, se imprimirá ba.
saeedn