Traducir Preludio a Befunge

19

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

  • vy ^actúe cíclicamente, de modo que la vvoz inferior copiará el elemento de pila de la voz superior y ^la voz superior copiará de la voz inferior. Corolario: Ambos vy ^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 ^y voperan 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 gy p) 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-1abajo 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 = 0corresponde a 0 y n = 1corresponde 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
Feersum
fuente
No entiendo: "Empuje en la pila el valor más alto en la pila de la voz anterior". No tiene que ser: "Empuje sobre la pila el valor más alto de la pila de la voz anterior".
Def
Dice que el preludio ejecuta voces simultáneamente, eso significa que realmente se ejecutan en un hilo separado o puedo simplemente ejecutar los primeros comandos en todas las voces (de arriba a abajo), luego los segundos comandos y así sucesivamente.
Def
@Deformyer Lo cambié de "on" a "of", pero pensé que el "valor superior en la pila" tampoco estaba mal. En cuanto a la simultaneidad, no, no es necesario interpretarlos en paralelo. Lo importante es que todos actúan sobre el estado anterior de las pilas, y ninguna operación en una columna determinada puede afectar a ninguna otra operación en esa columna.
Martin Ender
¿No violan varios de los casos de prueba "No hay columna con más de una instrucción de E / S (! O?)?"
Fuwjax
@proudhaskeller El 1está 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.
feersum

Respuestas:

10

Python 3, marcará más tarde

from collections import defaultdict
from functools import lru_cache
import sys

NUMERIC_OUTPUT = True

@lru_cache(maxsize=1024)
def to_befunge_num(n):
    # Convert number to Befunge number, using base 9 encoding (non-optimal,
    # but something simple is good for now)

    assert isinstance(n, int) and n >= 0

    if n == 0:
        return "0"

    digits = []

    while n:
        digits.append(n%9)
        n //= 9

    output = [str(digits.pop())]

    while digits:
        output.append("9*")
        d = digits.pop()

        if d:
            output.append(str(d))
            output.append("+")

    output = "".join(output)

    if output.startswith("19*"):
        return "9" + output[3:]

    return output

def translate(program_str):
    if program_str.count("(") != program_str.count(")"):
        exit("Error: number of opening and closing parentheses do not match")

    program = program_str.splitlines()
    row_len = max(len(row) for row in program)
    program = [row.ljust(row_len) for row in program]
    num_stacks = len(program)


    loop_offset = 3
    stack_len_offset = program_str.count("(")*2 + loop_offset
    stack_offset = stack_len_offset + 1
    output = [[1, ["v"]], [1, [">"]]] # (len, [strings]) for each row
    max_len = 1 # Maximum row length so far

    HEADER_ROW = 0
    MAIN_ROW = 1
    FOOTER_ROW = 2
    # Then stack lengths, then loop rows, then stacks

    # Match closing parens with opening parens
    loop_map = {} # {column: (loop num, stack number to check, is_start)}
    loop_stack = []
    loop_num = 0

    for col in range(row_len):
        col_str = "".join(program[stack][col] for stack in range(num_stacks))

        if col_str.count("(") + col_str.count(")") >= 2:
            exit("Error: more than one parenthesis in a column")

        if "(" in col_str:
            stack_num = col_str.index("(")

            loop_map[col] = (loop_num, stack_num, True)
            loop_stack.append((loop_num, stack_num, False))
            loop_num += 1

        elif ")" in col_str:
            if loop_stack:
                loop_map[col] = loop_stack.pop()

            else:
                exit("Error: mismatched parentheses")


    def pad_max(row):
        nonlocal max_len, output

        while len(output) - 1 < row:
            output.append([0, []])

        if output[row][0] < max_len:
            output[row][1].append(" "*(max_len - output[row][0]))
            output[row][0] = max_len


    def write(string, row):
        nonlocal max_len, output

        output[row][1].append(string)
        output[row][0] += len(string)

        max_len = max(output[row][0], max_len)


    def stack_len(stack, put=False):
        return (to_befunge_num(stack) + # x
                str(stack_len_offset) + # y
                "gp"[put])


    def get(stack, offset=0):
        assert offset in [0, 1] # 1 needed for 2-arity ops

        # Check stack length
        write(stack_len(stack) + "1-"*(offset == 1) + ":0`", MAIN_ROW)

        pad_max(HEADER_ROW)
        pad_max(MAIN_ROW)
        pad_max(FOOTER_ROW)

        write(">" + to_befunge_num(stack + stack_offset) + "g", HEADER_ROW)
        write("|", MAIN_ROW)
        write(">$0", FOOTER_ROW)

        pad_max(HEADER_ROW)
        pad_max(MAIN_ROW)
        pad_max(FOOTER_ROW)

        write("v", HEADER_ROW)
        write(">", MAIN_ROW)
        write("^", FOOTER_ROW)


    def put(stack, value=""):
        put_inst = (value +
                    stack_len(stack) +
                    to_befunge_num(stack + stack_offset) +
                    "p")

        post_insts.append(put_inst)


    def pop(stack):
        put(stack, "0")


    def inc_stack_len(stack):
        post_insts.append(stack_len(stack) + "1+")
        post_insts.append(stack_len(stack, put=True))


    def dec_stack_len(stack):
        post_insts.append(stack_len(stack) + ":0`-") # Ensure nonnegativity
        post_insts.append(stack_len(stack, put=True))


    # Technically not necessary to initialise stack lengths per spec, but it makes it
    # more portable and easier to test against other Befunge interpreters

    for stack in range(num_stacks):
        write("0" + stack_len(stack, put=True), MAIN_ROW)

    for col in range(row_len):
        post_insts_all = []

        loop_start = False
        loop_end = False

        if col in loop_map:
            if loop_map[col][2]:
                loop_start = True
            else:
                loop_end = True

        if loop_start:
            loop_row = loop_offset + 2*loop_map[col][0]
            get(loop_map[col][1])

        elif loop_end:
            get(loop_map[col][1])
            write("!", MAIN_ROW)


        for stack in range(num_stacks-1, -1, -1):
            char = program[stack][col]
            post_insts = [] # Executed after the gets in reverse order, i.e. last added first

            if char in " ()":
                continue

            # Pre-inc, post-dec
            elif char.isdigit():
                inc_stack_len(stack)
                put(stack, char)

            elif char == "?":
                inc_stack_len(stack)
                put(stack, "&")

            elif char == "!":
                get(stack)
                post_insts.append(".91+," if NUMERIC_OUTPUT else ",")
                pop(stack)
                dec_stack_len(stack)

            elif char == "#":
                pop(stack)
                dec_stack_len(stack)

            elif char in "+-":
                get(stack, 1)
                get(stack)
                post_insts.append(char)
                pop(stack) # This one first in case of ! or 1!
                post_insts.append(stack_len(stack) + ":1`-:1\\`+") # Ensure >= 1
                post_insts.append(stack_len(stack, put=True))
                put(stack)                

            elif char in "^v":
                offset = -1 if char == "^" else 1

                get((stack + offset) % num_stacks)
                inc_stack_len(stack)
                put(stack)

            else:
                exit("Error: invalid character " + char)

            post_insts_all.append(post_insts)


        while post_insts_all:
            write("".join(post_insts_all.pop()), MAIN_ROW)

        if loop_start or loop_end:
            loop_row = loop_offset + 2*loop_map[col][0]

            pad_max(HEADER_ROW)
            pad_max(MAIN_ROW)
            pad_max(loop_row)
            pad_max(loop_row + 1)

            write(">v", HEADER_ROW)
            write("|>", MAIN_ROW)

            if loop_start:
                write(" ^", loop_row)
                write(">", loop_row + 1)

            else:
                write("<", loop_row)
                write(" ^", loop_row + 1)


    write("@", MAIN_ROW)
    return "\n".join("".join(row) for row_len, row in output)

if __name__ == '__main__':
    if len(sys.argv) < 3:
        exit("Usage: py -3 prefunge.py <input filename> <output filename>")

    with open(sys.argv[1]) as infile:
        with open(sys.argv[2], "w") as outfile:
            outfile.write(translate(infile.read()))

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

v [header row]
> [main row]
  [footer row]
  ---
   |
   | rows for loops (2 per loop)
   |
  ---
  [stack length row]
  ---
   |
   | rows for stack space (1 per voice)
   |
  ---

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 gets y puts, por ejemplo, para imprimir el proceso es:

  • Consigue la celda en y = stack_row[stack], x = stack_length[stack]
  • Realizar .91+,, es decir, imprimir como entero y luego imprimir una nueva línea
  • Reemplace la celda en los coords anteriores con 0 (para simular popping)
  • Decremento stack_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:

       >v                     >v
(cond) |>  (program)  (cond) !|>

        ^                     <
       >                       ^

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, imprimir n-1a 0:

v                        >6gv>v                      >6gv      >6gv                                 >6gv                   >6gv                           >6gv >v
>005p05g1+05p&05g6p05g:0`|  >|>05g1+05p105g6p05g1-:0`|  >05g:0`|  >-005g6p05g:1`-:1\`+05p05g6p05g:0`|  >05g1+05p05g6p05g:0`|  >.91+,005g6p05g:0`-05p05g:0`|  >!|>@
                         >$0^                        >$0^      >$0^                                 >$0^                   >$0^                           >$0^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Cuadrado de la entrada:

v                                >8gv      >8gv             >v      >6gv                                   >8gv      >8gv        >7gv      >7gv                                                            >8gv >v      >7gv
>005p015p025p25g1+25p&25g8p25g:0`|  >25g:0`|  >05g1+05p05g6p|>05g:0`|  >15g1+15p15g7p25g1+25p125g8p25g1-:0`|  >25g:0`|  >15g1-:0`|  >15g:0`|  >+015g7p15g:1`-:1\`+15p15g7p-025g8p25g:1`-:1\`+25p25g8p25g:0`|  >!|>15g:0`|  >.91+,015g7p15g:0`-15p@
                                 >$0^      >$0^                     >$0^                                   >$0^      >$0^        >$0^      >$0^                                                            >$0^         >$0^
                                                             ^                                                                                                                                                  <
                                                            >                                                                                                                                                    ^

División (se recomiendan entradas pequeñas):

v                                                                          >91+gv>v      >94+gv                                                         >95+gv      >95+gv        >93+gv      >93+gv                                                                    >93+gv      >93+gv               >v      >93+gv                                                     >93+gv >v      >92+gv                  >v      >92+gv                                       >92+gv                                       >91+gv                                       >93+gv                     >91+gv                       >92+gv      >92+gv        >91+gv      >91+gv                                                                                      >92+gv >v                        >91+gv      >91+gv                                     >91+gv >v                        >95+gv      >95+gv                                     >95+gv
>009p019p029p039p049p09g1+09p109g91+p29g1+29p&29g93+p39g1+39p&39g94+p09g:0`|    >|>39g:0`|    >009g91+p09g:0`-09p29g1+29p29g93+p49g1+49p149g95+p49g1-:0`|    >49g:0`|    >29g1-:0`|    >29g:0`|    >-029g93+p29g:1`-:1\`+29p29g93+p+049g95+p49g:1`-:1\`+49p49g95+p29g:0`|    >29g:0`|    >19g1+19p19g92+p|>29g:0`|    >09g1+09p109g91+p19g1+19p19g92+p29g1+29p029g93+p29g:0`|    >!|>19g:0`|    >029g93+p29g:0`-29p|>19g:0`|    >09g1+09p09g91+p019g92+p19g:0`-19p19g:0`|    >019g92+p19g:0`-19p29g1+29p29g93+p09g:0`|    >009g91+p09g:0`-09p19g1+19p19g92+p29g:0`|    >19g1+19p19g92+p09g:0`|    >19g1+19p19g92+p19g1-:0`|    >19g:0`|    >09g1-:0`|    >09g:0`|    >-009g91+p09g:1`-:1\`+09p09g91+p+019g92+p19g:1`-:1\`+19p19g92+p029g93+p29g:0`-29p19g:0`|    >!|>09g1+09p109g91+p09g1-:0`|    >09g:0`|    >+009g91+p09g:1`-:1\`+09p09g91+p09g:0`|    >!|>49g1+49p149g95+p49g1-:0`|    >49g:0`|    >-049g95+p49g:1`-:1\`+49p49g95+p49g:0`|    >.91+,049g95+p49g:0`-49p@
                                                                           >$0  ^        >$0  ^                                                         >$0  ^      >$0  ^        >$0  ^      >$0  ^                                                                    >$0  ^      >$0  ^                       >$0  ^                                                     >$0  ^         >$0  ^                          >$0  ^                                       >$0  ^                                       >$0  ^                                       >$0  ^                     >$0  ^                       >$0  ^      >$0  ^        >$0  ^      >$0  ^                                                                                      >$0  ^                           >$0  ^      >$0  ^                                     >$0  ^                           >$0  ^      >$0  ^                                     >$0  ^
                                                                                  ^                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        <
                                                                                 >                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ^
                                                                                                                                                                                                                                                                                                          ^                                                                        <
                                                                                                                                                                                                                                                                                                         >                                                                          ^
                                                                                                                                                                                                                                                                                                                                                                                                                    ^                                                                                                                                                                                                                                                                                                                                              <
                                                                                                                                                                                                                                                                                                                                                                                                                   >                                                                                                                                                                                                                                                                                                                                                ^

También hay un montón de otras optimizaciones menores que me vienen a la mente, como reemplazar 07p07gcon :07p, pero estoy dando este paso a la vez :)

Sp3000
fuente
Entonces. Mucho. Gratis. Hora.
Optimizador
1
Will score later2 años y contando! :)
HyperNeutrino