Optimalkan Kompiler untuk Bahasa Pemrograman Notasi Polandia Reverse sederhana

24

Deskripsi

Bahasa pemrograman imajiner (IPL) menggunakan Polish Reverse Notation. Ini memiliki perintah berikut:

  • i - masukan nomor dan dorong ke tumpukan
  • o - output top non-destruktif dari stack (jumlah tetap pada stack)
  • d - buang bagian atas tumpukan
  • angka integer - dorong nomor ini ke tumpukan
  • + - * - pop dua angka dari tumpukan, melakukan operasi yang sesuai dan mendorong kembali hasilnya. Tidak ada divisi di IPL.

IPL hanya bekerja dengan bilangan bulat dan digunakan untuk perhitungan sederhana. Program IPL ditulis pada satu baris dan dipisahkan oleh spasi. String kosong adalah program IPL yang valid.

Program IPL:

i i + o 

Input dua angka, tambahkan bersama-sama dan hasilkan hasilnya.

Bilangan input dan bilangan bulat yang dapat didorong ke stack berada dalam kisaran [-999, 999], namun outputnya bisa apa saja. Jika bahasa Anda tidak mendukung angka besar, tidak apa-apa.

Format input / output

Anda dapat memilih format input / output apa pun selama jelas untuk memahami dan membaca / menulis: string, daftar, token, dll.

Tugas

Anda diberi beberapa program IPL, Anda perlu mengoptimalkannya (mengurangi panjang):

i 12 + 3 + o d 2 3 + d

Setelah optimasi akan menjadi

i 15 + o

Anda tidak harus mempertahankan status tumpukan, tetapi jumlah input dan output serta urutannya harus sesuai dengan program asli dan yang dioptimalkan.

Jadi program IPL:

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

Setelah optimasi akan menjadi

i -80 * o i 4 o i

atau

-80 i * o i 4 o i

(perhatikan bahwa Anda harus menyimpan semua input, meskipun inputnya tidak relevan).

Seharusnya tidak ada hardcoding untuk kasus uji, kode harus bekerja pada program IPL sembarang dan menghasilkan program IPL sesingkat mungkin yang memenuhi persyaratan.

Mencetak gol

Penilaian kode-golf default.

PEMBARUAN: mengubah skor menjadi penilaian kode golf murni, sesuai saran @Sanchises.

Kasus uji:

Memasukkan:

(empty string)

Output yang mungkin:

(empty string)

Memasukkan:

i 4 * 2 + 3 * 6 - o

Output yang mungkin:

i 12 * o

Memasukkan:

1 1 + o

Output yang mungkin:

2 o

Memasukkan:

i 2 + 3 + o d 2 3 + d

Output yang mungkin:

i 5 + o

Memasukkan:

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

Output yang mungkin:

-80 i * o i 4 o i

Memasukkan:

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

Output yang mungkin:

i i i i i d d d d o 

Memasukkan:

i i i 0 * * * o

Output yang mungkin:

i i i 0 o

Memasukkan:

i i i 1 * * * o

Output yang mungkin:

i i i * * o

Memasukkan:

i 222 + i 222 - + o

Output yang mungkin:

i i + o

Memasukkan:

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

Output yang mungkin:

i i i i i o 1 o

Memasukkan:

i 1 + 2 * 1 + o 

Output yang mungkin:

i 2 * 3 + o

Memasukkan:

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

Output yang mungkin:

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
Андрей Ломакин
sumber
1
Sebuah pertanyaan: dapat Anda menyederhanakan i i d oke i o i(input adalah dalam rangka dan output adalah dalam rangka) atau harus Anda tidak menyederhanakannya? (himpunan input dan output harus berurutan)
Sanchises
1
@ Tidak menjamin, input dan output harus berurutan. Jika program asli memasukkan 2 angka sebelum mengeluarkan apa pun yang dioptimalkan harus melakukan hal yang sama.
Андрей Ломакин
1
Selamat datang di PPCG! Tantangan pertama yang bagus!
Luis felipe De jesus Munoz
6
Dari review antrian , saya kira tantangan ini tidak jelas. Jika ya, beri komentar tentang alasannya.
mbomb007
2
@WW Saya pikir OP berarti bahwa Anda tidak boleh melakukan hardcode hanya pada kasus uji yang tercantum dalam pertanyaan. Anda harus mendukung input sewenang-wenang. Seharusnya tidak ada hardcoding untuk kasus uji, kode harus bekerja pada program IPL sembarang
mbomb007

Jawaban:

5

Bahasa Wolfram (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]]&

Cobalah online!

Ini adalah tour-de-force empat langkah yang (1) menggantikan "-" dengan "-1 * +" sehingga kita tidak harus berurusan dengan pengurangan, (2) menyederhanakan daftar perintah sedikit, ( 3) membuat daftar semua permutasi dari daftar perintah ini dan memilih yang memberikan hasil yang sama ketika diuraikan (dieksekusi), dan (4) menyederhanakan daftar perintah ini sedikit dan mengambil yang terpendek, setelah mengubah operasi tertentu kembali ke pengurangan.

Kode ini sangat tidak efisien karena melewati daftar semua permutasi dari kode input. Untuk kode input panjang, saya tidak merekomendasikan menjalankan kode ini; tetapi ketika saya membacanya tidak ada runtime atau batasan memori dalam tantangan ini.

Kode ini melakukan langkah pengoptimalan setelah mengonversi semua operasi "-" menjadi "+" dengan tanda terbalik, dan hanya pada akhirnya memperkenalkan kembali operator "-" ketika mengonversi kode kembali ke string. Misalnya ini menyiratkan bahwa "i -1 i * + o" dioptimalkan dengan benar untuk "ii - o".

Karena persyaratan format i / o cukup longgar, kode ini mengambil dan mengembalikan kode sebagai daftar, di mana simbol "+", "-", "*" masing-masing diwakili oleh p, m, t, token. Konversi dari dan ke string dilakukan dalam fungsi wrapper yang diberikan pada TIO:

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

Versi un-golf, termasuk pembungkus format string dan meminimalkan panjang string kode final alih-alih jumlah token, dan termasuk beberapa transformasi lebih baik:

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

Terima kasih kepada @redundancy karena telah menangkap bug: Pengurai membutuhkan a Expand diterapkan pada output untuk menangani kesetaraan distributif. 506 → 513

memperbarui

Sekarang juga mengoptimalkan 1 o 1 + ountuk 1 o 2 o. Ini adalah kasus yang sangat sulit dan membuat kode lebih lambat. 513 → 548

Roma
sumber
Sepertinya ini memberikan kesalahan pada test case i i 1 + i 1 + i 1 + i 1 + d d d d o.
Grimmy
@Gyy seperti yang saya katakan, kode ini tidak berjalan untuk masalah besar karena melewati pencarian kombinatorik yang lengkap dari ruang kode. Kesalahan Anda adalah kesalahan kehabisan memori pada TIO, dan bukan karena kode saya.
Roman
@Grimy untuk "ii 1 + d o" kode saya memberikan "iid o", yang saya anggap dioptimalkan. Untuk "ii 1 + i 1 + dd", ia memberikan "iii + d o", yang memiliki jumlah token yang sama dengan optimasi "iiidd o" yang lebih jelas. Saya belum mencoba input lagi.
Roman
Saya percaya input i 2 * i 2 * + oharus menghasilkan output yang dioptimalkan i i + 2 * o, tetapi kode ini mengembalikan input (tidak dioptimalkan).
redundansi
Terima kasih @redundancy, ini sudah diperbaiki dan contoh Anda sekarang adalah salah satu kasus uji yang disertakan.
Roman