Komprimieren Sie ein Befunge-Programm

17

Befunge ist eine zweidimensionale esoterische Programmiersprache. Die Grundidee ist, dass (Ein-Zeichen-) Befehle in einem zweidimensionalen Raster platziert werden. Der Kontrollfluss wandert über das Raster, führt Befehle aus, über die er geleitet wird, und ändert die Richtung, wenn er auf einen Pfeil ( >^<v) trifft . Befehle sind stapelbasiert. siehe diese Liste . Siehe auch http://esolangs.org/wiki/Befunge .

Die Spezifikation für Befunge-98 ist verfügbar.

Problem

Schreiben Sie ein Programm, das ein Befunge-Programm in eine kompaktere Darstellung umwandelt. Das folgende Programm druckt beispielsweise 0:

>   0   v

>   @   .

^       <

In diesem Fall könnte es komprimiert werden, ohne das Verhalten des Programms zu ändern, indem Leerzeilen entfernt werden, um zu geben

>0v
>@.
^ <

Durch komplexere Transformationen können Befehlssequenzen gedreht oder gespiegelt und unnötige Steuerungsflussbefehle beseitigt werden, um das Programm zu komprimieren. Zum Beispiel mit diesem Programm:

>12345v
      6
v....7<
.
.
.
@

Sie könnten das Ende des Programms in das Loch stecken:

>12345v
>...@ 6
^....7<

Für das erste Beispiel ist das kompakteste Programm möglich

>0.@

Sie können beliebige Transformationen verwenden, solange das Ausgabeprogramm das gleiche Ergebnis liefert.

Programme eingeben

Eingabeprogramme sind gültige Befunge-98-Programme.

Sie können davon ausgehen, dass das Eingabeprogramm deterministisch ist. Das heißt, es werden keine Befehle zum Lesen des externen Zustands verwendet: die Benutzereingabebefehle &und ~, der Randomizer ?und die selbstmodifizierenden Codebefehle pund g.

Sie können davon ausgehen, dass das Eingabeprogramm beendet wird.

Wertung

Dies ist kein Codegolf, sondern ein Problem beim Schreiben eines Programms, das Codegolf ausführt.

Die Eingabe ist eine Reihe von Testfällen (Befunge-Programme, die die oben genannten Eingabebeschränkungen erfüllen). Die Gesamtpunktzahl ist die Summe der Punkte für die Testfälle.

Ergebnis für jeden Testfall

Die Punktzahl ist die Fläche der konvexen Hülle der nicht leeren Zellen im Ausgabeprogramm, wobei jede Zelle als Quadrat behandelt wird, dessen vier Ecken Gitterpunkte in der kartesischen Ebene sind. Zum Beispiel ein Programm von

>   v
 @  <

erhält eine Punktzahl von 9,5.

Wenn Ihr Programm bei einer bestimmten Eingabe nicht innerhalb eines angemessenen Zeitraums und Speicherplatzes beendet wird, entspricht die Bewertung der des Eingabeprogramms. (Dies liegt daran, dass Sie trivialerweise einen zeitlich begrenzten Wrapper hinzufügen könnten, der das Eingabeprogramm unverändert ausgibt, wenn Ihr Programm nicht rechtzeitig beendet wird.)

Wenn das Testfallprogramm nach der Verarbeitung mit Ihrem Programm ein anderes Ergebnis hat (oder nicht beendet wird), ist die Punktzahl die Punktzahl des Eingabeprogramms zuzüglich einer Strafe von 100 Punkten.

Mechanische Schnecke
quelle
8
Was kann verhindert werden, dass das Programm vollständig ausgeführt und ein Befunge-Programm geschrieben wird, das dieselbe Ausgabe druckt?
Keith Randall
5
Sind "get" und "put" erlaubt? Wenn Sie "put" (selbstmodifizierender Code) zulassen, ist es schwierig, etwas zu tun.
Keith Randall
2
Wo beginnt die Hinrichtung? Obere linke Ecke? Wenn ja, können Sie die Ausgabe des zweiten Beispiels erläutern? .bedeutet Ausgabe-Ganzzahl, aber wenn Sie von links oben beginnen, ist im Stapel keine Ganzzahl für die Ausgabe vorhanden.
Elssar
1
@elssar yes, .gibt eine Ganzzahl aus. Wenn jedoch nicht genügend Parameter auf dem Stapel vorhanden sind, wird vorgetragen, dass stattdessen eine ausreichende Anzahl von Nullen vorhanden ist. Das zweite Beispiel würde also ausgegeben 000.
Daniero
@KeithRandall: Das Schreiben eines neuen Programms mit derselben Ausgabe funktioniert nur für Programme mit einer kurzen Ausgabe. gund psind nicht erlaubt (sorry, vergessen; bearbeitet).
Mechanische Schnecke

Antworten:

12

Ich habe eine lange Flugreise damit verbracht, diese zu verschlüsseln. Ich habe einen Pseudo-Befunge-Compiler geschrieben, der das Befunge-Programm ausführt, grundlegende Blöcke extrahiert und sie in einer kompakten Darstellung anordnet.

Link zum Programm .

Bei Ausführung mit diesem 99-Flaschen-Programm:

92+9*                           :. v  <
>v"bottles of beer on the wall"+910<
,:
^_ $                             :.v
            >v"bottles of beer"+910<
            ,:
            ^_ $                     v
>v"Take one down, pass it around"+910<
,:
^_ $                           1-v
                                 :
        >v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    >v" no more beer..."+910<
                    ,:
                    ^_ $$ @

Es erzeugt die folgende Ausgabe:

92+9*:.019+"llaw eht no "v
v  _v# :"bottles of beer"<
>    ,:    v
^  _v#     <
    >$:.019+"reeb f"v
 v _  v#:"bottles o"<
 >     ,:  v
 ^ _  v#   <
      >$019+"dnuo"v
     v"pass it ar"<
     >" ,nwod eno"v
 v _    v#:"Take "<
 >       ,:v
 ^ _    v# <
        >$1-:v
 v _      v# <
 >         :.019+"reeb "v
  v_  v#   :"bottles of"<
  >        ,v
  ^_  v#   :<
      >    $019+"llaw"v
           v" on the "<
           >"reeb fo "v
^  _^#      :"bottles"<
          >019+"...r"v
v  _v#:" no more bee"<
>    ,:    v
^  _v#     <
    >$$@    

Tatsächlich ist es nicht viel kompakter als der Quellcode, aber bei größeren / sparseren Programmen ist es wahrscheinlich besser.

Das Programm ist links mit einem Arbeitsplan und rechts mit dem Inhalt der Grundbausteine ​​angelegt. Ein Basisblock ist normalerweise in einer geraden Anzahl von Reihen angeordnet, so dass der Ein- und Ausgang an den Routing-Bereich angrenzt. Am Ende jedes Basisblocks führen das Gadget #^_vund die Varianten, die von rechts nach links angeordnet sind, die bedingte Verzweigung aus und leiten den Fluss in Spalten. Zu Beginn eines jeden Basisblocks werden diese Spalten in die Zeilen des Zielbasisblocks geroutet.

Wenn die Ausgabe kurz ist, wird sie außerdem explizit wie folgt generiert:

"output">:#,_@

Ich habe nichts unternommen, um die Basisblöcke selbst zu optimieren, nur das Layout. Machen.

Also wo sind die Tests?

Keith Randall
quelle
1
der Quellcode-Link scheint momentan 500 zu sein. Fehlkonfiguration des Servers?
John Dvorak
1
@ JanDvorak: in der Tat. Fest.
Keith Randall
1

Sed, 5 Zeichen

Also, auch wenn dies kein Codegolf ist, hier ist eine Lösung, die ein ziemlich gutes Verhältnis von Codelänge zu Punktzahl hat, aber nicht unbedingt eine gute Punktzahl.

/^$/d

Leerzeilen werden einfach entfernt.

daniero
quelle
10
Ihr Code ist nicht korrekt! Sie können nicht einfach Leerzeilen entfernen. Ich kann keinen 2d Code in Kommentar schreiben. Betrachten Sie jedoch einen Fall, bei dem die Richtung nach unten zeigt und eine konstante Zeichenfolge gestartet wird ( "). Jede Leerzeile im Weg sollte als Leerzeichen behandelt werden. Wenn wir diesen String ausdrucken, enthält der von Ihnen generierte Code keine Leerzeichen in der Ausgabe!
Saeedn
3
Sehen Sie sich den Code in ideone.com/BdcRcf an. Er sollte gedruckt werden b a. Nach dem Kürzen wird es gedruckt ba.
Saeedn