Optimice el compilador para un lenguaje de programación de notación polaca inversa simple

24

Descripción

El lenguaje de programación imaginario (IPL) utiliza la notación inversa polaca. Tiene los siguientes comandos:

  • i - ingrese el número y empújelo a la pila
  • o - salida no destructiva en la parte superior de la pila (el número permanece en la pila)
  • d - descartar la parte superior de la pila
  • número entero : empuje este número a la pila
  • + - * - saca dos números de la pila, realiza la operación correspondiente y retrasa el resultado. No hay división en IPL.

IPL funciona solo con enteros y se utiliza para cálculos simples. Un programa de IPL se escribe en una línea y se separa por espacios. La cadena vacía es un programa de IPL válido.

Programa de IPL:

i i + o 

Introduce dos números, los suma y genera el resultado.

Los números de entrada y los enteros que se pueden empujar a la pila están en el rango [-999, 999], sin embargo, la salida puede ser cualquiera. Sin embargo, si su idioma no admite números grandes, está bien.

Formato de entrada / salida

Puede elegir cualquier formato de entrada / salida siempre que sea claro para entender y leer / escribir: cadena, lista, tokens, etc.

Tarea

Le dan algún programa de IPL, necesita optimizarlo (reducir la longitud):

i 12 + 3 + o d 2 3 + d

Después de la optimización se convertirá

i 15 + o

No tiene que conservar el estado de la pila, pero la cantidad de entradas y salidas y su orden deben coincidir con el programa original y optimizado.

Entonces, el programa IPL:

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

Después de la optimización se convertirá

i -80 * o i 4 o i

o

-80 i * o i 4 o i

(tenga en cuenta que debe guardar todas las entradas, incluso si son irrelevantes).

No debe haber una codificación rígida para los casos de prueba, el código debe funcionar en cualquier programa de IPL arbitrario y producir el programa de IPL más corto posible que cumpla con los requisitos.

Tanteo

Código predeterminado de puntuación de golf.

ACTUALIZACIÓN: cambió la puntuación a puntuación de golf de código puro, según la sugerencia de @Sanchises.

Casos de prueba:

Entrada:

(empty string)

Salida posible:

(empty string)

Entrada:

i 4 * 2 + 3 * 6 - o

Salida posible:

i 12 * o

Entrada:

1 1 + o

Salida posible:

2 o

Entrada:

i 2 + 3 + o d 2 3 + d

Salida posible:

i 5 + o

Entrada:

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

Salida posible:

-80 i * o i 4 o i

Entrada:

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

Salida posible:

i i i i i d d d d o 

Entrada:

i i i 0 * * * o

Salida posible:

i i i 0 o

Entrada:

i i i 1 * * * o

Salida posible:

i i i * * o

Entrada:

i 222 + i 222 - + o

Salida posible:

i i + o

Entrada:

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

Salida posible:

i i i i i o 1 o

Entrada:

i 1 + 2 * 1 + o 

Salida posible:

i 2 * 3 + o

Entrada:

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

Salida posible:

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
Андрей Ломакин
fuente
1
Una pregunta: ¿puede simplificar i i d oa i o i(la entrada está en orden y la salida está en orden) o no debe simplificarlo? (el conjunto de entradas y salidas debe estar en orden)
Sanchises
1
@Sanchises no, las entradas y salidas deben estar en orden. Si el programa original ingresa 2 números antes de generar algo optimizado, debería hacer lo mismo.
Андрей Ломакин
1
Bienvenido a PPCG! ¡Buen primer desafío!
Luis felipe De jesus Munoz
66
De la cola de revisión , no creo que este desafío no esté claro. Si lo hace, comente por qué.
mbomb007
2
@WW Creo que el OP significa que no debe codificar solo los casos de prueba enumerados en la pregunta. Tienes que soportar entradas arbitrarias. No debería haber una codificación rígida para casos de prueba, el código debería funcionar en cualquier programa arbitrario de IPL
mbomb007

Respuestas:

5

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

Pruébalo en línea!

Este es un recorrido de cuatro pasos que (1) reemplaza "-" con "-1 * +" para que no tengamos que lidiar con sustracciones, (2) simplifica un poco la lista de comandos, ( 3) hace una lista de todas las permutaciones de esta lista de comandos y selecciona aquellas que dan el mismo resultado cuando se analizan (ejecutan), y (4) simplifica un poco estas listas de comandos y selecciona las más cortas, después de convertir ciertas operaciones de nuevo a sustracciones

Este código es terriblemente ineficiente porque pasa por la lista de todas las permutaciones del código de entrada. Para códigos de entrada largos, no recomiendo ejecutar este código; pero mientras lo leo, no hay restricciones de tiempo de ejecución o memoria en este desafío.

Este código realiza el paso de optimización después de convertir todas las operaciones "-" a operaciones "+" con signos invertidos, y solo al final reintroduce el operador "-" cuando vuelve a convertir el código en cadenas. Esto implica, por ejemplo, que "i -1 i * + o" está correctamente optimizado para "ii - o".

Como el requisito de formato de E / S es bastante flexible, este código toma y devuelve el código como listas, donde los símbolos "+", "-", "*" están representados por p, m, t, tokens respectivamente. La conversión desde y hacia cadenas se realiza en la función de contenedor dada en TIO:

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

Versión sin golf, que incluye el contenedor de formato de cadena y minimiza la longitud de la cadena de código final en lugar del número de tokens, e incluye algunas sutilezas de transformación más:

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

Gracias a @redundancy por detectar un error: el analizador necesita un Expand aplicación a la salida para manejar la equivalencia distributiva. 506 → 513

actualizar

Ahora también se optimiza 1 o 1 + opara 1 o 2 o. Este fue un caso sorprendentemente difícil e hizo que el código fuera mucho más lento. 513 → 548

romano
fuente
Parece que esto da un error en el caso de prueba i i 1 + i 1 + i 1 + i 1 + d d d d o.
Grimmy
@Grimy como dije, este código no se ejecuta por problemas grandes porque pasa por una búsqueda combinatoria exhaustiva de espacio de código. Su error es un error de falta de memoria en TIO y no se debe a mi código.
Romano
@Grimy para "ii 1 + d o" mi código da "iid o", que considero optimizado. Para "ii 1 + i 1 + dd o" da "iii + d o", que tiene el mismo número de tokens que la optimización más obvia de "iiidd o". No he probado entradas más largas.
Romano
Creo que la entrada i 2 * i 2 * + odebería producir una salida optimizada i i + 2 * o, pero este código devuelve la entrada (no optimizada).
redundancia
Gracias @redundancy, está solucionado y su ejemplo es ahora uno de los casos de prueba incluidos.
Romano