13
\$\begingroup\$

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 foo and b4b5d4d5f4f5g3h5 corresponds to the position foo

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ What color squares does the bishop go on? \$\endgroup\$ – Embodiment of Ignorance Feb 13 at 21:00
  • 2
    \$\begingroup\$ Your 2nd last test case contradicts your spec. You also need to explain how "each pair of characters can be interpreted as a square on a chessboard". \$\endgroup\$ – Shaggy Feb 13 at 21:58
  • 1
    \$\begingroup\$ a1b2c3d4d5f5f4g3g4h2b5 is not strong against bishops, since a bishop can get to h5, then go down to d1 \$\endgroup\$ – Embodiment of Ignorance Feb 13 at 23:05
  • 2
    \$\begingroup\$ @TRITICIMAGVS, Ourous: I've clarified that both the pawns and the bishop are white, so neither is allowed to capture (or land on, or move through, or jump over) the other. \$\endgroup\$ – Quuxplusone Feb 14 at 15:25
  • 1
    \$\begingroup\$ Also, could you add an example for one of the truthy test cases. Because I understand that the squares of the password are filled with white pawns, but I don't understand where the white bishop is placed. And if any place is fine, why can't it travel to each row 1 through 8 in the first test case? It cannot travel to each column, since the a column is completely filled with pawns, but it can travel to each row without a problem, can it not? I have the feeling I'm missing something.. :S \$\endgroup\$ – Kevin Cruijssen Feb 15 at 8:43
4
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Nice. q=r=1 would be shorter than q=1 r=1, right? And if r: shorter than if r>0:. \$\endgroup\$ – Quuxplusone Feb 17 at 2:14
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ @JoKing thanks! There's still whitespace before two fors that I couldn't see how to remove. I found that replacing range(99) with repr(f) works on my local machine but not on tio.run's interpreter... but then I found that [1]*99 was shorter anyway! So that saved 4 more bytes. \$\endgroup\$ – Quuxplusone Feb 18 at 20:48
  • \$\begingroup\$ whitespace before two fors that I couldn't see how to remove — Oh! Apparently Python treats 33for as two tokens (whereas for33 would be one token). Today I learned. Minus 2 more bytes, then. \$\endgroup\$ – Quuxplusone Feb 18 at 22:58
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Seems to incorrectly return True for a1b1c1d1e1f1g1? Not that I understand anything about how it works. :) \$\endgroup\$ – Quuxplusone Feb 18 at 21:35
  • 2
    \$\begingroup\$ @Quuxplusone I had a brain-fart and thought white bishops only used white squares. I've also added an explanation. \$\endgroup\$ – Οurous Feb 18 at 21:48
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ A few tips: True and False can be 1>0 and 0>1 respectively. p[1]@#&/@ is equivalent to just p@1/@. Sequence@@ can be replaced with ##&@@. Instead of {LetterNumber[#[[1]]],FromDigits[#[[2]]]}&/@, you can use {LetterNumber@#,FromDigits@#2}&@@@. \$\endgroup\$ – Doorknob Feb 17 at 23:44
  • \$\begingroup\$ @Doorknob thanks! Code golfing is teaching me all sorts of new things about Mathematica. I still don't 100% understand p@1/@, but I see the general idea. I suppose p@1 = StringPartition[#,1]&, it's slightly confusing to me I guess because p takes two arguments two different ways, one as m_ and the other as #...&, I guess this is just a matter of precedence. It makes sense though that p@m = p[m]. \$\endgroup\$ – Kai Feb 18 at 4:46
  • \$\begingroup\$ It has for me as well! The main change there is that for any function f that takes a single argument, f@#& has the same behavior as just f -- here, f is p[1]. (Then I changed the [] notation to @, which is always identical except for precedence.) \$\endgroup\$ – Doorknob Feb 18 at 5:29
  • \$\begingroup\$ @JoKing that's devious, this is more complicated than I first thought, having to consider backwards movements as well. Thanks \$\endgroup\$ – Kai Feb 18 at 6:06
  • \$\begingroup\$ @JoKing wrote a new one which accounts for backtracking. \$\endgroup\$ – Kai Feb 19 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.