Jangan bingung dengan Kata Sandi Uskup .

Diberikan string, jawab (kebenaran / kepalsuan atau dua nilai yang konsisten) jika itu merupakan kata sandi yang kuat terhadap uskup .

Kata sandi kuat terhadap uskup jika itu adalah string yang terdiri dari huruf bergantian (dalam a-h) dan digit (dalam 1-8) sedemikian rupa sehingga setiap pasangan karakter dapat diartikan sebagai kotak pada papan catur, dan jika Anda menempatkan pion putih pada setiap kotak bernama dalam kata sandi, maka tidak ada cara bagi uskup putih untuk melakukan perjalanan, dalam sejumlah gerakan berurutan, dari kotak mana pun di baris pertama ( 1) ke kotak mana saja di baris terakhir ( 8).

Contohnya

Kata sandi kuat terhadap para uskup

• a1b1c1d1e1f1g1h1
• a8b8c8d8e8f8g8h8
• a1b2c3d4d5f5f4g3g4h2b5
• h4g4f4e4c4b4a4c3e3
• a1b1c1d1e1f1g1a8b8c8d8e8f8g8
• b4b5d4d5f4f5g3h5

Misalnya, a1b1c1d1e1f1g1a8b8c8d8e8f8g8sesuai dengan posisi dan b4b5d4d5f4f5g3h5sesuai dengan posisi

Kata sandi lemah terhadap uskup

• a4c4e4g4g5d6f6e3d2b2 (terbentuk dengan baik tetapi tidak kuat - terima kasih Jo King untuk contoh ini!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (terbentuk dengan baik tetapi tidak kuat)
• h4g4f4e4c4b4a4c3 (terbentuk dengan baik tetapi tidak kuat)
• d4 (terbentuk dengan baik tetapi tidak kuat)
• b4b5d4d5f4f5g2h5 (terbentuk dengan baik tetapi tidak kuat)
• correct horse battery staple (bentuknya buruk)
• 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (bentuknya buruk)
• a (bentuknya buruk)
• aa (bentuknya buruk)

Ruby, 115 182 163 byte

->s{z=('00'..'99').map{|x|x=~/[09]/||s[(x[1].ord+48).chr+x[0]]};(11..18).map &g=->x{z[x]||[x-11,x-9,x+z[x]=9,x+11].map(&g)};s=~/^([a-h][1-8])*$/&&(z[81,9]-[9])[8]}

Cobalah online!

Pengembalian 1untuk yang kuat dan niluntuk yang lemah. (The +67 byte adalah untuk memperhitungkan "mundur.")

->s{
 z=                             # this is the board
 ('00'..'99').map{|x|           # coordinates are described as y*10 + x
  x=~/[09]/||                   # truthy if out of bounds...
  s[(x[1].ord+48).chr+x[0]]     # ...or impassable
 }                              # now only the passable squares are falsey
 (11..18).map                   # for each x position at y=1,
  &g=->x{                       # call helper function on that square
   z[x]||                       # if the square is passable (i.e. falsey),
    [x-11,x-9,x+z[x]=9,x+11]    # mark it impassable by setting to 9 (truthy)
     .map(&g)                   # call helper recursively for each neighbor
  }
 s=~/^([a-h][1-8])*$/           # make sure the input was valid,
 &&(z[81,9]-[9])[8]             # and check that the last row was never reached
}

Beberapa trik yang digunakan:

• Alih-alih rentang numerik 0..99, kami menggunakan rentang string'00'..'99' sehingga angka secara otomatis dibiarkan menjadi 2 digit dan dikelompokkan. Ini membuat di luar batas memeriksa sangat pendek - cocok dengan regex /[09]/.

• Di dalam fungsi helper, sambil membangun daftar koordinat baru [x-11, x-9, x+9, x+11], kami secara bersamaan menugaskan z[x]ke 9dalam proses, yang kebetulan merupakan nilai kebenaran (menandai kotak yang dikunjungi).

• Di baris terakhir, kami ingin memeriksa bahwa array z[81,9]tidak mengandung 9. Kami melakukan ini dengan menghapus semua instance dari 9( z[81,9]-[9]), lalu meminta elemen ke-9 dari array yang dihasilkan ( [8]). Karena kita tahu array awalnya memiliki 9 elemen, jika ada yang dihapus, kita akan dapatkan nil, sedangkan jika semuanya tetap, kita akan mendapatkan elemen terakhir dari array (yang selalu terjadi 1).

Python 2 , 330 318 313 309 370 byte

import numpy as n
b=n.ones([8,8])
q=r=1
s=input()
l=len(s)
def g(x,y=0,p=0):
    if b[y,x]and p<32:
        if y<7:
            if x<7:
                g(x+1,y+1,p+1)
                if y:g(x+1,y-1,p+1)
            if x:
                g(x-1,y+1,p+1)
                if y:g(x-1,y-1,p+1)
        else:global q;q=0
for i in range(l/2):
    x=ord(s[2*i])-97;y=ord(s[2*i+1])-49
    if y>8or y<0 or l%2or x>8or x<0:r=0
    if r:b[7-y,x]=0
map(g,range(8))
print q&r

Cobalah online!

Coba versi praktis online!(asli dapat mengambil 4 ^ 32 operasi untuk memeriksa sepenuhnya, saya sarankan menggunakan ini jumlah byte yang sama)

Bukan solusi super pendek - Saya tidak tahu cara membuat versi fungsi lambda dari g lebih pendek dari g itu sendiri.

-4 byte berkat Quuxplusone

+61 byte yang menghitung mundur (terima kasih telah menunjukkan bahwa Jo King dan untuk tips golf)

Python 2 , 490 476 474

def f(p):
 a=[set(ord(c)-33 for c in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()];x=set((ord(p[i+1])-49)*8+ord(p[i])-97 for i in range(0,len(p),2))
 r=set(range(8))-x
 for i in range(99):r=set().union(*[a[c]for c in r])-x
 return all(c<56 for c in r)

Cobalah online!

Ini bekerja dengan "mengisi banjir." Pertama-tama kita membuat daftar akuadrat mana yang berbatasan dengan kuadrat lainnya. Lalu kami membuat satu set xpengecualian (berdasarkan kata sandi). Kemudian kita menginisialisasi satu setr kotak yang dapat dijangkau, yang dimulai hanya sebagai baris pertama (minus pengecualian), dan berulang kali "banjir" keluar dari sana, 99 kali, yang seharusnya lebih dari cukup. Akhirnya, kami menguji untuk melihat apakah ada kotak di baris terakhir yang berakhir pada set yang dapat dijangkau. Jika demikian, kami memiliki kata sandi yang lemah! Jika tidak, kami memiliki kata sandi yang kuat.

Kerugian, mungkin mendiskualifikasi (saya tidak tahu aturan biasanya di sini): Jika kata sandi tidak terbentuk (seperti "baterai kuda yang benar"), maka kami membuang pengecualian alih-alih kembali False. Tapi kami selalu kembali Truejika kata sandinya kuat!

Minus 16 byte, terima kasih kepada Jo King. Kami berbaris adi satu tempat yang digunakan, dan terus-menerus melipat beberapa matematika.

def f(p):
 x=set(ord(p[i])-489+8*ord(p[i+1])for i in range(0,len(p),2));r=set(range(8))-x
 for i in[1]*99:r=set().union(*[[set(ord(k)-33for k in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()][c]for c in r])-x
 return all(c<56for c in r)

Bersih , 285 byte

import StdEnv,Data.List
$_[_]=1<0
$a[x,y:l]=case[[u,v]\\u<-[0..7],v<-[0..7]|u==toInt x-97&&v==toInt y-49]of[p]= $[p:a]l;_=1<0
$a _=all(\[_,y]=y<7)(iter 64(nub o\e=e++[k\\[u,v]<-e,p<-[-1,1],q<-[-1,1],k<-[[abs(u+p),abs(v+q)]]|all((<>)k)a&&all((>)8)k])(difference[[e,0]\\e<-[0..7]]a))

$[]

Cobalah online!

$[]adalah $ :: [[Int]] [Char] -> Boolterdiri dengan argumen pertama, memberikan \ [Char] -> Bool.

Fungsi ini bekerja dengan menggunakan string dua karakter sekaligus, segera mengembalikan false jika string dalam format yang tidak valid segera setelah melihat bagian yang tidak valid. Begitu string telah diproses, itu menempatkan seorang uskup di setiap kotak kosong di satu sisi papan dan menggerakkan mereka dengan segala cara yang mungkin 64 kali dan memeriksa apakah ada posisi akhir di baris target.

Bahasa Wolfram (Mathematica) , 339 316 358 353 345 byte

-23 byte terima kasih kepada @Doorknob.

+42 byte yang menghitung mundur.

p[m_]:=StringPartition[#,m]&;l=Range@8;f[n_]:=Check[w=(8#2+#1-8)&@@@({LetterNumber@#,FromDigits@#2}&@@@(p@1/@p[UpTo@2]@n));g=Graph[Sort/@UndirectedEdge@@@Position[Outer[EuclideanDistance@##&,#,#,1],N@Sqrt@2]&@GraphEmbedding@GridGraph@{8,8}//Union]~VertexDelete~w;c:=#~Complement~w&;m=0;Do[m+=Length@FindPath[g,i,j],{i,c@l},{j,c[l+56]}];m==0,0>1]

Cobalah online!

Saya menulis ulang sebagian besar dari ini untuk menjelaskan kemunduran, saya pikir mungkin ada cara yang lebih mudah untuk mendefinisikan grafik g, Mathematica memiliki GraphData[{"bishop",{8,8}}]grafik semua gerakan yang dapat dilakukan oleh seorang uskup di papan catur ( Grafik Uskup ), tetapi grafik ini mencakup koneksi lebih lanjut dari tetangga diagonal terdekat. Jika ada yang tahu cara yang lebih singkat untuk melakukannya, beri tahu saya. Penghargaan untuk konstruksi grafik diberikan untuk jawaban MathematicaSE ini .

Pengembalian Trueuntuk kata sandi yang kuat, Falseuntuk kata sandi yang lemah / buruk. Perhatikan bahwa untuk sebagian besar kata sandi yang tidak dibentuk dengan benar, ia akan menghasilkan banyak pesan kesalahan dan kemudian kembali False. Jika ini tidak sesuai dengan aturan maka mereka dapat ditekan dengan mengubah f[n_]:=...ke f[n_]:=Quiet@...biaya 6 byte.

Tidak Disatukan:

p[m_] := StringPartition[#, m] &;

f[n_] :=
 Check[
  w = (8 #2 + #1 - 
       8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@ 
        p[UpTo@2]@n));
  r = GridGraph[{8, 8}];
  g = Graph[Sort /@ UndirectedEdge @@@
             Position[Outer[EuclideanDistance@## &, #, #, 1],N@Sqrt@2] &@
              GraphEmbedding@r // Union]~VertexDelete~w;
  s = Complement[{1,2,3,4,5,6,7,8},w];
  e = Complement[{57,58,59,60,61,62,63,64},w];
  m = 0;
  Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
  If[m == 0,True,False]
  , False]

Kerusakan:

p[m_]:=StringPartition[#,m]& 

Membawa argumen string dan membaginya menjadi daftar string yang masing-masing panjangnya m.

Check[...,False]

Mengembalikan Falsejika ada pesan kesalahan yang dihasilkan, yang merupakan cara kita menangkap string yang terbentuk buruk (yaitu menganggap mereka terbentuk dengan baik, pasti menghasilkan kesalahan di telepon).

(8*#2 + #1 - 8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@ 
        p[UpTo@2]@n));

Mengambil string posisi gadai dan membaginya sedemikian rupa sehingga "a2h5b"menjadi {{"a","2"},{"h","5"},{"b"}}, kemudian LetterNumberakan mengubah huruf menjadi angka ( a -> 1, dll) dan FromDigitsmengubah angka menjadi bilangan bulat. Jika string tidak terbentuk dengan baik, langkah ini akan menghasilkan kesalahan yang akan ditangkap oleh Check, kembali False. Kedua angka ini kemudian dikonversi menjadi bilangan bulat yang sesuai dengan kotak di papan tulis.

r = GridGraph[{8, 8}];
g = Graph[
     Sort /@ UndirectedEdge @@@ 
          Position[Outer[EuclideanDistance@## &, #, #, 1], 
           N@Sqrt@2] &@GraphEmbedding@r // Union]~VertexDelete~w;

Buat grafik semua tepi diagonal tetangga terdekat dengan posisi pion dihapus.

s = Complement[{1,2,3,4,5,6,7,8},w];
e = Complement[{57,58,59,60,61,62,63,64},w];

Ini adalah daftar simpul awal dan akhir yang tidak dihuni masing-masing

m=0
Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
If[m == 0,True,False]

Loop atas simpul awal dan akhir, untuk setiap pasangan FindPathakan menjadi daftar jalur di antara mereka. Jika tidak ada jalur di antara mereka, itu akan menjadi daftar kosong, jadi Length@kembali 0. Jika tidak ada jalan sama sekali, maka makan menjadi nol, dan kami kembaliTrue , jika tidak kembali False.