RoboZZle interpreter

10

Tugas Anda adalah menulis juru bahasa RoboZZle. Jika Anda tidak terbiasa dengan permainan, silakan menonton video di robozzle.com atau baca deskripsi saya di bawah ini.

Robot tinggal di kotak persegi panjang berwarna merah, hijau, biru, atau hitam. Kotak hitam tidak dapat diakses. Yang lain dapat diakses dan beberapa di antaranya berisi bintang. Tujuannya adalah untuk mengumpulkan semua bintang tanpa menginjak kotak hitam atau jatuh dari peta. Robot menempati satu kotak dan menghadap ke arah tertentu - kiri, kanan, atas, atau bawah. Ini mengikuti instruksi seperti perakitan yang dikelompokkan ke dalam subrutin F1, F2, ..., F5. Instruksi adalah sepasang predikat ("tidak ada", "jika pada warna merah", "jika pada warna hijau", "jika pada warna biru") dan sebuah tindakan ("maju", "belok kiri", "belok kanan", "belok kanan", "cat merah kotak saat ini", "cat hijau", "cat biru", "jangan apa-apa", "sebut F1", ..., "panggil F5"). Panggilan ke subrutin menggunakan tumpukan dan bisa bersifat rekursif. Sama seperti dalam pemrograman konvensional, setelah instruksi terakhir dari sebuah subrutin selesai, eksekusi berlanjut dari titik di mana subrutin itu dipanggil. Eksekusi dimulai dari instruksi pertama F1 dan berlanjut sampai robot mengunjungi semua kotak dengan bintang, atau ketika robot menginjak kotak hitam atau di luar peta, atau 1000 instruksi telah dieksekusi (predikat gagal dan tindakan "tidak melakukan apa-apa") tidak masuk hitungan), atau tidak ada instruksi lagi untuk dieksekusi (stack underflow).

Input:

  • a- matriks karakter 12x16 (seperti biasanya direpresentasikan dalam bahasa Anda, mis. array string) yang menyandikan peta - '#'untuk kotak yang tidak dapat diakses (hitam), '*'untuk kotak dengan bintang, '.'untuk sisanya

  • c- matriks karakter 12x16 yang menggambarkan warna kotak yang dapat diakses - 'R'(merah), 'G'(hijau), atau 'B'(biru). Kotak yang tidak dapat diakses akan diwakili oleh surat arbitrer dari ketiganya.

  • ydan x- baris dan kolom berbasis 0 robot; a[y][x]dijamin'.'

  • d- arah robot ini menghadap: 0 1 2 3untuk kanan, bawah, kiri, atas, yaitu ke arah (y,x+1), (y+1,x), (y,x-1),(y-1,x)

  • f- string tunggal, implementasi gabungan dari F1 ... F5. Setiap implementasi adalah urutan (kemungkinan kosong) dari pasangan tindakan predikat (paling banyak 10 pasang per subrutin), diakhiri dengan'|' .

    • predikat: '_'tidak ada, 'r'merah, 'g'hijau, 'b'biru

    • tindakan: 'F'maju, 'L'belok kiri, 'R'belok kanan, 'r'cat merah, 'g'cat hijau, 'b'cat biru, '1'panggil F1, ..., '5'panggil F5, '_'jangan lakukan apa-apa

Anda tidak harus memberi nama input seperti di atas, tetapi nilainya harus seperti yang ditentukan.

Keluaran: 1(atau true) jika robot mengumpulkan semua bintang sesuai dengan aturan, 0( false) jika tidak.

Contoh :

a=["################","################","##*....*...*#.##","##.####.#####.##","##.####.#####.##","##.####*...*#.##","##.########.####","##*........*#.##","################","################","################","################"]
c=["RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRBBBBRGGGGRRRR","RRBRRRRGRRRRRRRR","RRBRRRRGRRRRRRRR","RRBRRRRRGGGBRRRR","RRBRRRRRRRRGRRRR","RRRBBBBGGGGBRBRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR"]
y=2; x=6; d=2

// and then depending on "f":
f="_FrLg2_1|_FbLrR_2||||" // result:1
f="_FrRg2_1|_FbLrR_2||||" // result:0 (stepped on a black square)
f="_FrLrL_1|_FbLrR_2||||" // result:0 (1000-step limit exceeded)
f="_FrLg2__|________||||" // result:0 (stack underflow)

Contoh lain , yang melibatkan instruksi "cat":

a=["#***************","#*###*###*###*##","#*###*###*###*##","***#***#***#***#","***#***#***#***#","*###*###*###*###","***#***#***#***#","***#***#***#***#","***#***#***#***#","*###*###*###*###","*.*#***#***#***#","***#***#***#***#"]
c=["RGGGGGGGGGGGGGGG","RBRRRGRRRGRRRGRR","RBRRRGRRRGRRRGRR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BRRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BGRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR"]
y=10; x=1; d=0
f="_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||"
// result:1

Untuk menghasilkan tes Anda sendiri, buka puzzle dari daftar di robozzle.com , cobalah untuk menyelesaikannya (atau tidak menyelesaikannya), tekan F12 di browser Anda, ketikkan di konsol JS:

r=robozzle;s=JSON.stringify;with(r.level)console.log('a='+s(Items)+'\nc='+s(Colors)+'\ny='+RobotRow+'\nx='+RobotCol+'\nd='+RobotDir+'\nf='+s(r.encodeSolution()))

dan format ulang hasilnya untuk bahasa Anda.

Kemenangan terpendek. Tidak ada celah.

ngn
sumber
1
Bisakah kita menggunakan karakter berbeda untuk mewakili data dan bukan yang disediakan?
HyperNeutrino
1
Untuk jawaban APL Anda ke tantangan "Loop it", Anda dapat mengurutkan nilai sudut terakhir dengan mengurangi besarnya kompleks.
user202729
1
@ user202729 Eh, saya tidak mengharapkan komentar tentang tantangan itu di sini :) Ide Anda berhasil, terima kasih! Saya akan mencoba menerapkannya tanpa membuat jumlah karakter terlalu memalukan.
ngn
1
Bisakah kita mengambil matriks karakter sebagai daftar pasangan lokasi dan karakter?
0
1
@ 0 'Prinsip yang saya ikuti di sini (lihat juga komentar HyperNeutrino) adalah sedekat mungkin dengan format input yang sebenarnya digunakan di robozzle.com, jadi saya khawatir seharusnya tidak menjadi daftar pasangan.
ngn

Jawaban:

5

Prolog (SWI) , 574 byte

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).
N^C^G^[P,I|R]^F^X^Y^D:-map_assoc(\=(74),G);N<1e3,get_assoc(X^Y,G,J),J>67,put_assoc(X^Y,G,78,H),T=N+1,((I\=95,(P=95;get_assoc(X^Y,C,P)))->(between(49,53,I),plus(48,M,I),nth1(M,F,Q),append(Q,R,S),T^C^H^S^F^X^Y^D;member(I,`RL`),E is(D-I//3)mod 4,T^C^H^R^F^X^Y^E;I=70,(D=0,U is X+1;D=1,V is Y+1;D=2,U is X-1;D=3,V is Y-1),(U=X;V=Y),T^C^H^R^F^U^V^D;I>97,put_assoc(X^Y,C,I,W),T^W^H^R^F^X^Y^D);N^C^H^R^F^X^Y^D).
A+C+F+L:-A*G,C*B,split_string(F,"|","",P),maplist(string_codes,P,[M|N]),0^B^G^M^[M|N]^L.

Cobalah online!

Ini mendefinisikan predikat bahwa ketika dipanggil berhasil jika semua bintang berhasil dikumpulkan dan gagal sebaliknya. Predikat mengambil argumen seperti: a+c+f+x^y^d.. adan charus berupa daftar string yang dikutip backtick, sementara fharus berupa string yang dikutip ganda.

Penjelasan

Program ini berisi tiga predikat, */2, ^/2, dan +/2. The */2predikat yang didefinisikan pada baris pertama bertanggung jawab untuk bagian dari pengolahan masukan. The ^/2predikat rekursif menghitung berapa bergerak robot langkah demi langkah dan berhasil jika robot secara hukum mengumpulkan semua bintang dan gagal sebaliknya. The +/2predikat adalah predikat utama dari program ini dan mempersiapkan masukan untuk ^/2predikat dengan beberapa bantuan dari */2predikat. Perhatikan bahwa masing-masing predikat ini secara teknis hanya membutuhkan dua argumen tetapi menggunakan operator dan pencocokan pola mereka dapat berperilaku seolah-olah mereka memiliki lebih banyak argumen (saya membahas fenomena ini lebih mendalam di sini ).

*/2

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).

Predikat ini membutuhkan dua argumen. Yang pertama adalah daftar daftar kode karakter (ini adalah bagaimana Prolog mem-parsing backtick string yang dikutip). Yang kedua adalah peta asosiatif dari titik-titik dalam peta 12x16 (diwakili sebagai X^Y) hingga 32 ditambah kode karakter yang disimpan pada titik itu dalam daftar daftar kode karakter. 32 ditambahkan ke masing-masing kode karakter sehingga untuk matriks warna itu akan mengubah karakter warna huruf besar menjadi karakter warna huruf kecil.

Cara melakukannya adalah menghasilkan daftar pasang poin dan kode karakter pada saat itu menggunakan findall/3. Kemudian digunakan list_to_assoc/2untuk membuat peta asosiatif yang sesuai dari titik ke kode karakter pada titik itu.

The findall/3predikat adalah builtin sebuah membutuhkan "template" sebagai argumen pertama, gol sebagai argumen kedua dan daftar sebagai argumen ketiga. Predikat mengisi daftar dengan semua nilai yang mungkin dari templat yang menyebabkan tujuan berhasil. Karena didahulukan operator, template yang dilewatkan ke findall/3dalam */2parsing sebagai (X^Y)-D. The -Operator merupakan sepasang dua nilai di Prolog sehingga template merupakan lokasi titik ini ( X^Y) dipasangkan dengan kode karakter 32 ditambah titik ini ( D). Perhatikan bahwa yang ^digunakan dalam mewakili titik sama sekali tidak terhubung ke ^/2predikat.

Mari kita perhatikan tujuan yang diteruskan ke findall/3predikat.

nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D) % Note that the O (oh) is not a 0 (zero)

Sasaran berisi tiga predikat yang masing-masing perlu berhasil agar sasaran berhasil. The nth0/3predikat yang digunakan dua kali digunakan untuk mendapatkan nilai pada indeks tertentu daftar (yang 0dalam namanya menunjukkan itu adalah nol diindeks). Panggilan pertama untuk menyimpan Ybaris th dari matriks karakter Osementara panggilan kedua menyimpan Xkarakter th di baris itu di C. Predikat terakhir plus/3berhasil jika dua argumen pertamanya sama dengan argumen ketiga. Ini digunakan untuk membuat kode karakter dalam pasangan 32 lebih besar dari kode karakter dalam matriks karakter yang sebagaimana dinyatakan di atas akan mengubah semua huruf besar menjadi huruf kecil.

Akhirnya, findall/3simpan semua X^Y-Dkombinasi yang menyebabkan tujuannya berhasil dalam daftar dari Lmana peta asosiatif dibangun.

Selebihnya datang segera...

0 '
sumber
4

JavaScript (ES6), 298 276 264 byte

Disimpan 8 byte berkat @ngn

Mengambil input sebagai (a,c,x,y,d,f), di mana adan cadalah array dari array karakter. Pengembalian 0atau 1.

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

Uji kasus

Berkomentar

(                                           // main function taking:
  a, c, x, y, d, f,                         //   - input variables
  k = 1e3                                   //   - k = instruction counter
) => (                                      //
  g = (                                     // g = recursive execution function, taking:
    F,                                      //   - F = subroutine id
    p = 0,                                  //   - p = instruction pointer
    s = f.split`|`[F],                      //   - s = instruction string
    r = a[y]                                //   - r = current row in a[]
  ) =>                                      //
    !k |                                    // if we've executed 1000 instructions
    !r | x & 16 ||                          // or we've felt out of the map
    r[x] < '$' ?                            // or we've reached a black square:
      2                                     //   exit with error code 2
    :                                       // else:
      /\*/.test(a) ? (                      //   if there are still some stars:
        r[x] = o = 0,                       //     mark the current cell as visited
        (I = s[p + 1], P = s[p]) &&         //     I = instruction, P = predicate
        (                                   //     if P is defined:
          P < 'b' |                         //       if the predicate is '_'
          P == c[y][x].toLowerCase()        //       or it matches the color of the cell
          && I != '_'                       //       and the instruction is not '_',
          && k-- ?                          //       then decrement k and:
            +I ?                            //         if I is '1' ... '5':
              o = g(I - 1)                  //           process call to subroutine
            :                               //         else:
              I == 'L' ?                    //           if I is 'L':
                d--                         //             turn left
              :                             //           else:
                I == 'R' ?                  //             if I is 'R':
                  d++                       //               turn right
                :                           //             else:
                  I < 'b' ? (               //               if I is not a color:
                    y += (                  //                 I must be 'F',
                      d &= 3,               //                 so make the bot advance
                      x -= ~-d % 2,         //                 by updating x
                      2 - d                 //                 and y
                    ) % 2                   //
                  ) :                       //               else:
                    c[y][x] = I             //                 paint the current cell
          :                                 //       else:
            0,                              //         do nothing
          o ||                              //       provided that o is equal to 0,
          g(F, p + 2)                       //       go on with the next instruction
        )                                   //     end of instruction execution
      ) :                                   //   else:
        1                                   //     success: return 1
  )(0) & 1                                  // initial call to the subroutine F1
Arnauld
sumber
x+='2101'[d&3]-1,y+='1210'[d&3]-1->d&=3,x+=(1-d)%2,y+=(2-d)%2
ngn
1
xberubah paling banyak 1, jadi saya pikir Anda dapat mengganti x&~15denganx&16
ngn
1

APL (Dyalog Classic) , 236 233 byte

-3 Terima kasih kepada Erik the Outgolfer

Sekarang saya telah memberikan bonus, saya memposting solusi sampel untuk tantangan saya sendiri. Ada ruang untuk perbaikan di sini - jangan ragu untuk menyalin dan golf lebih lanjut.

a c r d f←⎕⋄c819cF0,('|'1f)/⍳≢ftn0
{~(⊂r)∊⍳⍴a:0'#'=ra:0p q2f↓⍨⊃⌽t⋄(_p'|')∧×≢t:0_:∇t↓←¯1⋄(⊃⌽t)+←2⋄~p'_',rc:∇0n+←1n>999:0⋄(ra)←'.'⋄~'*'a:1r+←(q'F'11 90j1*dd+←4|'.R.L'qq'rgb':∇(rc)←qq∊⎕d:∇t,←F[⍎q]⋄∇0}0

Cobalah online!

Sama seperti di atas, diperluas dengan komentar:

io0                    0-based indices (not counted in the score)
a c r d f←⎕              decompose eval'ed input (⎕) into variables
c←819⌶c                 ⍝ make c lowercase
F←0,('|'=¯1⌽f)/⍳≢f      ⍝ split f at the '|'-s
t←n←0                   ⍝ t:stack, n:step counter
{                       ⍝ lambda
  ~(⊂r)∊⍳⍴a:0           ⍝ if the robot is off the map, return 0
  '#'=r⌷a:0             ⍝ if the robot is on a wall, return 0
  p q2f↓⍨⊃⌽t           current instruction - p:predicate, q:action
  (_p'|')∧1≥≢t:0       if at end of func and stack is empty, return 0
  _:∇t↓←¯1               if at end of func, pop from stack and recurse
  (⊃⌽t)+←2               increment program counter (top of stack)
  ~p'_',rc:∇0          if predicate doesn't match cell colour, recurse
  n+←1⋄n>999:0          ⍝ if too meany steps, return 0
  (r⌷a)←'.'             ⍝ consume star
  ~'*'∊a:1              ⍝ if no more stars left, return 1
  r+←(q≡'F')×11 9○0j1*d ⍝ if action is F, move forward
  d+←4|'.R.L'⍳q         ⍝ if action is L or R, turn left or right
  q∊'rgb':∇(r⌷c)←q      ⍝ if action is paint (r,g,b), do it
  q∊⎕d:∇t,←F[⍎q]        ⍝ if action is F1...F5, push on stack and recurse
  ∇0                    ⍝ action is nop (_), recurse
}0                      ⍝ call the lambda (argument will be ignored)
ngn
sumber
233 byte
Erik the Outgolfer
@EriktheOutgolfer diterapkan, terima kasih
ngn