6
\$\begingroup\$

Objective

You have two knights on a standard chessboard labelled 1-8 and A-H, one knight is located at 1C and the other at 2G. You have to write a program in the language of your choosing that accepts a set of coordinates from stdin, like 2C, and then calculates which of the two knights you have to move in order to capture the enemy pawn at the provided coordinates with the least amount of moves assuming it is standing still. The program must also output which are these moves that the knight has to make.

Example Usage

# echo 1C|./faster
Move Knight: 1C
Moves:

Also

# echo 3B|./faster
Move Knight: 1C
Moves: 1C -> 3B

One more

# echo 5A|./faster
Move Knight: 1C
Moves: 1C -> 3B
Moves: 3B -> 5A

Output shall be exactly as shown.

Useful Resources

Knight's Tour

Bonuses

You get -50 Bytes if your program is expandable and works with N knights.

\$\endgroup\$
18
  • \$\begingroup\$ You posted two challenges in rapid succession. Did you get these challenges from some external website? In that case, you should link to them. If you wrote these challenges yourself, that's rather impressive :-). \$\endgroup\$
    – Justin
    Commented Oct 2, 2015 at 16:39
  • 3
    \$\begingroup\$ Suggestion: remove the [code-challenge] tag; I think there's a [chess] tag, instead of "you get one point ..." or "you lose 50 points", remove the three points of the Scoring System and instead put under "Bonuses", "-50 chars if your code works with N knights". Also, I recommend using the sandbox in the future. \$\endgroup\$
    – Justin
    Commented Oct 2, 2015 at 16:41
  • \$\begingroup\$ @Justin I just started posting in Code Golf. I actually have a collection of them and I came up with most of them. Now some of them may be duplicates because someone else must have thought of it too, but I haven't checked. I just hope you like them.. \$\endgroup\$
    – DaKnOb
    Commented Oct 2, 2015 at 16:41
  • \$\begingroup\$ @Justin Thanks. Suggestions implemented. I'm still learning \$\endgroup\$
    – DaKnOb
    Commented Oct 2, 2015 at 16:51
  • 1
    \$\begingroup\$ The choice of squares is interesting. Because a knight always hops to an opposite coloured square, and these squares are opposite coloured, it means there is never a "draw." By convention, squares are normally labelled A1 instead of 1A, but that doesn't make any difference. \$\endgroup\$ Commented Oct 2, 2015 at 17:59

1 Answer 1

1
\$\begingroup\$

Mathematica 1183 483 bytes (or 190) bytes

Approach 1

240-50 (bonus) = 190 bytes

The knight's tour can be represented as a graph. So the issue becomes simply to find the shortest path from each knight to the pawn. Mathematica offers both KnightTourGraph and FindShortestPath as built-in functions.

w@p_:=Characters@p/.{r_,s_}:>(ToCharacterCode[s][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(v~Mod~8/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~h~k_:=Row[SortBy[(z/@FindShortestPath[8~KnightTourGraph~8,#,w@p])&/@w/@k,Length][[1]],"->"]

Examples

h["5A",{"1C","2G"}]

1C -> 3B -> 5A

h["8G",{"1C","2G"}]

2G -> 3E -> 5D -> 7E -> 8G


Approach 2

(533-50 (bonus)= 483 bytes)

Here the knight's tour graph is constructed without using KnightTourGraph.

s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less][Quotient[v-1,8]+1,#2],v+#3,Nothing]&@@@{{1,2,-17,1,1},{8,2,-15,0,1},{2,1,-10,1,1},{7,1,-6,0,1},{2,8,6,1,0},{7,8,10,0,0},{1,7,15,1,0},{8,7,17,0,0}})   
w@p_:=Characters[p]/.{r_,q_}:>(ToCharacterCode[q][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(Mod[v,8]/.{0 -> 8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~f~k_:=Row[SortBy[(z/@FindShortestPath[Graph[Range@64,Union@Flatten[s/@Range@64]],#,w@p])&/@w/@k,Length][[1]],"->"]

Explanation

Below are two views of the chessboard. On the left, each chessboard position corresponds to vertex bearing an integer name. On the right, the positions have been labelled according to the convention suggested by the OP.

In both figures, White sits on the right, Black sits on the left.

chessboards

Legal moves of a knight are paths along a knight tour graph.

The function, s, generates all 512 moves (as if each square allowed for 8 knight moves), eliminates inverses, and then weeds out the moves that would land off the board. There are 168 edges on the graph.

edges consists of a list of elements of the form, UndirectedEdge[a,b]. For instance, the edge, UndirectedEdge[1,11]corresponds to the idea that a knight at vertex 1, that is, at "A1" in standard notation, may jump to vertex 11, or "B3", and vice-versa.

toVertex takes a position (see right board) and returns a vertex (see left board). For instance toVertex["3H"] returns 59.

toChessPosition does the opposing conversion, namely from a vertex to a chess position.

vertexNames is a list of replacements: {1->"1A",2->"2A"...64->"8H"}. This is only needed for the right chessboard figure shown above.

numberedKnightsTouris the graph displayed above on the left.

chessKnightsTouris the graph displayed above on the right.

The graphs are constructed using the above-defined vertices and edges.

findShortestPath receives the position of the pawn and a list of positions of the knights and finds the shortest path along the graph from a knight to the pawn.

    s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less]
edges=Union@Flatten[s/@Range@64];
toVertex[p_]:=Characters[p]/.{rank_,file_}:> (ToCharacterCode[file][[1]]-65)*8+ToExpression[rank]
toChessPosition[v_]:=ToString@(Mod[v,8]/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
vertexNames=Thread[Range@64->(toChessPosition[#]&/@Range[64])];
numberedKnightsTour=Graph[Range@64,edges,VertexLabels->"Name",GraphLayout->"SpringEmbedding"];
vertexNames=Thread[Range[64]->(toChessPosition[#]&/@Range[64])];
chessKnightsTour=Graph[Range@64,edges,ImageSize->Large,VertexLabels-> vertexNames,GraphLayout->"SpringEmbedding"];
GraphicsGrid[{{numberedKnightsTour,chessKnightsTour}},PlotLabel->"For each board below, \nWhite sits at Right, Black at Left\nNumbers refers to rank, letters refer to file",ImageSize->Large]
    findShortestPath[pawn_,knights_]:=Row[SortBy[(toChessPosition/@FindShortestPath[chessKnightsTour,#,toVertex@pawn])&/@toVertex/@knights,Length][[1]],"->"]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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