Beschreibung

Imaginary Programming Language (IPL) verwendet die polnische Umkehrnotation. Es hat die folgenden Befehle:

• i - Nummer eingeben und auf den Stapel schieben
• o - zerstörungsfreie Ausgabe oben auf dem Stapel (Nummer bleibt auf dem Stapel)
• d - Stapel oben wegwerfen
• Ganzzahl - Schieben Sie diese Zahl auf den Stapel
• + - * - Zwei Zahlen aus dem Stapel ziehen, entsprechende Operation ausführen und das Ergebnis zurückschieben. Es gibt keine Unterteilung in IPL.

IPL funktioniert nur mit ganzen Zahlen und wird für einfache Berechnungen verwendet. Ein IPL-Programm wird in eine Zeile geschrieben und durch Leerzeichen getrennt. Leere Zeichenfolge ist ein gültiges IPL-Programm.

IPL-Programm:

i i + o 

Gibt zwei Zahlen ein, addiert sie und gibt das Ergebnis aus.

Eingabenummern und Ganzzahlen, die zum Stapeln verschoben werden können, liegen im Bereich [-999, 999], die Ausgabe kann jedoch beliebig sein. Wenn Ihre Sprache keine großen Zahlen unterstützt, ist dies jedoch in Ordnung.

Eingabe- / Ausgabeformat

Sie können ein beliebiges Eingabe- / Ausgabeformat auswählen, sofern das Verstehen und Lesen / Schreiben klar ist: Zeichenfolge, Liste, Token usw.

Aufgabe

Sie erhalten ein IPL-Programm, das Sie optimieren müssen (Länge reduzieren):

i 12 + 3 + o d 2 3 + d

Nach der Optimierung werden

i 15 + o

Sie müssen den Stapelstatus nicht beibehalten, aber die Anzahl der Eingaben und Ausgaben sowie deren Reihenfolge sollten für das ursprüngliche und optimierte Programm übereinstimmen.

Also IPL-Programm:

-40 i * 2 * o i + 3 1 + o i 2 *

Nach der Optimierung werden

i -80 * o i 4 o i

oder

-80 i * o i 4 o i

(Beachten Sie, dass Sie alle Eingaben speichern müssen, auch wenn sie irrelevant sind).

Es sollte keine Hardcodierung für Testfälle geben, Code sollte auf jedem beliebigen IPL-Programm funktionieren und ein möglichst kurzes IPL-Programm erstellen, das die Anforderungen erfüllt.

Wertung

Standard-Code-Golf-Wertung.

UPDATE: Die Wertung wurde gemäß @Sanchises-Vorschlag in reine Code-Golfwertung geändert.

Testfälle:

Eingang:

(empty string)

Mögliche Ausgabe:

(empty string)

Eingang:

i 4 * 2 + 3 * 6 - o

Mögliche Ausgabe:

i 12 * o

Eingang:

1 1 + o

Mögliche Ausgabe:

2 o

Eingang:

i 2 + 3 + o d 2 3 + d

Mögliche Ausgabe:

i 5 + o

Eingang:

-40 i * 2 * o i + 3 1 + o i 2 *

Mögliche Ausgabe:

-80 i * o i 4 o i

Eingang:

i i 1 + i 1 + i 1 + i 1 + d d d d o 

Mögliche Ausgabe:

i i i i i d d d d o 

Eingang:

i i i 0 * * * o

Mögliche Ausgabe:

i i i 0 o

Eingang:

i i i 1 * * * o

Mögliche Ausgabe:

i i i * * o

Eingang:

i 222 + i 222 - + o

Mögliche Ausgabe:

i i + o

Eingang:

i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Mögliche Ausgabe:

i i i i i o 1 o

Eingang:

i 1 + 2 * 1 + o 

Mögliche Ausgabe:

i 2 * 3 + o

Eingang:

1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Mögliche Ausgabe:

2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o

Wolfram Language (Mathematica) , 733 728 690 564 516 506 513 548 Bytes

j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}->{y,t,x*y,p},{x_j,y_j,p}->x+y,{x_j,y_j,t}->x*y,{x_j,p,y_j,p}->{x+y,p},{x_j,t,y_j,t}->{x*y,t},{0,p}|{1,t}->{},{0,t}->{d,0}}]//.{a___,Except[i|o]}->{a}&,#]&;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&,c=0;{},#],x]&;F=MinimalBy[w=A@f[#/.m->{-1,t,p}];z=B@w;s[#,{-1,t,p}->m]&/@A/@Select[Permutations@Join[w,Cases[z /.i@_->i,_j,∞]],B@#==z&],Length][[1]]&

Probieren Sie es online!

Dies ist eine vierstufige Tour-de-Force, die (1) "-" durch "-1 * +" ersetzt, damit wir uns nicht mit Subtraktionen befassen müssen, (2) die Liste der Befehle ein wenig vereinfacht, ( 3) erstellt eine Liste aller Permutationen dieser Befehlsliste und wählt diejenigen aus, die beim Parsen (Ausführen) das gleiche Ergebnis liefern, und (4) vereinfacht diese Befehlslisten ein wenig und wählt die kürzesten aus, nachdem bestimmte Operationen zurück in konvertiert wurden Subtraktionen.

Dieser Code ist schrecklich ineffizient, da er die Liste aller Permutationen des Eingabecodes durchläuft. Für lange Eingabecodes empfehle ich nicht, diesen Code auszuführen. aber wie ich es lese, gibt es keine Laufzeit- oder Speicherbeschränkungen in dieser Herausforderung.

Dieser Code führt den Optimierungsschritt aus, nachdem alle "-" Operationen in "+" Operationen mit gespiegelten Vorzeichen konvertiert wurden, und führt den "-" Operator erst am Ende wieder ein, wenn der Code wieder in Zeichenfolgen konvertiert wird. Dies impliziert zum Beispiel, dass "i -1 i * + o" korrekt auf "ii - o" optimiert ist.

Da das E / A-Format ziemlich locker ist, nimmt dieser Code den Code als Listen und gibt ihn zurück, wobei die Symbole "+", "-", "*" jeweils durch p, m, t, Token dargestellt werden. Die Konvertierung von und nach Strings erfolgt in der Wrapper-Funktion von TIO:

G[S_] := StringReplace[{"p" -> "+", "m" -> "-", "t" -> "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -> p, "-" -> m, "*" -> t}]

Ungolf-Version, einschließlich des Wrappers für das String-Format und Minimierung der endgültigen Länge des Code-Strings anstelle der Anzahl der Tokens, und einige weitere Feinheiten bei der Transformation:

(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -> i, "o" -> o, "d" -> d, "+" -> p, "-" -> {-1, t, p}, "*" -> t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -> m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x < 0, p} -> {-x, m},             (* convert "y x +" to "y -x -" when x<0     *)
   {x_ /; x < 0, t, p} -> {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x<0 *)
  {"m" -> "-", "p" -> "+", "t" -> "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -> {y, t, x*y, p},  (*  "x + y *" -> "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -> x + y,              (*  "x y +" -> "(x+y)"              *)
   {x_Integer, y_Integer, t} -> x*y,                (*  "x y *" -> "(xy)"               *)
   {x_Integer, p, y_Integer, p} -> {x + y, p},      (*  "x + y +" -> "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -> {x*y, t},        (*  "x * y *" -> "(xy) *            *)
   {0, p} | {1, t} -> {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -> {i, x, p},                  (*  "x i +" -> "i x +"              *)
   {x_Integer, i, t} -> {i, x, t},                  (*  "x i *" -> "i x *"              *)
   {0, t} -> {d, 0}}] //.                           (*  "0 *" -> "d 0"                  *)
  {a___, Except[i | o]} -> {a} &, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)

Dank an @redundancy für das Erkennen eines Fehlers: Der Parser benötigt ein Expandauf die Ausgabe angewendetes Element , um die Verteilungsäquivalenz zu handhaben. 506 → 513

aktualisieren

Optimiert jetzt auch 1 o 1 + ozu 1 o 2 o. Dies war ein überraschend schwieriger Fall und machte den Code viel langsamer. 513 → 548