Labirin catur

14

Potongan-potongan catur (raja, ratu, benteng, uskup, dan ksatria) dan pion ada di papan, tetapi tidak di kotak a1 atau h8 . Tugas Anda adalah melakukan perjalanan dari a1 kosong ke kotak h8 kosong , hanya melewati kotak kosong. Aturan pergerakan adalah sebagai berikut:

  1. Anda dapat melanjutkan dari setiap kotak kosong ke kotak kosong di sebelahnya (peringkat yang sama, file berikutnya atau sebelumnya; atau file yang sama, peringkat berikutnya atau sebelumnya).
  2. Anda dapat melanjutkan dari sembarang kotak kosong ke kotak kosong mana saja secara diagonal di sebelahnya (pangkat berikutnya atau sebelumnya, berikutnya atau sebelumnya), asalkan kotak kati-sudut berisi (a) dua pion atau (b) pion / potongan yang berlawanan warna. (Dua potong non-bidak, atau non-bidak dan bidak, dengan warna yang sama cukup kuat untuk menghalangi kemajuan Anda di sudut, tetapi dua bidak tidak; dan bidak / bidak dengan warna yang berlawanan tidak bekerja di konser untuk menghalangi jalan Anda.) Misalnya, jika Anda menggunakan c4 dan d5 kosong, Anda dapat melanjutkan ke itu asalkan c5 dan d4 berisi pion atau berisi potongan / pion dengan warna yang berlawanan. Lihat bagian "Contoh diagonal", di bawah, untuk gambar.

Memasukkan

Deskripsi papan FEN . Yaitu: Input akan berupa string yang mencakup deskripsi peringkat 8 , garis miring ( /), deskripsi peringkat 7 , garis miring, ..., dan deskripsi peringkat 1 . Deskripsi setiap peringkat terdiri dari angka dan huruf yang berjalan dari file a ke file h , di mana huruf menunjukkan potongan dan pion (yang hitam adalah p= pion, n= ksatria, b= uskup, r= benteng, q= ratu, k= raja, dan putih yang merupakan versi kapital dari yang sama) dan angka-angka menunjukkan jumlah kuadrat kosong berturut-turut. Sebagai contoh, rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNadalah papan setelah satu langkah (pion raja ke e4) dalam permainan catur.

a1 dan h8 akan kosong dalam input; yaitu, garis miring pertama memiliki angka di depannya, dan garis miring terakhir memiliki angka di belakangnya.

Keluaran

Truthy or falsey, menunjukkan apakah berhasil menuju h8 adalah mungkin.

Jika input bukan deskripsi papan FEN yang valid (artinya, yang cocok dengan penjelasan saya di atas), atau jika a1 atau h8 ditempati, maka outputnya bisa apa saja atau tidak sama sekali. (Dengan kata lain: Anda dapat menganggap input memenuhi persyaratan di atas.)

Mencetak gol

Ini adalah kode golf: byte paling sedikit menang.

Contoh input dan output

Perhatikan bahwa kode Anda harus bekerja untuk semua input yang valid, tidak hanya contoh.

Tambahkan spasi dan wsetelah setiap FEN untuk memvisualisasikannya di http://www.dhtmlgoodies.com/scripts/chess-fen/chess-fen-3.html. (Perhatikan bahwa beberapa visualisator FEN online lainnya tidak akan mengizinkan papan yang ilegal dalam catur, misalnya dengan pion pada peringkat 1 atau 8 , jadi tidak dapat digunakan untuk tujuan kita.)

Contoh yang benar

  • 8/8/8/8/8/8/8/8 - papan kosong
  • 1p1Q4/2p1Q3/2p1Q3/2p1Q3/2p1Q3/2p1Q3/Q1p1Q3/1q3q2- ada jalur a1 , b2 , b3 , b4 , b5 , b6 , b7 , c8 , d7 , ( bukan e8 , yang diblokir, tetapi) d6 , d5 , d4 , d3 , d2 , d1 , d1 , e1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , g8 , h8
  • 8/8/KKKKK3/K3K3/K1K1p3/Kp1K4/K1KK4/2KK4 - contoh di mana kotak yang diblokir pada satu titik harus melewati nanti (untuk memastikan Anda tidak menetapkan kotak sebagai tidak bisa dilewati)
  • K1k1K1K1/1K1k1K1k/K1K1k1K1/1k1K1K1k/K1k1K1k1/1K1k1k1K/K1K1k1K1/1k1k1K1k- ada satu jalur yang dilalui (cukup ikuti hidung Anda: hanya ada satu kotak untuk bergerak pada setiap langkah, kecuali jika mengambil langkah mundur); ini juga merupakan contoh di mana kotak diblokir pada satu titik tetapi perlu nanti

Contoh-contoh Falsey

  • 6Q1/5N2/4Q3/3N4/2Q5/1N6/2Q5/1N6 - setiap upaya di jalan harus melewati dua potongan warna yang sama terletak secara diagonal
  • N1q1K1P1/1R1b1p1n/r1B1B1Q1/1p1Q1p1b/B1P1R1N1/1B1P1Q1R/k1k1K1q1/1K1R1P1r- satu-satunya jalan melalui diagonal a8-h1 adalah pada f2-g3 , tetapi itu akan membutuhkan jalan melalui e1-d2 atau f2-e3 , yang keduanya tidak mungkin.
  • 4Q3/4q3/4Q3/5Q2/6Q1/3QqP2/2Q5/1Q6
  • 4q3/4Q3/4q3/5q2/6q1/3qQp2/2q5/1q6

Contoh diagonal

Jika prosa di atas tidak jelas, berikut adalah beberapa gambar.

Diagonal lumayan

pion dengan warna yang sama gadai warna yang berlawanan benteng warna yang berlawanan

Diagonal yang tidak bisa dilewati

benteng dan pion dengan warna yang sama rooks dengan warna yang sama

msh210
sumber
Maaf, saya tidak yakin tentang aturan golf standar: Apa yang terjadi, jika Anda memasukkan String ilegal? Bolehkah perilaku terjadi?
alex berne
@alexberne Saya percaya ini mencakup: "kode Anda harus bekerja untuk semua input yang valid ".
Rainbolt
@alexberne, saya sudah mengedit. Apakah sudah jelas sekarang?
msh210
ya terima kasih. Saya baru di sini, jadi mungkin hal biasa bagi pegolf, tetapi bagi saya itu tidak jelas :)
alex berne
Hanya ingin mengucapkan terima kasih untuk teka-teki hebat @ msh210. Saya tidak mengerti mengapa tidak ada lebih banyak jawaban.
Joffan

Jawaban:

6

VBA 668 666 633 622 548 510 489 435 331 322 319 315 byte

Function Z(F):Dim X(7,7):While Q<64:R=R+1:V=Asc(Mid(F,R))-48:If V>9 Then X(Q\8,Q Mod 8)=(3+(V\8=V/8))*Sgn(48-V):V=1
Q=Q-V*(V>0):Wend:X(7,0)=1:For W=0 To 2E3:Q=W Mod 8:P=W\8 Mod 8:For T=Q+(Q>0) To Q-(Q<7):For S=P+(P>0) To P-(P<7):If X(S,T)=0 Then X(S,T)=(1=X(P,Q))*(6>X(P,T)*X(S,Q))
Next S,T,W:Z=X(0,7):End Function

Membaca string input menempati hingga 'Wend'. Efek samping yang bagus - ini meninggalkan string input setelah board [X] dikodekan sepenuhnya, sehingga Anda dapat meninggalkan deskripsi di bagian akhir.

Di papan kode, pion 2, potongan lainnya 3, hitam negatif. Pion dikenali oleh 'P' & 'p' memiliki kode karakter yang dapat dibagi oleh 8.

'X (7,0) = 1', pengaturan a1 dapat diakses, adalah tempat pemeriksaan path dimulai. Ini berulang kali memindai papan yang mencoba menambahkan kotak yang dapat diakses dari kotak yang ditandai dapat diakses (1) sejauh ini. Akses dan hunian diagonal diperiksa dalam IF + logic-calc yang pernah hidup dalam suatu fungsi tetapi sekarang duduk di loop tetangga bersarang. Pemeriksaan akses diagonal bergantung pada produk dari dua kotak sudut-kucing, yang hanya sebesar 6 atau lebih jika potongan-potongan ada warna yang sama dan setidaknya satu adalah potongan bukan pion.

Hubungi spreadsheet; mengembalikan nilai dalam X (0,7) - 1 jika h8 dapat diakses dan 0 jika tidak - yang Excel akui sebagai benar / salah. = JIKA (Z (C2), "ya", "tidak")

masukkan deskripsi gambar di sini

Saya mungkin terbawa dengan menggerogoti kode di atas, jadi di sini adalah versi komentar semi-ungolfed:

Function MazeAssess(F)  'input string F (FEN)
Dim X(7, 7)             'size/clear the board; also, implicitly, Q = 0: R = 0
'Interpret string for 8 rows of chessboard
While Q < 64
    R = R + 1           ' next char
    V = Asc(Mid(F, R)) - 48  ' adjust so numerals are correct
    If V > 9 Then X(Q \ 8, Q Mod 8) = (3 + (V \ 8 = V / 8)) * Sgn(48 - V): V = 1 ' get piece type (2/3) and colour (+/-); set for single column step
    Q = Q - V * (V > 0) ' increment column (unless slash)
Wend
'Evaluate maze
X(7, 0) = 1             ' a1 is accessible
For W = 0 To 2000       ' 1920 = 30 passes x 8 rows x 8 columns, golfed to 2E3
    Q = W Mod 8         ' extracting column
    P = W \ 8 Mod 8     ' extracting row
    For T = Q + (Q > 0) To Q - (Q < 7)     ' loop on nearby columns Q-1 to Q+1 with edge awareness
        For S = P + (P > 0) To P - (P < 7) ' loop on nearby rows (as above)
            If X(S, T) = 0 Then X(S, T) = (1 = X(P, Q)) * (6 > X(P, T) * X(S, Q)) ' approve nearby empty squares if current square approved and access is possible
        Next 'S
    Next 'T
Next 'W
MazeAssess = X(0, 7)    ' report result for h8
End Function

Catatan kemajuan

Sunting 1: Kode sekarang bukan sebagai 666-devilish :-D dan telah kehilangan fungsinya; Saya menemukan cara yang cukup singkat untuk menulisnya untuk menghindari biaya overhead.

Sunting 2: Lompatan besar lain ke depan, secara efektif menyelesaikan pekerjaan menghapus fungsi inc / dec, mendesah, dan menggunakan beberapa global Saya mungkin akhirnya bisa memahami ini ....

Pengkodean potongan & kotak berubah. Tidak berpengaruh pada panjang kode.

Sunting 3: Kembalinya fungsi (palsu), menghapus semua Callbyte yang mengganggu , dan beberapa tweak lainnya.

Sunting 4: Menembus 500 besar, woohoo - smooshed 3 Untuk loop menjadi 1.

Sunting 5: Jiminy Cricket, penurunan besar lainnya ketika saya melakukan dua fungsi secara bersamaan - pemeriksaan akses diagonal saya selalu berlaku untuk kotak yang berdekatan, jadi ...

Sunting 6: Holy niblicks, penurunan besar lainnya. Buh-bye ke fungsi eksternal dan dengan demikian global ... Saya telah pergi ke bawah setengah panjang aslinya diposting ....

Sunting 7: Tambahkan versi yang tidak diubah

Sunting 8: Memperbaiki proses membaca untuk beberapa dolar lebih banyak

Sunting 9: Peras beberapa ekspresi untuk beberapa tetes darah terakhir

Sunting 10: NextPernyataan komputer memberikan beberapa byte


Yang menarik, grafik papan setelah analisis aksesibilitas (nomor kode ketinggalan zaman tetapi ...) kotak yang dapat diakses berwarna hijau, kotak yang tidak dapat diakses, berwarna putih dan warna lainnya adalah potongan atau pion.

3 papan sukses 3 papan diblokir

Beberapa papan tantangan: h8 dapat diakses di keduanya:

  • P1Pq2p1 / 1P1R1R1p / 1K2R1R1 / 1p1p1p2 / p1b1b1np / 1B1B1N1k / Q1P1P1N1 / 1r1r1n2 - 10 lolos untuk menyelesaikan
  • P1P3r1 / 1P1R2r1 / 1N1R1N2 / 1P1P1P2 / 1n1p1ppp / 1B1B4 / 1b1pppp1 / 1P6 - jalur berliku
Joffan
sumber
1
Sangat bagus, dan +1, tetapi: (1) Apakah Anda yakin 960 langkah sudah cukup? (2) Dapatkah Anda menyimpan beberapa byte dengan melihat papan terbalik? If V>9 Then X(7-P,C)=akan saya pikir (bukan yang saya tahu VBA) menjadi If V>9 Then X(P,C)=.
msh210
Sebenarnya teknik itu menghemat inisialisasi P, jadi terima kasih telah bertanya :-). Dan ya, saya yakin 15 board sudah cukup; Saya melakukan cukup banyak pengecekan. Sebenarnya saya belum bisa mendorongnya melewati 10 lintasan, tetapi 640 dan 960 memiliki jumlah karakter yang sama jadi saya akan memainkannya dengan aman. TETAPI jika saya bult papan terbalik, itu BISA mengambil lebih dari 10 pass, dan mungkin lebih dari 15 - kecuali saya melintasi papan terbalik juga, yang akan memiliki overhead.
Joffan
@ msh210 1 pengamatan tambahan - 15 loop hanya cukup untuk menganalisis seluruh papan, kasus terburuk, tetapi 10 loop cukup untuk mendapatkan status h8, jadi saya memiliki margin yang besar kok. Alasannya adalah bahwa jalur pencarian bekerja jauh lebih cepat ke arah penilaian, meningkatkan baris # dan kolom # - selama jalur naik atau kanan, itu akan diselesaikan dalam satu lintasan. Ke kiri atau ke bawah hanya mendapatkan satu langkah lebih jauh per lulus.
Joffan
@ msh210 Sebagai bagian dari pembenahan pada proses membaca - yang sempit membuat fasilitas untuk meninggalkan komentar pada akhir string FEN - Saya menambahkan pembalikan papan yang Anda sarankan - beberapa papan sekarang mengambil alih 15 lintasan (hingga 17) jadi fungsi telah meningkat menjadi 30 lintasan papan.
Joffan
@Joffan Anda dapat menjatuhkan 3 Bytes dengan mengkondensasi semua instance [some non-letter character] Toke[some non-letter character]To
Taylor Scott
3

Matlab, 636 887 bytes disimpan (termasuk indentasi)

Solusi ini tidak terlalu golf, tetapi saya ingin terus maju dan memasangnya.

function[n] = h(x)
o=[];
for i=x
 b={blanks(str2num(i)),'K','k',i};o=[o b{~cellfun(@isempty,regexp(i,{'\d','[NBRQK]','[nbrqk]','p|P'}))}];
end
o=fliplr(reshape(o,8,8))
for i=1:64
 b=i-[-8,8,7,-1,-9,1,9,-7];
 if mod(i,8)==1
  b=b(1:5);
 elseif mod(i,8)==0
  b=b([1,2,6:8]);
 end
 b=b(b<65&b>0);c=o(b);dn=b(isspace(c)&ismember(b,i-[9,7,-9,-7]));
 for j=dn
  g=o(b(ismember(b,j-[-8,8,7,-1,-9,1,9,-7])));
  if ~isempty(regexp(g,'pk|kp|PK|KP|kk|KK'));c(b==j)='X';end;
 end
 Bc{i}=b(c==32);
end
n=Bc{1};
on=[];
while length(n)>length(on)
 on=n;
 for i=1:length(n)
  n=unique([n Bc{n(i)}]);
 end
end
any(n==64)
end

Membaca string papan xseperti yang ditentukan di atas dan mengubahnya menjadi lebih lengkap o, lalu temukan semua gerakan (tepi grafik) di antara spasi, lalu cari tahu pergerakan mana yang mungkin (bukan ke dalam ruang yang diisi), lalu cari tahu pergerakan mana yang mungkin terjadi " gerbang "dari dua potong untuk lewat, kemudian mencari tahu apakah gerbang terbuka (bidak, warna berlawanan) atau ditutup (warna yang sama dan termasuk non-gadai). Kemudian, ia berjalan untuk menemukan lokasi yang dapat dicapai dengan jalur dari alun-alun kiri bawah dan jika jalur dapat mencapai ruang 64, itu adalah papan Ya.

sintaks
sumber
1
Keren. Apakah Anda mengujinya terhadap contoh FEN saya dalam pertanyaan untuk memastikan itu mengembalikan hasil yang benar untuk masing-masing? Juga, karena ini adalah pertanyaan kode-golf , Anda benar-benar harus golf ini. Jika tidak ada yang lain, dapatkah Anda menyingkirkan lekukan (atau menjadikannya spasi tunggal atau tab alih-alih empat spasi)? dan / atau jatuhkan spasi di sekitar =s? (Saya tidak tahu MATLAB: mungkin itu tidak mungkin.)
msh210
Ya, dan saya mungkin melakukan itu selama istirahat berikutnya. Saya memang mengujinya terhadap semua contoh Anda dan kemudian beberapa. Haruskah saya menunjukkannya dalam beberapa cara?
sintax
Tidak tahu; Saya hanya ingin tahu.
msh210