Traduzir Prelude para Befunge

19

Este é o Desafio Semanal # 2. Tema: Tradução

Escreva um programa ou função que receba o código fonte de um programa no Prelude e envie o código para um programa equivalente no Befunge-93 . Para que o programa seja equivalente, ele deve, para qualquer entrada fornecida, produzir a mesma saída que o programa Prelude e interromper se e somente se o programa Prelude parar.

Idioma de entrada: Prelude

Intérprete Python:

Um programa Prelude consiste em várias "vozes" que executam instruções simultaneamente. As instruções para cada voz estão em uma linha separada. Cada voz tem uma pilha separada, que é inicializada com uma quantidade infinita de zeros. A execução começa na coluna mais à esquerda e avança uma coluna para a direita a cada tick, exceto quando influenciada por )ou (instruções. O programa termina quando a última coluna é atingida.

Prelude especificações para este desafio:

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

  • ve ^aja de forma cíclica, para que a vvoz na parte inferior copie o elemento de pilha da voz superior e ^na voz superior copie da voz inferior. Corolário: Ambos ve ^duplicar o topo da pilha em um programa de voz única.
  • A (e sua correspondência )podem estar localizadas em linhas diferentes. No entanto , a )sempre observará a pilha da voz em que o correspondente (foi colocado, e não a pilha em que o )próprio é colocado.
  • Os valores produzidos pelas instruções ^e voperam com os valores presentes antes da conclusão de quaisquer outras operações na mesma coluna.
  • ?e !opere de maneira diferente da especificação encontrada em esolangs.org, portanto, teste com o intérprete levemente modificado fornecido nesta publicação.

A entrada é garantida para ter:

  • Parênteses correspondentes
  • Não há mais de um parêntese em uma coluna
  • Mesmo número de caracteres em cada linha
  • Pelo menos uma linha
  • Nenhuma coluna com mais de uma instrução de E / S ( !ou ?)
  • Um caractere de avanço de linha após as instruções para cada voz
  • Nenhum caractere além dos mencionados acima

Idioma de saída: Befunge-93

Befunge é uma linguagem baseada em pilha cujo contador de programa (PC; um ponteiro para a instrução atual) se move livremente em uma grade bidimensional. Começa no canto superior esquerdo, movendo-se para a direita. O campo de jogo é toroidal, ou seja, o movimento do PC envolve as duas extremidades. O Befunge também possui uma pilha que é inicializada com um número infinito de zeros. Befunge tem as seguintes operações:

Você pode assumir as seguintes características do compilador / intérprete Befunge-93:

  • Os números inteiros são de precisão ilimitada.
  • Permite grades de qualquer tamanho.
  • As coordenadas da grade (para ge p) são baseadas em 0.

Pontuação

Para impedir envios que simplesmente produzam um intérprete do Prelude no Befunge e codifiquem a fonte do Prelude nele, o objetivo será minimizar o tamanho do código-fonte do Befunge resultante.

Abaixo são fornecidos vários programas do Prelude. Seu tradutor será executado em tudo isso. Sua pontuação é a soma dos tamanhos dos programas Befunge, desde que todos eles sejam válidos.

O seu tradutor não deve ser otimizado especificamente para esses casos de teste (por exemplo, codificando programas Befunge manuscritos para eles). Se eu suspeitar de alguma resposta, reservo-me o direito de alterar entradas ou criar outras.

Entradas de amostra

Imprima n-1para 0:

?(1-^!)

AND lógico:

?  (0)  
 ?(0  ) 
    1  !

OU lógico:

 ?   (0) 
? (0)    
   1  1 !

Verifique a paridade da entrada (ou seja, módulo 2) do número não negativo:

?(1-)   
 ^  v   
 v1-^^-!

Esquadrar a entrada:

 ^    
  ^+ !
?(1-) 

Imprimir o n th número de Fibonacci, onde n = 0corresponde a 0 e n = 1corresponde a 1:

0 v+v!
1   ^ 
?(1-) 

Signum:

  1) v #  - !
 vv (##^v^+) 
?(#   ^   ## 

Divisão para entradas não negativas:

1 (#  1) v #  - 1+)   
     vv (##^v^+)      
?  v-(0 # ^   #       
 ?                    
   1+              1-!

Obviamente, seu programa deve exibir o mesmo comportamento para todos os casos, mesmo que o comportamento do programa de amostra para números negativos não seja especificado.

Por fim, seu tradutor não deve ser excessivamente longo:

  • Ele deve estar contido em uma postagem do Stack Exchange
  • Ele deve processar as entradas de amostra em menos de 10 minutos em um computador desktop típico.

Observe que uma entrada numérica para Prelude ou Befunge é fornecida como um sinal de menos opcional seguido por um ou mais dígitos decimais, seguido por uma nova linha. Outra entrada é um comportamento indefinido.

Você pode escrever seu tradutor em qualquer idioma. O menor código Befunge traduzido vence.

Entre os melhores

  • Sp3000 : 16430 bytes
feersum
fonte
Não entendo: "Empurre para a pilha o valor mais alto da pilha da voz acima". Não precisa ser: "Empurre para a pilha o valor mais alto da pilha da voz acima".
1164 de
Ele diz que o prelúdio executa vozes simultaneamente, isso significa que elas são realmente executadas em um thread separado ou posso apenas executar os primeiros comandos em todas as vozes (de cima para baixo), depois os segundos comandos e assim por diante.
Def
@ Deformyer Eu mudei de "on" para "of", mas pensei que "o valor máximo da pilha" também não estava errado. Quanto à simultaneidade, não, você não precisa realmente interpretá-las em paralelo. O importante é que todos ajam no estado anterior das pilhas, e nenhuma operação em uma determinada coluna pode afetar qualquer outra operação nessa coluna.
Martin Ender
Vários casos de teste não violam "Nenhuma coluna com mais de uma instrução de E / S (! Ou?)?"
Fuwjax
@proudhaskeller O 1está dentro de um loop, portanto não pode ser pressionado. Um 0 pode vir da quantidade infinita de 0s que começa nas pilhas.
feersum

Respostas:

10

Python 3, marcará mais 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()))

Corra como py -3 prefunge.py <input filename> <output filename>.

Tem sido uma semana lenta para mim, então eu finalmente estava entediada o suficiente para enfrentar essa questão de seis meses. Eu perguntaria por que ninguém mais tentou, mas ainda sinto a dor da depuração (e provavelmente ainda existem bugs ainda por saber).

A questão não fornece um intérprete Befunge-93, então usei este , que é um pouco diferente das especificações. As duas principais diferenças são:

  • Se um caractere não existir em uma determinada linha do programa, você não poderá gravar nessa linha. Isso significa que você precisará pressionar Enter várias vezes para introduzir novas linhas suficientes no final . Se você NaNvir s na saída, essa é a causa mais provável.

  • As células da grade não são pré-inicializadas a zero - por conveniência, incluí alguma pré-inicialização nas saídas do Befunge, mas, como não é necessário, posso retirá-la quando começar a marcar.

O layout principal dos programas de saída é este:

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

O espaço da pilha está fora do programa, portanto, o comentário da nova linha Enter-spamming anterior.

A idéia central é atribuir a cada voz uma linha que serve como sua pilha. Para manter essas pilhas, também temos uma linha especial de comprimento da pilha, na qual o comprimento de cada pilha é registrado em uma célula ao longo da linha. O programa gcontém muitas ets e puts, por exemplo, para imprimir o processo é:

  • Obtenha o celular em y = stack_row[stack], x = stack_length[stack]
  • Executar .91+,, ou seja, imprima como número inteiro e imprima uma nova linha
  • Substitua a célula nas cordas acima por 0 (para simular popping)
  • Decremento stack_length[stack]

Para executar a avaliação simultânea de uma coluna, todas as células necessárias são lidas e seus valores são mantidos na pilha antes de qualquer célula ser gravada (por exemplo, no exemplo de impressão, pode haver mais instruções entre a primeira e a segunda etapas).

`, que é maior que, é empregado para garantir que os comprimentos da pilha nunca sejam negativos e para pressionar 0s quando a pilha estiver vazia. É daí que surge a ramificação claramente visível, mas eu tenho uma idéia que removerá a ramificação, o que deve remover muito espaço em branco da primeira e terceira linhas.

Para os loops, como os loops Prelude podem saltar para os dois lados, usamos duas linhas por loop em uma configuração como esta:

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

        ^                     <
       >                       ^

Atualmente, esses loops compõem a maioria dos bytes, mas podem ser facilmente reduzidos colocando-os na caixa de códigos p, o que pretendo fazer depois que estiver feliz que o tradutor esteja funcionando corretamente.

Aqui está um exemplo de saída para ?(1-^!), ou seja, imprima n-1para 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^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Quadrado da 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^
                                                             ^                                                                                                                                                  <
                                                            >                                                                                                                                                    ^

Divisão (pequenas entradas são recomendadas):

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  ^
                                                                                  ^                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        <
                                                                                 >                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ^
                                                                                                                                                                                                                                                                                                          ^                                                                        <
                                                                                                                                                                                                                                                                                                         >                                                                          ^
                                                                                                                                                                                                                                                                                                                                                                                                                    ^                                                                                                                                                                                                                                                                                                                                              <
                                                                                                                                                                                                                                                                                                                                                                                                                   >                                                                                                                                                                                                                                                                                                                                                ^

Há também várias outras otimizações menores que vêm à mente, como substituir 07p07gpor :07p, mas estou dando esse passo de cada vez :)

Sp3000
fonte
Então. Muito de. Livre. Tempo.
Optimizer
11
Will score later2 anos e contando! :)
HyperNeutrino 15/17