Passwords Strong Against Bishops

Question

Not to be confused with Password Bishop Goodness!

Given a string, answer (truthy/falsy or two consistent values) if it constitutes a password which is strong against bishops.

A password is strong against bishops if it is a string consisting of alternating letters (in a-h) and digits (in 1-8) such that each pair of characters can be interpreted as a square on a chessboard, and if you place a white pawn on each square named in the password, then there is no way for a white bishop to travel, in any number of consecutive moves, from any square in the first (1) row to any square in the last (8) row.

Examples

Passwords strong against bishops

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

For example, a1b1c1d1e1f1g1a8b8c8d8e8f8g8 corresponds to the position and b4b5d4d5f4f5g3h5 corresponds to the position

Passwords weak against bishops

• a4c4e4g4g5d6f6e3d2b2 (well-formed but not strong — thanks Jo King for this example!)
• b1c1d1e1f1g1h1a8b8c8d8e8f8g8 (well-formed but not strong)
• h4g4f4e4c4b4a4c3 (well-formed but not strong)
• d4 (well-formed but not strong)
• b4b5d4d5f4f5g2h5 (well-formed but not strong)
• correct horse battery staple (ill-formed)
• 1a1b1c1d1e1f1g8a8b8c8d8e8f8g (ill-formed)
• a (ill-formed)
• aa (ill-formed)

Answer 1

Ruby, 115 182 163 bytes

->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]}

Try it online!

Returns 1 for strong and nil for weak. (The +67 bytes was for taking into account "backtracking.")

->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
}

A few tricks that were used:

• Instead of the numerical range 0..99, we use the string range '00'..'99' so that the number is automatically left-padded to 2 digits and stringified. This makes out of bounds checking very short -- match with regex /[09]/.

• Inside the helper function, while building the list of new coordinates [x-11, x-9, x+9, x+11], we simultaneously assign z[x] to 9 in the process, which happens to be a truthy value (marking the square visited).

• In the last line, we want to check that the array z[81,9] does not contain 9. We do this by removing all instances of 9 (z[81,9]-[9]), then asking for the 9th element of the resulting array ([8]). Since we know the array originally had 9 elements, if any were removed, we'll get nil, whereas if they all remained, we'll get the last element of the array (which happens to always be 1).

Answer 2

Python 2, 330 318 313 309 370 bytes

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

Try it online!

Try practical version online! (original can take 4^32 operations to check completely, I suggest using this one - same number of bytes)

Not a super short solution - I couldn't figure out how to make a lambda function version of g shorter than g itself.

-4 bytes thanks to Quuxplusone

+61 bytes accounting for backtracking (thanks for pointing that out Jo King and for the golfing tips)

Answer 3

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)

Try it online!

This works by "flood-fill." First we create a list a of which squares are adjacent to which other squares, bishopwise. Then we create a set x of exclusions (based on the password). Then we initialize a set r of reachable squares, which starts out as just the first row (minus any exclusions), and repeatedly "flood" outward from there, 99 times, which should be more than enough. Finally, we test to see if any of the squares in the last row ended up in our reachable set. If so, we have a weak password! If not, we have a strong password.

Disadvantage, perhaps disqualifying (I don't know the usual rule here): If the password is ill-formed (such as "correct horse battery staple"), then we throw an exception instead of returning False. But we do always return True iff the password is strong!

Minus 16 bytes thanks to Jo King. We inline a in the one place it's used, and constant-fold some math.

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)

Answer 4

Wolfram Language (Mathematica), 339 316 358 353 345 bytes

-23 bytes thanks to @Doorknob.

+42 bytes accounting for backtracking.

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]

Try it online!

I rewrote most of this to account for backtracking, I think there may be an easier way to define the graph g, Mathematica has GraphData[{"bishop",{8,8}}] which is the graph of all moves a bishop can make on a chessboard (Bishop Graph), but this graph includes connections further than nearest diagonal neighbor. If anyone knows a shorter way to do that let me know. Credit for the graph construction goes to this MathematicaSE answer.

Returns True for strong passwords, False for weak/ill-formed passwords. Note that for most of the ill-formed passwords it will produce a bunch of error messages and then return False. If this is not in line with the rules then they can be suppressed by changing f[n_]:=... to f[n_]:=Quiet@... costing 6 bytes.

Ungolfed:

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]

Breakdown:

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

Takes a string argument and splits it into a list of strings each of length m.

Check[...,False]

Returns False if any error messages are produced, which is how we catch the ill-formed strings (i.e. assume they are well-formed, inevitably producing an error down the line).

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

Takes the string of pawn positions and splits it such that "a2h5b" becomes {{"a","2"},{"h","5"},{"b"}}, then LetterNumber will convert the letter to a number (a -> 1, etc) and FromDigits converts the numeral into an integer. If the string is not well formed, this step will produce an error which will be caught by Check, returning False. These two numbers are then converted to an integer corresponding to a square on the board.

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

Constructs the graph of all nearest-neighbor diagonal edges with the pawn positions deleted.

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

These are lists of unoccupied starting and ending vertices respectively

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

Loops over the starting and ending vertices, for each pair FindPath will be a list of paths between them. If there are no paths between them, it will be an empty list, so Length@ returns 0. If there are no paths at all, then m will be zero, and we return True, otherwise return False.

Answer 5

Clean, 285 bytes

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))

$[]

Try it online!

$[] is $ :: [[Int]] [Char] -> Bool composed with the first argument, giving \ [Char] -> Bool.

The function works by consuming the string two characters at a time, immediately returning false if the string is in an invalid format as soon as it sees the invalid part. Once the string has been processed, it places a bishop on every empty square on one side of the board and moves them in every way possible 64 times and checks if any of the end positions is in the target row.