PWC 281 Knight’s Move

A Knight in chess can move from its current position to any square two rows or columns plus one column or row away. Write a script which takes a starting position and an ending position and calculates the least number of moves required.

Example 1

• Input: $start = 'g2', $end = 'a8'
• Output: 4
• g2 -> e3 -> d5 -> c7 -> a8

Example 2

• Input: $start = 'g2', $end = 'h2'
• Output: 3
• g2 -> e3 -> f1 -> h2

Strategize

If you didn’t immediately start humming “Night Moves” by Bob Seger, well, then you, uh, probably aren’t as old as I am. “… How far off, I sat and wondered … Ain’t it funny how the night moves …”

It’s a shortest-path problem. The classic computer science solution is a breadth-first search, mildly complicated by the weird L-shaped moves of the knight and the chess notation. As early answers trickled in, I saw that everyone appeared to be going down this path, and I sighed and thought about all the ways I was going to mess this up until I beat it into submission with the debugger.

But here’s a different way to approach the problem. Let’s place a knight in the bottom left corner (a1) and label that corner 0. From here, there are two possible knight moves; let’s label them with 1. Then, for each of the 1s, let’s label the possible knight moves from there with a 2.

If we continue doing this until the 8×8 grid fills up, the board will look like this:

We have a lookup table. If we place the start point at a1, then we can read the move count directly out of the table at the end point. Well, mostly, assuming the end point is above and to the right of the start point.

There are symmetries we can exploit. Knight moves are the same forward and backward, so we can interchange start and end. If we think of the start and end as being the ends of a line segment, we can rotate by 90 degrees or reflect horizontally or vertically, and the move distance will remain the same.

So, given this table, we can slide or reflect the start/end pair over the grid until one of the points is at a1 and the other point is somewhere on the grid.

It took all of five minutes to generate the grid on a piece of graph paper, and the easy move here would be to hard-code the grid into a two-dimensional array. To make it more fun, we could write the code to generate the grid. That might be useful if the problem were generalized to board sizes other than 8×8, which I am not going to do, just to be clear.

For even more Perl fun, let’s use the class feature to build an object around the board.

So, let’s start laying out a program.

• Chess notation is annoying. We’re quickly going to convert to using 0 to 7 as row and column indexes.

sub chessToGrid($chess)
{ return ( substr($chess,1,1) - 1, ord(substr($chess, 0, 1)) - ord('a') )
}

Our board is going to be a class, because I want it to be. I use v5.40, which has class features, but it still gives “experimental” warnings. The attributes of a Board are its size, and the two-dimensional grid. The only public methods we really need are a constructor, and a method to retrieve a value from the grid.

use v5.40;
use feature 'class'; no warnings "experimental::class"; class Board
{ field $row :param //= 8; field $col :param //= 8; field $lastRow = $row - 1; field $lastCol = $col - 1; field @board; ADJUST { # The board starts out as 8x8 undef values push @board, [ (undef) x $col ] for ( 1 .. $row ); $self->_init(); } method at($r, $c) { ... } # Private methods method _init() { ... } method _knightMoveFrom($r, $c) { ... }
}

Some Perl points:

• field $row :param //= 8 — The :param declares that this is a parameter that could be passed to the constructor, but the //=8 declares that it will default to 8 if not given.
• field $lastRow = $row - 1 — This is a convenience variable, which will be set up in the constructor. It’s not a parameter to the constructor.
• ADJUST — This is a Perl class convention for adding code to the constructor. In this case, we’re going to initialize @board to be a two-dimensional array, and then we’re going to call a private method to fill in the distance values.
• method at() — This is an accessor to a square on the board, helping us keep @board private to the class.
• method _init() — I’m using the ancient venerable convention that private methods have an underscore prefix.

Let’s tackle the sub-problem of figuring out possible knight moves. For a square in the middle of the board, there are 8 possible moves:

• go right 2, then up or down;
• go left 2, then up or down.
• go up 2, then left or right;
• go down 2, then left or right;

These possibilities can be represented in a list of (row,column) delta pairs.

( [-1, 2], [1,2], [-1,-2], [1,-2], [2,1], [2, -1], [-2, 1], [-2, -1 ] )

Now we can find our possible moves by adding our given row and column to each of these deltas:

map { [ $r + $_->[0], $c + $_->[1] ] } ( [-1,2]... )

That yields a list of [row,column] pairs, but some of those pairs might now be off the grid. Let’s prune the list:

grep { 0 <= $_->[0] <= $lastRow && 0 <= $_->[1] <= $lastCol }

Since this is a class method, it has access to the fields, so $lastRow and $lastCol are available for the bounds check. The whole thing together is a terse couple of lines:

method knightMoveFrom($r, $c)
{ grep { 0 <= $_->[0] <= $lastRow && 0 <= $_->[1] <= $lastCol } map { [ $r + $_->[0], $c + $_->[1] ] } ( [-1, 2], [1,2], [-1,-2], [1,-2], [2,1], [2, -1], [-2, 1], [-2, -1 ] )
}

Having this function available, it becomes possible to write the _init() private method. I’m going to omit the code for it, in an already-lost quest for brevity; it’s on GitHub

Let’s return to the main function of the program. We’re given a start and end square in chess notation. We want to convert that to Cartesian coordinates, and then figure out how to translate the points to the origin.

We’re going to check the slope of the line between the two points. If it’s positive, then one of the points is up and to the right of the other, and all we have to do is slide the points down and to the left until one reaches (0,0).

If the slope is negative, that means that if we slide the two points towards the origin, one of them is going to fall outside of the grid. Fortunately, we can use symmetry to flip the line over and make the slope positive. For example, suppose our start and end points look like this:

| . . . . . .
| . S . . . .
| . . . . . .
| . . . . . .
| . . . . E .
| . . . . . .
+------------------

As far as the knight-move distance between the points is concerned, this is equivalent to flipping the points:

| . . . . . .
| . S------->s' .
| . . . . . .
| . . . . . .
| . e'<------E .
| . . . . . .
+------------------

The reflection means that for S, keep its row, but move it over to E’s column; and for E, keep its row, but move it over to S’s column. That is, (in programming terms), swap the column coordinates.

Once we’ve adjusted the points so that they form a positive slope, then we have to slide the one closest to the origin to (0,0), and slide the other point by the same amount. If the end is closer than the start, then we swap the points (again, as far as knight-move distance is concerned, it’s going to be the same).

The translation to (0,0) happens by subtracting the start point from the end point. Finally, the number of moves is just a table lookup from our carefully constructed Board object.

sub km($start, $end)
{ my @start = chessToGrid($start); my @end = chessToGrid($end); # If the slope is negative, reflect the line so that the slope is positive.  my $dy = $end[1] - $start[1]; my $dx = $end[0] - $start[0]; my $slope = ( $dx == 0 ? 0 : $dy / $dx ); if ( $slope < 0 ) { ( $start[1], $end[1] ) = ( $end[1], $start[1] ); } # If the end is closer to the origin, swap ends if ( $end[0] < $start[0] || $end[1] < $start[1] ) { ( $start[0], $start[1], $end[0], $end[1] ) = ( @end, @start); } # Shift the end point as if the start is at 0,0 $end[0] -= $start[0]; $end[1] -= $start[1]; return $Board->at(@end);
}