Übersetzen Sie Vorspiel zu Befunge

19

Dies ist die wöchentliche Herausforderung Nr. 2. Thema: Übersetzung

Schreiben Sie ein Programm oder eine Funktion, die Quellcode für ein Programm in Prelude und Code für ein gleichwertiges Programm in Befunge-93 ausgibt . Damit das Programm äquivalent ist, sollte es für eine bestimmte Eingabe dieselbe Ausgabe wie das Prelude-Programm erzeugen und nur dann anhalten, wenn das Prelude-Programm anhält.

Eingabesprache: Prelude

Python-Interpreter:

Ein Prelude-Programm besteht aus mehreren "Stimmen", die gleichzeitig Befehle ausführen. Die Anweisungen für jede Stimme befinden sich in einer separaten Zeile. Jede Stimme hat einen separaten Stapel, der mit einer unendlichen Anzahl von Nullen initialisiert wird. Die Ausführung beginnt in der äußersten linken Spalte und rückt mit jedem Häkchen eine Spalte nach rechts vor, es sei denn, dies wird durch )oder beeinflusst( Anweisungen beeinflusst. Das Programm wird beendet, wenn die letzte Spalte erreicht ist.

Vorspezifikation für diese Herausforderung:

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

Anmerkungen

  • vund ^agiere zyklisch, so dass die vuntere Stimme das Stack-Element der oberen Stimme und ^die obere Stimme die untere Stimme kopiert. Folgerung: Beides vund ^Duplizieren der Stapelspitze in einem einstimmigen Programm.
  • A (und seine Übereinstimmung )können sich in verschiedenen Zeilen befinden. Allerdings , ein )schaut immer auf dem Stapel der Stimme , wo die entsprechenden (platziert wurde, nicht den Stapel , wo die )selbst angeordnet ist.
  • Die von den Befehlen ^und erzeugten Werte vbeziehen sich auf die Werte, die vor Abschluss aller anderen Vorgänge in derselben Spalte vorliegen.
  • ?und !funktionieren anders als auf esolangs.org angegeben. Testen Sie daher unbedingt mit dem in diesem Beitrag bereitgestellten leicht geänderten Interpreter.

Input hat garantiert:

  • Passende Klammern
  • Nicht mehr als eine Klammer in einer Spalte
  • Gleiche Anzahl von Zeichen in jeder Zeile
  • Mindestens eine Zeile
  • Keine Spalte mit mehr als einer E / A- Anweisung ( !oder ?)
  • Ein Zeilenvorschubzeichen nach den Anweisungen für jede Stimme
  • Keine anderen Zeichen als die oben genannten

Ausgabesprache: Befunge-93

Befunge ist eine stapelbasierte Sprache, deren Programmzähler (PC; Zeiger auf die aktuelle Anweisung) sich auf einem zweidimensionalen Raster frei bewegt. Es beginnt in der oberen linken Ecke und bewegt sich nach rechts. Das Spielfeld ist toroidal, dh die PC-Bewegung verläuft um beide Kanten. Befunge hat auch einen Stapel, der mit einer unendlichen Anzahl von Nullen initialisiert wird. Befunge hat folgende Operationen:

Sie können die folgenden Eigenschaften des Befunge-93-Compilers / -Interpreters annehmen:

  • Ganzzahlen sind unbegrenzt genau.
  • Es erlaubt Gitter jeder Größe.
  • Gitterkoordinaten (für gund p) basieren auf 0.

Wertung

Um zu verhindern, dass Einreichungen, die lediglich einen Prelude-Interpreter in Befunge erzeugen, die Prelude-Quelle fest codieren, wird das Ziel darin bestehen, die Größe des resultierenden Befunge-Quellcodes zu minimieren.

Im Folgenden finden Sie eine Reihe von Prelude-Programmen. Ihr Übersetzer wird auf all diesen ausgeführt. Ihre Punktzahl ist die Summe der Größen der Befunge-Programme, sofern alle gültig sind.

Ihr Übersetzer sollte nicht speziell für diese Testfälle optimiert werden (z. B. durch Hardcodierung handgeschriebener Befunge-Programme für diese). Wenn ich eine Antwort vermute, behalte ich mir das Recht vor, Eingaben zu ändern oder zusätzliche zu erstellen.

Beispieleingaben

Drucken n-1bis 0:

?(1-^!)

Logisches UND:

?  (0)  
 ?(0  ) 
    1  !

Logisches ODER:

 ?   (0) 
? (0)    
   1  1 !

Überprüfen Sie die Parität der Eingabe (dh Modulo 2) der nichtnegativen Zahl:

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

Quadrieren Sie die Eingabe:

 ^    
  ^+ !
?(1-) 

Gib die n- te Fibonacci-Zahl aus, wobei n = 00 und n = 11 entspricht:

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

Signum:

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

Division für nicht negative Eingänge:

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

Natürlich muss Ihr Programm in allen Fällen dasselbe Verhalten aufweisen, auch wenn das Verhalten des Beispielprogramms für negative Zahlen nicht angegeben ist.

Schließlich sollte Ihr Übersetzer nicht unangemessen lang sein:

  • Es muss in einem Stack Exchange-Post enthalten sein
  • Auf einem typischen Desktop-Computer sollten die Beispieleingaben in weniger als 10 Minuten verarbeitet werden.

Beachten Sie, dass eine numerische Eingabe für Prelude oder Befunge als optionales Minuszeichen gefolgt von einer oder mehreren Dezimalstellen und einer neuen Zeile angegeben wird. Andere Eingaben sind undefiniertes Verhalten.

Sie können Ihren Übersetzer in jeder Sprache schreiben. Kürzester übersetzter Befunge-Code gewinnt.

Bestenliste

  • Sp3000 : 16430 Byte
Feersum
quelle
Ich verstehe nicht: "Schieben Sie den obersten Wert auf dem Stapel der obigen Stimme auf den Stapel." Muss es nicht sein: "Schiebe den höchsten Wert des Stapels der obigen Stimme auf den Stapel ."
Def
Im Vorspiel werden Stimmen gleichzeitig ausgeführt. Bedeutet dies, dass sie tatsächlich in einem separaten Thread ausgeführt werden, oder kann ich nur die ersten Befehle für alle Stimmen ausführen (von oben nach unten), dann die zweiten Befehle und so weiter.
Def
@Deformyer Ich habe es von "on" auf "of" geändert, aber ich dachte, "Top Value on the Stack" wäre auch nicht falsch. Was die Gleichzeitigkeit betrifft, müssen Sie sie nicht parallel interpretieren. Wichtig ist, dass alle auf den vorherigen Status der Stapel angewendet werden und keine Operation in einer bestimmten Spalte eine andere Operation in dieser Spalte beeinflussen kann.
Martin Ender
Verstoßen nicht mehrere Testfälle gegen "Keine Spalte mit mehr als einer E / A-Anweisung (! Oder?)?"
Fuwjax
@proudhaskeller Der 1befindet sich in einer Schleife, daher darf er nicht gedrückt werden. Eine 0 kann aus der unendlichen Anzahl von Nullen entstehen, die auf den Stapeln beginnen.
Feersum

Antworten:

10

Python 3 wird später punkten

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

Laufen wie py -3 prefunge.py <input filename> <output filename>.

Es war eine langsame Woche für mich, also langweilte ich mich endlich genug, um diese sechs Monate alte Frage anzugehen. Ich würde fragen, warum es niemand anders versucht hat, aber ich habe immer noch das Gefühl, dass das Debuggen mir weh tut (und wahrscheinlich gibt es immer noch Fehler, soweit ich weiß).

Die Frage enthält keinen Befunge-93-Interpreter, daher habe ich diesen verwendet , der sich geringfügig von der Spezifikation unterscheidet. Die zwei Hauptunterschiede sind:

  • Wenn in einer bestimmten Zeile des Programms kein Zeichen vorhanden ist, können Sie nicht in diese Zeile schreiben. Dies bedeutet , dass Sie mehrmals die Eingabetaste drücken müssen, um am Ende genügend Zeilenumbrüche einzufügen . Wenn Sie NaNs in der Ausgabe sehen, ist dies die wahrscheinlichste Ursache.

  • Gitterzellen sind nicht auf Null vorinitialisiert - der Einfachheit halber habe ich einige Vorinitialisierungen in die Befunge-Ausgaben aufgenommen, da dies jedoch nicht erforderlich ist, kann ich sie entfernen, wenn ich mit dem Scoring beginne.

Das Kernlayout der Ausgabeprogramme lautet wie folgt:

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

Der Stapelspeicherplatz befindet sich außerhalb des Programms, daher der Kommentar zum Eingeben von Spam in der neuen Zeile aus früheren Versionen.

Die Kernidee ist, jeder Stimme eine Reihe zuzuweisen, die als Stapel dient. Um diese Stapel beizubehalten, haben wir auch eine spezielle Reihe mit Stapellängen, in der die Länge jedes Stapels in einer Zelle entlang der Reihe aufgezeichnet wird. Das Programm gibt dann viele gets und puts aus, zB zum Ausdrucken des Prozesses ist:

  • Holen Sie sich die Zelle an y = stack_row[stack], x = stack_length[stack]
  • Führen Sie dies aus .91+,, dh drucken Sie als Ganzzahl und drucken Sie dann eine neue Zeile
  • Ersetzen Sie die Zelle bei den obigen Koordinaten durch 0 (um das Aufspringen zu simulieren)
  • Dekrement stack_length[stack]

Um die gleichzeitige Auswertung einer Spalte durchzuführen, werden alle erforderlichen Zellen gelesen und ihre Werte auf dem Stapel gehalten, bevor Zellen beschrieben werden (z. B. für das Druckbeispiel können zwischen dem ersten und dem zweiten Schritt mehr Anweisungen vorhanden sein).

`Der Wert größer als wird verwendet, um sicherzustellen, dass die Stapellängen niemals negativ werden, und um Nullen zu setzen, wenn der Stapel leer ist. Hier kommt die deutlich sichtbare Verzweigung her, aber ich habe eine Idee, mit der die Verzweigung entfernt wird, wodurch viel Leerzeichen in der ersten und dritten Zeile entfernt werden sollten.

Da Prelude-Schleifen in beide Richtungen springen können, verwenden wir für die Schleifen zwei Zeilen pro Schleife in einer Konfiguration wie der folgenden:

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

        ^                     <
       >                       ^

Diese Loops machen derzeit den größten Teil der Bytes aus, können jedoch leicht heruntergespielt werden, indem sie in der Codebox mit abgelegt werden p ich, nachdem ich froh bin, dass der Übersetzer richtig funktioniert.

Hier ist ein Beispiel für die Ausgabe von ?(1-^!), dh Drucken n-1auf 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^
                              ^                                                                                                                                <
                             >                                                                                                                                  ^

Square-the-Input:

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

Division (kleine Eingaben werden empfohlen):

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

Es gibt auch eine Reihe anderer kleinerer Optimierungen, die mir in den Sinn kommen, zum Beispiel das Ersetzen 07p07gdurch :07p, aber ich mache diesen Schritt nach dem anderen :)

Sp3000
quelle
So. Viel. Frei. Zeit.
Optimierer
1
Will score later2 Jahre und es zählt! :)
HyperNeutrino