Перевести прелюдию на Befunge

19

Это еженедельный вызов № 2. Тема: Перевод

Напишите программу или функцию, которая принимает исходный код для программы в Prelude и выводит код для эквивалентной программы в Befunge-93 . Для того чтобы программа была эквивалентной, она должна для любого заданного ввода выдавать тот же результат, что и программа Prelude, и останавливаться тогда и только тогда, когда программа Prelude останавливается.

Язык ввода: прелюдия

Интерпретатор Python:

Программа Prelude состоит из нескольких «голосов», которые выполняют инструкции одновременно. Инструкции для каждого голоса находятся на отдельной строке. Каждый голос имеет отдельный стек, который инициализируется бесконечным количеством нулей. Выполнение начинается в крайнем левом столбце и продвигается на один столбец вправо каждый тик, за исключением случаев, когда на него влияют )или (инструкции. Программа завершается при достижении последнего столбца.

Прелюдия спецификации для этого вызова:

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

Примечания

  • vи ^действуйте циклически, поэтому vнижний голос скопирует элемент стека верхнего голоса, а ^верхний голос скопирует из нижнего голоса. Следствие:v и то, и другое ^дублирует верхнюю часть стека в одноголосной программе.
  • А (и его соответствие )могут быть расположены на разных строках. Тем не менее , a )всегда будет смотреть на стек голоса, в котором (был размещен соответствующий голос , а не на стек, где был размещен сам голос ).
  • Значения , произведенные ^и vинструкция по эксплуатации от значений , присутствующих до завершения каких - либо других операций в том же самом столбце.
  • ?и !работать не так, как в спецификации на esolangs.org, поэтому не забудьте протестировать с немного измененным интерпретатором, представленным в этом посте.

Вклад гарантированно будет иметь:

  • Соответствующие скобки
  • Не более одной скобки в столбце
  • Одинаковое количество символов в каждой строке
  • Хотя бы одна строка
  • Нет столбца с более чем одной инструкцией ввода-вывода ( !или ?)
  • Один символ перевода строки после инструкций для каждого голоса
  • Нет символов, кроме упомянутых выше

Язык вывода: Befunge-93

Befunge - это стековый язык, программный счетчик которого (ПК; указатель на текущую инструкцию) свободно перемещается по двумерной сетке. Он начинается в верхнем левом углу, двигаясь вправо. Поле для игры является тороидальным, то есть движение ПК охватывает оба края. Befunge также имеет стек, который инициализируется бесконечным числом нулей. Befunge выполняет следующие операции:

Вы можете принять следующие характеристики компилятора / интерпретатора Befunge-93:

  • Целые числа имеют неограниченную точность.
  • Это позволяет сетки любого размера.
  • Координаты сетки (для gи p) основаны на 0.

счет

Чтобы не допустить отправки, которые просто создают интерпретатор Prelude в Befunge и жестко кодируют в него исходный код Prelude, цель состоит в том, чтобы минимизировать размер получающегося исходного кода Befunge.

Ниже представлен ряд программ Prelude. Ваш переводчик будет работать на все это. Ваша оценка - это сумма размеров программ Befunge при условии, что все они действительны.

Ваш переводчик не должен быть оптимизирован специально для этих тестовых случаев (например, путем жесткого написания для них рукописных программ Befunge). Если я подозреваю какой-либо ответ на этот вопрос, я оставляю за собой право изменять входные данные или создавать дополнительные.

Образцы входов

Распечатать n-1до 0:

?(1-^!)

Логическое И:

?  (0)  
 ?(0  ) 
    1  !

Логическое ИЛИ:

 ?   (0) 
? (0)    
   1  1 !

Проверьте четность ввода (т.е. по модулю 2) неотрицательного числа:

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

Квадратный вход:

 ^    
  ^+ !
?(1-) 

Выведите n- е число Фибоначчи, где n = 0соответствует 0 и n = 1соответствует 1:

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

Signum:

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

Отдел неотрицательных входов:

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

Конечно, ваша программа должна демонстрировать одинаковое поведение во всех случаях, даже если поведение программы примера для отрицательных чисел не указано.

Наконец, ваш переводчик не должен быть неоправданно длинным:

  • Он должен содержаться в сообщении Stack Exchange
  • Он должен обрабатывать вводимые данные менее чем за 10 минут на обычном настольном компьютере.

Обратите внимание, что числовой ввод для Prelude или Befunge задается как необязательный знак минуса, за которым следуют одна или несколько десятичных цифр, за которыми следует новая строка. Другой ввод - неопределенное поведение.

Вы можете написать свой переводчик на любом языке. Кратчайший перевод кода Befunge выигрывает.

Leaderboard

  • Sp3000 : 16430 байт
feersum
источник
Я не понимаю: «Поместите в стек верхнее значение в стеке вышеупомянутого голоса». Разве это не должно быть: «Нажмите на стек верхнее значение из стека указанного выше голоса.»
Def
Он говорит, что prelude выполняет голоса одновременно, означает ли это, что они действительно выполняются в отдельном потоке, или я могу просто выполнить первые команды для всех голосов (сверху вниз), затем вторые команды и так далее.
Def
@Deformyer Я изменил его с «on» на «of», но я подумал, что «top value on the stack» также не ошибся. Что касается одновременности, нет, вам не нужно фактически интерпретировать их параллельно. Важно то, что все они влияют на предыдущее состояние стеков, и никакие операции в данном столбце не могут повлиять на другие операции в этом столбце.
Мартин Эндер
Не нарушают ли несколько тестов «Нет столбца с более чем одной инструкцией ввода-вывода (! Или?)?»
Fuwjax
@proudhaskeller 1находится внутри цикла, поэтому его нельзя нажимать. 0 может исходить из бесконечного количества 0, которые начинаются на стеках.
feersum

Ответы:

10

Python 3, забьет позже

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()))

Беги как py -3 prefunge.py <input filename> <output filename>.

Это была медленная неделя для меня, поэтому мне наконец-то стало достаточно скучно, чтобы заняться этим шестимесячным вопросом. Я спросил бы, почему никто не попробовал, но я все еще чувствую боль от отладки (и, вероятно, все еще остаются ошибки, насколько я знаю).

Вопрос не предусматривает интерпретатора Befunge-93, поэтому я использовал этот , который немного отличается от спецификации. Два ключевых различия:

  • Если в данной строке программы нет символа, вы не можете писать в эту строку. Это означает, что вам нужно будет нажать Enter несколько раз, чтобы ввести достаточно новых строк в конце . Если вы видите NaNs в выводе, это наиболее вероятная причина.

  • Ячейки сетки не инициализируются до нуля - для удобства я включил некоторую преинициализацию в выходы Befunge, но, поскольку это не является необходимым, я могу убрать его, когда начну подсчет очков.

Основная схема выходных программ такова:

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

Пространство стека находится за пределами программы, отсюда и новый комментарий Enter-spamming от ранее.

Основная идея состоит в том, чтобы назначить каждому голосу строку, которая служит его стеком. Для поддержки этих стеков у нас также есть специальная строка длины стека, где длина каждого стека записывается в ячейку вдоль строки. В программе много gплюсов и pминусов, например, для печати процесс выглядит так:

  • Получить камеру в y = stack_row[stack], x = stack_length[stack]
  • Выполните .91+,, то есть напечатайте как целое число, затем напечатайте новую строку
  • Замените ячейку с указанными выше координатами на 0 (для имитации появления)
  • декремент stack_length[stack]

Чтобы выполнить одновременную оценку столбца, все необходимые ячейки считываются и их значения сохраняются в стеке до того, как в них будут записаны какие-либо ячейки (например, для примера печати может быть больше инструкций между первым и вторым этапами).

`, который больше чем, используется, чтобы убедиться, что длина стека никогда не становится отрицательной, и для нажатия 0, когда стек пуст. Отсюда и ясно видимое ветвление, но у меня есть идея, которая удалит ветвление, которое должно удалить большое количество пробелов из первой и третьей строк.

Для циклов, поскольку циклы Prelude могут перемещаться в обоих направлениях, мы используем две строки на цикл в такой конфигурации:

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

        ^                     <
       >                       ^

Эти циклы в настоящее время составляют большую часть байтов, но их можно легко обойти, поместив их в кодовое поле p, что я планирую сделать после того, как буду рад, что переводчик работает правильно.

Вот пример выходных данных для ?(1-^!), т.е. распечатать n-1до 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^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Квадрат-заместитель ввод:

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

Разделение (рекомендуются небольшие входы):

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

Также на ум приходит множество других небольших оптимизаций, например, замена 07p07gна :07p, но я делаю это по одному шагу за раз :)

Sp3000
источник
Так. Многое. Свободно. Время.
Оптимизатор
1
Will score later2 года и считай! :)
HyperNeutrino