Memecahkan Ice Maze

Labirin es telah menjadi salah satu kebutuhan pokok gim Pokémon saya sejak debut mereka di Pokémon Gold and Silver. Tugas Anda adalah membuat program yang memecahkan masalah jenis ini.

Labirin es terutama terdiri dari, seperti namanya, es. Setelah pemain bergerak ke arah di atas es, mereka akan terus bergerak ke arah itu sampai mereka bertabrakan dengan beberapa rintangan. Ada juga tanah yang dapat dipindahkan secara bebas dan akan menghentikan pemain yang bergerak melewatinya. Rintangan terakhir adalah batu. Stone tidak dapat menempati ruang yang sama dengan pemain dan jika pemain mencoba untuk pindah ke dalamnya mereka akan berhenti bergerak sebelum mereka bisa.

Anda akan menerima wadah nilai dua dimensi, seperti daftar daftar atau string yang dipisahkan oleh baris baru, yang berisi 3 nilai berbeda untuk masing-masing dari 3 jenis lantai (Es, Tanah, dan Batu). Anda juga akan menerima dua pasangan (atau dua wadah bernilai setara lainnya) yang mengindikasikan koordinat awal dan tujuan dalam labirin. Ini mungkin nol atau satu diindeks.

Anda harus mengeluarkan daftar gerakan (4 nilai berbeda dengan bijih ke N, E, S, W) yang akan menyebabkan pemain tiba di akhir saat dijalankan.

Input akan selalu memiliki batas batu yang tertutup di sekitar labirin sehingga Anda tidak perlu khawatir tentang pemain yang keluar dari labirin

Ini adalah kode-golf sehingga byte paling sedikit menang

Uji Kasus

Di sini .akan mewakili es, ~akan mewakili tanah, dan Oakan mewakili batu. Koordinat 1 diindeks. Setiap huruf dalam solusi mewakili arah yang dimulai dengan huruf itu (misalnya N= Utara)

Memasukkan

OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Keluaran

Memasukkan

OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

Start : 15,12
End   : 16,8

Keluaran

N,W,N,E,N,E,S,W,N,W,S,E,S,E,N,E,N

Memasukkan

OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

Start : 2,2
End   : 14,3

Keluaran

E,S,S,W,N,E,N

Memasukkan

OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Start : 2,2
End   : 11,11

Keluaran

E,E,E,E,E,S,S,E,N,W,S,E,N,N,N

code-golf grid path-finding maze Wisaya Gandum
sumber

Apakah input akan selalu memiliki setidaknya satu solusi yang valid?

Pavel

@Pavel Anda bisa berasumsi begitu.

Wheat Wizard

Apakah kotak uji (baris, kolom) atau (kolom, baris)? 1 atau 0 diindeks? Apakah tepi papan dihitung sebagai dinding?

MildlyMilquetoast

Terkait

Peter Taylor

@busukxuan Anda dapat secara permanen terperangkap di dalam labirin (lihat testcase 1)

Wheat Wizard

Jawaban:

Mathematica, 247 byte

(p=x#[[##&@@x]];m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};e=Flatten[Table[#->c,{c,a@#}]&/@g,1];Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]])&

Dengan jeda baris:

(
p=x#[[##&@@x]];
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]
)&

Gagasan langsung saya adalah untuk mewakili posisi es dan tanah sebagai simpul dalam grafik dengan tepi terarah sesuai dengan gerakan hukum, lalu gunakan FindPath. Orang mungkin berpikir bahwa menentukan langkah hukum akan menjadi bagian yang mudah dan menemukan solusinya akan menjadi bagian yang sulit. Bagi saya, itu kebalikannya. Terbuka untuk saran tentang cara menghitung tepi.

Argumen pertama #adalah array 2D di mana 0mewakili es, 1mewakili tanah, dan 2mewakili batu.

Argumen kedua #2dan argumen ketiga #3adalah titik awal dan akhir, masing-masing, dalam formulir {row,column}.

adalah 3 byte yang U+F4A1mewakili karakter penggunaan pribadi \[Function].

Penjelasan

p=x#[[##&@@x]];

Menentukan fungsi pyang mengambil daftar xformulir {row,column}dan output #[[row,column]]; yaitu nilai es / tanah / batu pada koordinat tersebut.

m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c]

Menentukan fungsi myang mengambil posisi awal cdan arah vektor vdan secara rekursif menentukan di mana Anda akan berakhir. Jika c+ves, maka kami terus meluncur dari titik itu, jadi itu kembali m[c+v,v]. Jika c+vtanah, maka kita bergerak ke c+vdan berhenti. Kalau tidak (jika c+vbatu atau di luar batas), Anda tidak bergerak. Perhatikan bahwa ini hanya dimaksudkan untuk dipanggil pada posisi es atau tanah.

g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];

Menentukan daftar gposisi es dan tanah ( pnilainya kurang dari 2).

a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};

Mendefinisikan fungsi ayang mengambil posisi awal cdan kembali hasil bergerak di {1,0}, {-1,0}, {0,1}, dan {0,-1}arah. Mungkin ada redundansi. Sekali lagi, ini diasumsikan csesuai dengan es atau tanah.

e=Flatten[Table[#->c,{c,a@#}]&/@g,1];

Menentukan daftar etepi terarah yang mewakili langkah hukum. Untuk setiap posisi #dalam g, hitung tabel tepi #->cuntuk setiap cin a@#. Kemudian karena kita akan berakhir dengan sublist untuk setiap posisi #, saya meratakan tingkat pertama. Mungkin ada beberapa loop dan banyak sisi.

Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]

Graph[e]adalah grafik di mana simpul adalah posisi hukum (es atau tanah) dan ujungnya mewakili gerakan hukum (mungkin menabrak batu dan tidak bergerak). Kami kemudian gunakan FindPathuntuk menemukan jalur dari #2untuk #3diwakili sebagai daftar node. Karena FindPathdapat mengambil argumen tambahan untuk menemukan lebih dari satu jalur, hasilnya akan benar-benar menjadi daftar yang berisi jalur tunggal, jadi saya mengambil elemen pertama menggunakan [[1]]. Lalu saya mengambil berturut-turut Differenceskoordinat dan Normalizemereka. Jadi ke atas {-1,0}, ke bawah, ke {1,0}kanan {0,1}dan ke kiri {0,-1}.

Uji kasus

ngenisis
sumber

JavaScript (ES6) 180 183

(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

Menggunakan BFS , seperti yang saya lakukan untuk mengatasi tantangan terkait ini

Input
Peta labirin adalah string multiline, menggunakan Oatau 0untuk batu, 8untuk tanah dan setiap angka bukan nol kurang dari 8 untuk es ( 7terlihat bagus).
Posisi awal dan akhir berbasis nol.

Output
Daftar offset, di mana -1 adalah W, 1 adalah E, negatif kurang dari -1 adalah Ndan positif lebih besar dari 1 adalahS

Kurang golf

(m,[x,y],[t,u])=>{
  o=~m.search`\n`
  s=[[x-y*o,[]]]
  k=[]
  for(i=0; [p,l]=s[i++], k[p]=1, t-u*o != p;)
  {
    [-1,o,1,-o].map(d=>(
      M=p=>+m[p+=d] ? m[p]<8 ? M(p) : p : p-d,
      q=M(p),
      k[q]||s.push([q,[...l,d]])
    ))
  }
  return l
}

Uji

Solve=
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

function Go(maze) {
  var map = maze.textContent;
  var [sx,sy, dx,dy] = map.match(/\d+/g)
  --sx, --sy // zero based
  --dx, --dy // zero based
  map = map.split('\n').slice(1).join('\n') // remove first line
  var result = Solve(map.replace(/\./g, 7).replace(/~/g, 8), [sx,sy], [dx,dy])
  S.textContent = result
  Animate(maze, map, result, sx, sy)
}

function Display(maze, map, pos) {
  var row0 = maze.textContent.split('\n')[0]
  map = [...map]
  map[pos] = '☻'
  maze.textContent = row0+'\n'+map.join('')
}

function Animate(maze, map, moves, x, y) {
  console.log('A',moves)
  var offset = map.search('\n')+1
  var curPos = x + offset * y
  var curMove = 0
  var step = _ => {
    Display(maze, map, curPos)
    if (curMove < moves.length) 
    {
      curPos += moves[curMove]
      if (map[curPos] == 'O')
      {
        curPos -= moves[curMove]
        ++curMove
      }  
      else 
      {
        if (map[curPos] == '~') {
          ++curMove
        }
      }
      setTimeout(step, 100)
    }
    else
      setTimeout(_=>Display(maze,map,-1),500)
  }
  step()
}

td { 
  border: 1px solid #888;
}

Select maze<pre id=S></pre>
<table cellspacing=5><tr>
<td valign=top><input type=radio name=R onclick='Go(M1)'><br>
<pre id=M1>3,3 to 3,2  
OOOOO
OO.OO
O...O
OOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M2)'><br>
<pre id=M2>15,12 to 16,8
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M3)'><br>
<pre id=M3>2,2 to 14,3
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M4)'><br>
<pre id=M4>2,2 to 11,11
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO</pre></td>
</tr></table>

Luaskan cuplikan

edc65
sumber