Przetłumacz Preludium na Befunge

19

To jest Tygodniowe Wyzwanie # 2. Temat: Tłumaczenie

Napisz program lub funkcję, która pobiera kod źródłowy dla programu w Preludium i wypisuje kod dla równoważnego programu w Befunge-93 . Aby program był równoważny, powinien, dla dowolnego wejścia, generować takie same dane wyjściowe jak program Preludium i zatrzymywać się wtedy i tylko wtedy, gdy program Prelude zatrzyma się.

Język wprowadzania: Preludium

Tłumacz języka Python:

Program Preludium składa się z wielu „głosów”, które wykonują instrukcje jednocześnie. Instrukcje dla każdego głosu znajdują się w osobnej linii. Każdy głos ma osobny stos, który jest inicjowany nieskończoną ilością zer. Egzekucja rozpoczyna się od lewej kolumny i przesuwa o jedną kolumnę w prawo po każdym tiku, chyba że wpływ )lub (instrukcje. Program kończy się po osiągnięciu ostatniej kolumny.

Preludium dla tego wyzwania:

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

Notatki

  • vi ^działają cyklicznie, więc vgłos dolny skopiuje element stosu głosu górnego, a ^głos górny skopiuje głos dolny. Następstwo: Zarówno vi ^duplikuj górę stosu w programie z jednym głosem.
  • A (i jego dopasowanie )może znajdować się na różnych liniach. Jednak a )zawsze będzie patrzeć na stos głosu, w którym (został umieszczony odpowiedni, a nie na stos, na którym )umieszczony jest sam.
  • Wartości wygenerowane przez instrukcje ^i vdziałają na wartościach obecnych przed zakończeniem jakichkolwiek innych operacji w tej samej kolumnie.
  • ?i !działają inaczej niż specyfikacja znaleziona na stronie esolangs.org, więc koniecznie przetestuj nieco zmodyfikowany interpreter podany w tym poście.

Gwarantowane wejście ma:

  • Pasujące nawiasy
  • Nie więcej niż jeden nawias w kolumnie
  • Ta sama liczba znaków w każdej linii
  • Co najmniej jedna linia
  • Brak kolumny z więcej niż jedną instrukcją We / Wy ( !lub ?)
  • Jeden znak kanału po instrukcjach dla każdego głosu
  • Żadnych znaków innych niż wymienione powyżej

Język wyjściowy: Befunge-93

Befunge jest językiem stosowym, którego licznik programów (PC; wskaźnik do bieżącej instrukcji) porusza się swobodnie na dwuwymiarowej siatce. Zaczyna się w lewym górnym rogu, przesuwając w prawo. Pole gry jest toroidalne, tzn. Ruch PC owija się wokół obu krawędzi. Befunge ma również stos, który jest inicjowany do nieskończonej liczby zer. Befunge ma następujące operacje:

Możesz założyć następujące cechy kompilatora / interpretera Befunge-93:

  • Liczby całkowite są nieograniczoną precyzją.
  • Umożliwia siatki o dowolnym rozmiarze.
  • Współrzędne siatki (dla gi p) są oparte na 0.

Punktacja

Aby zapobiec przesyłaniu, które po prostu tworzą interpreter Preludium w Befunge i zakoduje w nim źródło Prelude, celem będzie zminimalizowanie rozmiaru wynikowego kodu źródłowego Befunge.

Poniżej podano kilka programów Preludium. Twój tłumacz będzie działał na wszystkich tych urządzeniach. Twój wynik jest sumą rozmiarów programów Befunge, pod warunkiem, że wszystkie są ważne.

Twój tłumacz nie powinien być zoptymalizowany specjalnie pod kątem tych przypadków testowych (np. Przez zakodowanie dla nich ręcznie napisanych programów Befunge). Jeśli podejrzewam jakąkolwiek odpowiedź, zastrzegam sobie prawo do zmiany danych wejściowych lub tworzenia dodatkowych.

Przykładowe dane wejściowe

Wydrukuj n-1do 0:

?(1-^!)

Logiczne ORAZ:

?  (0)  
 ?(0  ) 
    1  !

Logiczne LUB:

 ?   (0) 
? (0)    
   1  1 !

Sprawdź parzystość wejścia (tj. Moduł 2) liczby nieujemnej:

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

Kwadrat wejściowy:

 ^    
  ^+ !
?(1-) 

Wydrukuj n- ty numer Fibonacciego, gdzie n = 0odpowiada 0 i n = 1odpowiada 1:

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

Signum:

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

Podział na dane nieujemne:

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

Oczywiście, twój program musi wykazywać to samo zachowanie dla wszystkich przypadków, nawet jeśli zachowanie przykładowego programu dla liczb ujemnych nie jest określone.

Twój tłumacz nie powinien być zbyt długi:

  • Musi być zawarty w poście stosu wymiany
  • Powinien przetworzyć przykładowe dane wejściowe w niecałe 10 minut na typowym komputerze stacjonarnym.

Zauważ, że dane liczbowe dla Preludium lub Befunge są podawane jako opcjonalny znak minus, po którym następuje jedna lub więcej cyfr dziesiętnych, a następnie nowa linia. Inne dane wejściowe to niezdefiniowane zachowanie.

Możesz napisać tłumacza w dowolnym języku. Najkrótszy przetłumaczony kod Befunge wygrywa.

Tabela liderów

  • Sp3000 : 16430 bajtów
feersum
źródło
Nie rozumiem: „Wciśnij na stos najwyższą wartość na stosie powyższego głosu”. Nie musi to być: „Push na stos wartość najwyższą od stosu powyższej głosem.”
Def
Mówi, że preludium wykonuje głosy jednocześnie, czy to znaczy, że są one naprawdę wykonywane w osobnym wątku, czy mogę po prostu wykonać pierwsze polecenia na wszystkich głosach (od góry do dołu), a następnie drugie polecenia i tak dalej.
Def
@Deformyer Zmieniłem to z „on” na „of”, ale pomyślałem, że „najwyższa wartość na stosie” też nie było złe. Jeśli chodzi o równoczesność, nie trzeba interpretować ich równolegle. Ważne jest to, że wszystkie działają na poprzednim stanie stosów i żadna operacja w danej kolumnie nie może wpłynąć na żadną inną operację w tej kolumnie.
Martin Ender
Czy kilka przypadków testowych nie narusza zasad „Brak kolumny z więcej niż jedną instrukcją we / wy (! Lub?)?”
Fuwjax
@proudhaskeller 1Jest w pętli, więc nie można go popychać . 0 może pochodzić z nieskończonej liczby zer, które zaczynają się na stosach.
feersum

Odpowiedzi:

10

Python 3, zdobędzie później

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

Biegnij jak py -3 prefunge.py <input filename> <output filename>.

To był dla mnie powolny tydzień, więc w końcu nudziłem się, by odpowiedzieć na to sześciomiesięczne pytanie. Zapytałbym, dlaczego nikt inny nie próbował, ale wciąż odczuwam ból podczas debugowania (i prawdopodobnie nadal pozostały błędy).

Pytanie nie zapewnia interpretera Befunge-93, więc użyłem tego , który nieco różni się od specyfikacji. Dwie kluczowe różnice to:

  • Jeśli znak nie istnieje w danym wierszu programu, nie możesz pisać do tego wiersza. Oznacza to , że musisz nacisnąć Enter kilka razy, aby na końcu wprowadzić wystarczającą liczbę nowych linii . Jeśli widzisz NaNs na wyjściu, jest to najbardziej prawdopodobna przyczyna.

  • Komórki siatki nie są wstępnie inicjowane do zera - dla wygody umieściłem trochę wstępnej inicjalizacji w wynikach Befunge, ale ponieważ nie jest to konieczne, mogę to zabrać, gdy zacznę punktować.

Podstawowy układ programów wyjściowych jest następujący:

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

Miejsce na stosie znajduje się poza programem, stąd nowy wiersz komentarza Enter-spam z wcześniejszego.

Podstawową ideą jest przypisanie każdemu głosowi wiersza, który służy jako jego stos. Aby zachować te stosy, mamy również specjalny rząd długości stosu, w którym długość każdego stosu jest rejestrowana w komórce wzdłuż tego rzędu. Program zawiera wtedy wiele gets i puts, np. Do drukowania proces to:

  • Pobierz komórkę na y = stack_row[stack], x = stack_length[stack]
  • Wykonaj .91+,, tj. Wydrukuj jako liczbę całkowitą, a następnie wydrukuj nowy wiersz
  • Zamień komórkę na powyższych współrzędnych na 0 (aby symulować popping)
  • Zmniejszenie stack_length[stack]

Aby wykonać jednoczesną ocenę kolumny, wszystkie niezbędne komórki są odczytywane, a ich wartości są przechowywane na stosie przed zapisaniem jakichkolwiek komórek (np. W przykładzie drukowania może być więcej instrukcji pomiędzy pierwszym a drugim krokiem).

`, który jest większy niż, służy do upewnienia się, że długości stosu nigdy nie są ujemne, oraz do wypychania zer, gdy stos jest pusty. Stąd pochodzi wyraźnie widoczne rozgałęzienie, ale mam pomysł, który usunie rozgałęzienie, które powinno usunąć sporo białych znaków z pierwszego i trzeciego wiersza.

W przypadku pętli, ponieważ pętle Prelude mogą przeskakiwać w obie strony, używamy dwóch wierszy na pętlę w konfiguracji takiej jak ta:

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

        ^                     <
       >                       ^

Pętle te stanowią obecnie większość bajtów, ale można je łatwo zagrać w golfa, umieszczając je w pudełku kodowym p, co planuję zrobić po tym, jak cieszę się, że tłumacz działa poprawnie.

Oto kilka przykładowych danych wyjściowych ?(1-^!), np. Wydrukuj n-1do 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^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Kwadrat wejściowy:

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

Podział (zalecane są małe nakłady):

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

Jest też kilka innych drobnych optymalizacji, które przychodzą na myśl, jak zastępowanie 07p07gz :07p, ale biorę ten jeden krok na raz :)

Sp3000
źródło
Więc. Wiele. Darmowy. Czas.
Optymalizator
1
Will score later2 lata i wciąż rośnie! :)
HyperNeutrino,