23
\$\begingroup\$

You find yourself on a chessboard, as one does. You can see the exit but it is awfully far away and you would rather not walk all the way. Luckily some locals have offered you a ride. A Knight, a Rook, a Bishop and a King are all willing to take you to your destination, but seeing how this is a chessboard they must each abide by the rules of chess on the way to your destination. You would like to get out of here as soon as possible, whose offer do you accept?

Task

Given a arbitrarily shaped and sized chessboard and two points on the chess board, output the chess piece that can move between the two locations in as few moves as possible. Boards will not necessarily be continuous meaning that there could be gaps between sections of the board. Each of the four pieces (King, Rook, Knight, and Bishop) can move according to their standard rules in chess. The Queen and pawn pieces have been intentionally left out of this challenge.

I/O

You may take input in any reasonable format and you may output in whatever format you choose as well. Your input and output must be self-consistent. If multiple pieces can make it to the destination in the same number of moves you must output all of the pieces that can get there in the minimum amount of time. If none of the four pieces can make it to the end you may output anything as long as it is distinct from all other possible outputs. This could include outputting nothing or throwing an error.

Test Cases

A square indicates the starting point and a circle indicates the ending point.


Test 1

Bishop


Test 2

Knight


Test 3

King


Test 4

Rook


Test 5

King, Knight


Test 6

None

\$\endgroup\$
  • \$\begingroup\$ Nice. I like this but isn't an "arbitrarily shaped and size chessboard" a single entity? I don't really see how examples 2 and 6 fit in with this as it looks like they are two separate boards which only the knight can jump between. Maybe I am missing something? \$\endgroup\$ – ElPedro Mar 16 '17 at 18:43
  • 2
    \$\begingroup\$ @ElPedro They are still a single board, its just not a continuous board. Part of arbitrary shape is that the boards can be non-continuous. \$\endgroup\$ – Sriotchilism O'Zaic Mar 16 '17 at 18:46
  • \$\begingroup\$ For example 3, shouldn't it be "king, queen"? \$\endgroup\$ – Cows quack Mar 16 '17 at 18:46
  • \$\begingroup\$ Thanks @Wheat. Not sure that was clear from the question but I understand now. \$\endgroup\$ – ElPedro Mar 16 '17 at 18:47
  • 2
    \$\begingroup\$ @KritixiLithos To keep things interesting there is no Queen or Pawn. \$\endgroup\$ – Sriotchilism O'Zaic Mar 16 '17 at 18:49
8
\$\begingroup\$

Haskell, 447 439 437 432 bytes

t=[1,2]
p=[(+),(-)]
f=filter
a=abs
(#)=elem
x?y=[min x y..max x y]
f&g=(\x->g x>>=f)
(b!1)(c,r)=f(#b)[(c!d,r#s)|(!)<-p,(#)<-p,d<-t,s<-t,d/=s]
(b!2)(c,r)=f(\(d,s)->(c==d&&all(#b)[(c,z)|z<-r?s])||r==s&&all(#b)[(z,r)|z<-c?d])b
(b!3)(c,r)=f(\(d,s)->a(c-d)==a(r-s)&&all(#b)(zip(c?d)$r?s))b
(b!4)(c,r)=f(\(d,s)->a(c-d)<2&&a(r-s)<2)b
(b%p)n s=[s]>>=foldr(&)(:[])(replicate n$b!p)
g b s e=head$f(not.null)[[p|p<-[1..4],e#(b%p)n s]|n<-[0..]]

Call using g <board> <start> <end> where <board> :: [(Int, Int)], <start> :: (Int, Int) and <end> :: (Int, Int). Returns a list containing 1 for Knight, 2 for Rook, 3 for Bishop, and 4 for King. If no solutions are found, it consistently overflows the stack (that counts as throwing an error, right?).

Inspiration taken from LYAH's chapters on Monads—(%) is just a generalized and golfed inMany, with (&) equivalent to (Control.Monad.<=<). Everything else should be more-or-less self-explanatory.

This can probably be golfed a lot more, but I've had enough fun for now.

Ungolfed:

data Piece = Knight | Rook | Bishop | King deriving (Show)
type Place = (Int, Int)
type Board = [Place]

x `to` y = [min x y..max x y]

f <=< g = (\x -> g x >>= f)

moves
    :: Board    -- available spaces
    -> Piece    -- type of piece
    -> Place    -- starting place
    -> [Place]  -- places available in one move
moves b Knight (c,r) =
    filter (`elem` b) [(c!d, r#s) |
                       (!) <- [(+),(-)], (#) <- [(+),(-)],
                       d <- [1,2], s <- [1,2], d/=s]
moves b Rook   (c,r) =
    filter (\(d,s) -> (c == d && all (`elem` b) [(c,z) | z <- r `to` s])
                    || r == s && all (`elem` b) [(z,r) | z <- c `to` d]) b
moves b Bishop (c,r) =
    filter (\(d,s) -> abs(c-d) == abs(r-s)
                && all (`elem` b) (zip (c `to` d) (r `to` s))) b
moves b King   (c,r) =
    filter (\(d,s) -> abs(c-d) <= 1 && abs(r-s) <= 1) b

canGoIn
    :: Board    -- available spaces
    -> Piece    -- type of piece
    -> Int      -- number of moves
    -> Place    -- starting place
    -> [Place]  -- places available in the specified number of moves
canGoIn b p n s =
    return s >>= foldr (<=<) return (replicate n (moves b p))

quickestPieces
    :: Board    -- available spaces
    -> Place    -- starting place
    -> Place    -- ending place
    -> [Piece]  -- quickest pieces
quickestPieces b s e =
        head $ filter (not.null)
            [[p | p <- [Knight, Rook, Bishop, King], elem e (canGoIn b p n s)] |
                n<-[0..]]
\$\endgroup\$
  • \$\begingroup\$ Nice use of functional programming! \$\endgroup\$ – Sriotchilism O'Zaic Mar 17 '17 at 4:44
5
\$\begingroup\$

Mathematica, 326 325 bytes

Thanks to masterX224 for pointing out a byte savings!

f[g_,w_,x_]:=(c={{1,1},{-1,1}};s=c.c/2;e=#<->#2&@@@#&;j=Join;h=FindShortestPath;t=#~Tuples~2&;a@d_:=e@Select[t@g,#-#2&@@#==d&];y@k=j@@(a/@j[s,c]);y@n=j@@(a/@{{1,2},{2,1},{-2,1},{-1,2}});v=Flatten[e@t@#&/@ConnectedComponents@a@#&/@#]&;y@r=v@s;y@b=v@c;Pick[p={b,k,n,r},z=Length[h[y@#,w,x]/.h@__->0]&/@p,Min[z~Complement~{0}]]);

Defines a function f taking three arguments: g is a list of ordered pairs of integers representing the board, and w and x ordered pairs representing the start and end squares. The output is the subset of {b, k, n, r} (representing bishop, king, knight, and rook, respectively) which have a minimal-moves path between the two squares. For example, the third test case is invoked by f[{{0, 0}, {1, 1}, {1, 2}, {0, 3}}, {0, 0}, {0, 3}] and returns {k}; the last two test cases return {k, n} and {}, respectively.

The strategy is to translate the squares of the board into vertices of a graph, where the edges are determined by each piece's moves, and then use built-in graph routines.

More user-friendly version of the code:

 1  f[g_, w_, x_] := ( c = {{1, 1}, {-1, 1}}; s = c.c/2;
 2    e = # <-> #2 & @@@ # &; j = Join; h = FindShortestPath; t = #~Tuples~2 &; 
 3    a@d_ := e@Select[t@g, # - #2 & @@ # == d &]; 
 4    y@k = j @@ (a /@ j[s, c]); 
 5    y@n = j @@ (a /@ {{1, 2}, {2, 1}, {-2, 1}, {-1, 2}}); 
 6    v = Flatten[e@t@# & /@
 7         ConnectedComponents@a@# & /@ #] &;
 8    y@r = v@s; y@b = v@c; 
 9    Pick[p = {b, k, n, r}, 
10      z = Length[h[y@#, w, x] /. h@__ -> 0] & /@ p, 
11      Min[z~Complement~{0}]]
12  );

In line 3, Select[g~Tuples~2, # - #2 & @@ # == d finds all ordered pairs of vertices whose difference is the vector d; e then transforms each such ordered pair into an undirected graph edge. So a is a function that creates edges between all vertices that differ by a fixed vector.

That's enough to define, in lines 4 and 5, the king's graph y@k (which takes the union of edges generated by the vectors {1, 1}, {-1, 1}, {0, 1}, and {-1, 0}) and the knight's graph y@n (which does the same with {1, 2}, {2, 1}, {-2, 1}, and {-1, 2}).

In line 7, ConnectedComponents@a@# takes one of these neighbor graphs and then finds its connected components; this corresponds to grouping all line segments of vertices in the given direction (so that a rook or bishop doesn't have to move through them one by one). Then e@t@# on line 6 puts edges between every pair of vertices in the same connected component, which are then Flattened into a single graph. Thus lines 6 through 8 define the rook's graph y@r and the bishop's graph y@b.

Finally, lines 9 through 11 choose the elements of {b, k, n, r} that yield the shortest path between the two target vertices. FindShortestPath will throw an error and return unevaluated if a target vertex doesn't appear in the graph (which will happen if no edges emanate from it), so we use h@__ -> 0 to return 0 in those cases instead. And the lack of a path between valid vertices returns a list of length 0, so Min[z~Complement~{0}] calculates the length of the smallest path that actually exists, ignoring the bad cases above.

\$\endgroup\$
  • \$\begingroup\$ any reason for double f in the function name? or is it a mathematica limit? \$\endgroup\$ – masterX244 Mar 17 '17 at 9:49
  • \$\begingroup\$ oh, haha, no it's a mental limit on my part :) I had an f in that session already, but I should have changed it before submission! \$\endgroup\$ – Greg Martin Mar 17 '17 at 17:15

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.