Catur: Raja Saya?

14

Tantangan:

Diberikan kotak-kotak, hasilkan jumlah gerakan terkecil yang diperlukan (dengan anggapan hitam tidak bergerak sama sekali) untuk menjadi raja sepotong merah, jika memungkinkan.

Aturan :

Sisi merah akan selalu berada di bagian bawah, namun bidak mereka dapat dimulai pada baris apa pun (bahkan barisan raja yang harus mereka lewati). Potongan hitam stasioner , artinya mereka tidak bergerak di antara gerakan merah, tetapi mereka dikeluarkan dari papan ketika ditangkap. Perhatikan bahwa potongan dapat dimulai pada ruang apa pun di papan tulis, termasuk tepat di sebelah satu sama lain. Ini bukan bagaimana catur normal dimainkan, tetapi program Anda harus dapat menyelesaikannya. (Lihat input 5) Namun, keping checker hanya boleh bergerak secara diagonal (lihat input 3). Pengambilan mundur dibolehkan jika penangkapan pertama maju dalam rantai (lihat input 7).

Memasukkan:

Kotak centang 8x8, dengan ruang papan ditentukan sebagai karakter berikut (jangan ragu untuk menggunakan alternatif selama konsisten):

. - Kosong

R - Potongan merah

B - Potongan hitam

Keluaran:

The terkecil jumlah bergerak itu akan mengambil sepotong merah menjadi 'kinged' dengan memasukkan baris raja pada baris atas papan (sisi hitam), 0 jika tidak ada langkah yang diperlukan (sepotong merah dimulai pada baris raja), atau angka negatif jika tidak mungkin untuk raja sepotong merah (yaitu hitam menempati seluruh baris pertama).

Input 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 1:

7

Input 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Output 2:

2

Input 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 3:

-1

Input 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 4:

0

Input 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Output 5:

4

Input 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Output 6:

2

Input 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Output 7:

4

Mencetak:

Ini adalah kode-golf , jadi kode terpendek dalam byte menang.

code-golf grid game path-finding board-game Yodle
sumber
1
Tidakkah seharusnya test case kedua menjadi 2, karena Anda dapat melipatgandakan / melompati tiga?
DJMcMayhem
Apakah keadaan array array bilangan bulat sebagai input OK?
Jonathan Allan
1
Saya menambahkan testcase lain yang seharusnya terbukti sulit. Ini melibatkan beberapa lompatan, beberapa bagian dan melompat mundur untuk mencapai solusi terbaik.
orlp
1
@ Atlp Hm, saya akan mengatakan tidak ada bagian merah yang diizinkan untuk bergerak mundur karena tidak ada dari mereka adalah raja (maka dari itu tantangannya), tetapi tampaknya beberapa orang bermain dengan aturan di mana menangkap mundur diperbolehkan oleh non- potongan raja jika penangkapan pertama adalah ke depan. Saya akan menambahkan itu ke aturan karena saya tidak mengetahui hal ini sebelumnya.
Yodle
1
ooooooooh, kamu tidak harus memilih hanya satu potong merah, mereka bisa bergabung! Saya mengerti
Greg Martin

Jawaban:

4

JavaScript (ES6), 354 322 byte

Mengambil array sebagai input dengan:

  • 0 = kotak kosong
  • 1 = potongan merah
  • 2 = potongan hitam

Mengembalikan jumlah gerakan optimal, atau 99 jika tidak ada solusi.

Ini sangat cepat tetapi bisa bermain golf lebih banyak.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});
Luaskan cuplikan

Arnauld
sumber
99 mungkin baik-baik saja, saya tidak bisa membayangkan solusi nyata mengambil 99 gerakan di papan 8x8. Pekerjaan yang baik!
Yodle