Optimiser le compilateur pour un langage de programmation à notation polonaise inversée simple

24

La description

Le langage de programmation imaginaire (IPL) utilise la notation inversée polonaise. Il a les commandes suivantes:

  • i - entrez le numéro et poussez-le dans la pile
  • o - sortie non destructive en haut de la pile (le nombre reste sur la pile)
  • d - jeter le haut de la pile
  • nombre entier - pousser ce nombre dans la pile
  • + - * - pop deux nombres de la pile, effectuez l'opération correspondante et repoussez le résultat. Il n'y a pas de division dans IPL.

L'IPL ne fonctionne qu'avec des entiers et est utilisé pour des calculs simples. Un programme IPL est écrit sur une ligne et séparé par des espaces. La chaîne vide est un programme IPL valide.

Programme IPL:

i i + o 

Saisit deux nombres, les additionne et produit le résultat.

Les nombres d'entrée et les entiers pouvant être poussés vers la pile sont dans la plage [-999, 999], mais la sortie peut être quelconque. Si votre langue ne prend pas en charge les grands nombres, tout va bien.

Format d'entrée / sortie

Vous pouvez choisir n'importe quel format d'entrée / sortie tant qu'il est clair pour comprendre et lire / écrire: chaîne, liste, jetons, etc.

Tâche

On vous donne un programme IPL, vous devez l'optimiser (réduire la longueur):

i 12 + 3 + o d 2 3 + d

Après l'optimisation deviendra

i 15 + o

Vous n'avez pas à conserver l'état de la pile, mais la quantité d'entrées et de sorties et leur ordre doivent correspondre au programme d'origine et optimisé.

Alors programme IPL:

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

Après l'optimisation deviendra

i -80 * o i 4 o i

ou

-80 i * o i 4 o i

(notez que vous devez enregistrer toutes les entrées, même si elles ne sont pas pertinentes).

Il ne devrait pas y avoir de codage en dur pour les cas de test, le code devrait fonctionner sur n'importe quel programme IPL arbitraire et produire le programme IPL le plus court possible qui réponde aux exigences.

Notation

Score par défaut du code-golf.

MISE À JOUR: modification du score en notation de golf en code pur, conformément à la suggestion de @Sanchises.

Cas de test:

Contribution:

(empty string)

Sortie possible:

(empty string)

Contribution:

i 4 * 2 + 3 * 6 - o

Sortie possible:

i 12 * o

Contribution:

1 1 + o

Sortie possible:

2 o

Contribution:

i 2 + 3 + o d 2 3 + d

Sortie possible:

i 5 + o

Contribution:

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

Sortie possible:

-80 i * o i 4 o i

Contribution:

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

Sortie possible:

i i i i i d d d d o 

Contribution:

i i i 0 * * * o

Sortie possible:

i i i 0 o

Contribution:

i i i 1 * * * o

Sortie possible:

i i i * * o

Contribution:

i 222 + i 222 - + o

Sortie possible:

i i + o

Contribution:

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

Sortie possible:

i i i i i o 1 o

Contribution:

i 1 + 2 * 1 + o 

Sortie possible:

i 2 * 3 + o

Contribution:

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

Sortie possible:

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
Андрей Ломакин
la source
1
Une question: peut vous simplifier i i d oà i o i(l'entrée est en ordre et la sortie est en ordre) ou si vous simplifier pas? (l'ensemble des entrées et sorties doit être en ordre)
Sanchises
1
@Sanchises non, les entrées et sorties doivent être en ordre. Si le programme d'origine entre 2 nombres avant de sortir quelque chose d'optimisé, il devrait en faire de même.
Андрей Ломакин
1
Bienvenue chez PPCG! Beau premier défi!
Luis felipe De jesus Munoz
6
De la file d'attente d'examen , je ne pense pas que ce défi ne soit pas clair. Si vous le faites, veuillez expliquer pourquoi.
mbomb007
2
@WW Je pense que l'OP signifie que vous ne devez pas coder en dur uniquement les cas de test répertoriés dans la question. Vous devez prendre en charge les entrées arbitraires. Il ne devrait pas y avoir de codage en dur pour les cas de test, le code devrait fonctionner sur n'importe quel programme IPL arbitraire
mbomb007

Réponses:

5

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

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]]&

Essayez-le en ligne!

Il s'agit d'un tour de force en quatre étapes qui (1) remplace "-" par "-1 * +" afin que nous n'ayons pas à traiter les soustractions, (2) simplifie un peu la liste des commandes, ( 3) fait une liste de toutes les permutations de cette liste de commandes et sélectionne celles qui donnent le même résultat lors de l'analyse (exécutée), et (4) simplifie un peu ces listes de commandes et sélectionne la plus courte, après avoir reconverti certaines opérations en soustractions.

Ce code est terriblement inefficace car il passe par la liste de toutes les permutations du code d'entrée. Pour les codes d'entrée longs, je ne recommande pas d'exécuter ce code; mais comme je l'ai lu, il n'y a aucune restriction d'exécution ou de mémoire dans ce défi.

Ce code effectue l'étape d'optimisation après la conversion de toutes les opérations "-" en opérations "+" avec des signes inversés, et seulement à la fin réintroduit l'opérateur "-" lors de la reconversion du code en chaînes. Cela implique par exemple que "i -1 i * + o" est correctement optimisé en "ii - o".

Comme l'exigence de format d'E / S est assez lâche, ce code prend et renvoie le code sous forme de listes, où les symboles "+", "-", "*" sont représentés respectivement par p, m, t, jetons. La conversion de et vers des chaînes se fait dans la fonction wrapper donnée sur TIO:

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

Version sans golf, incluant l'encapsuleur au format chaîne et minimisant la longueur de chaîne de code finale au lieu du nombre de jetons, et incluant quelques subtilités de transformation supplémentaires:

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

Merci à @redundancy d'avoir attrapé un bug: l'analyseur a besoin d'un Expandappliqué à la sortie afin de gérer l'équivalence distributive. 506 → 513

mise à jour

Maintenant , permet d' optimiser également 1 o 1 + oà 1 o 2 o. C'était un cas étonnamment difficile et a rendu le code beaucoup plus lent. 513 → 548

romain
la source
On dirait que cela donne une erreur sur le cas de test i i 1 + i 1 + i 1 + i 1 + d d d d o.
Grimmy
@Grimy comme je l'ai dit, ce code ne fonctionne pas pour les gros problèmes car il passe par une recherche combinatoire exhaustive de l'espace de code. Votre erreur est un défaut de mémoire insuffisante sur TIO et n'est pas dû à mon code.
Roman
@Grimy pour "ii 1 + d o" mon code donne "iid o", que je considère comme optimisé. Pour "ii 1 + i 1 + dd o", cela donne "iii + d o", qui a le même nombre de jetons que l'optimisation la plus évidente "iiidd o". Je n'ai pas essayé d'entrées plus longues.
Roman
Je pense que l'entrée i 2 * i 2 * + odevrait produire une sortie optimisée i i + 2 * o, mais ce code renvoie l'entrée (non optimisée).
redondance
Merci @redundancy, c'est corrigé et votre exemple est maintenant l'un des cas de test inclus.
Roman