PWC 281 Knight's Move

#perl #pwc #perlweeklychallenge

PWC 281 Task 2: 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.

	a	b	c	d	e
5	2		2
4		2		2
3	2	1			2
2			1	2
1	0		2		2

If we continue doing this until the 8x8 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, I think 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.

Ooops

Unfortunately, I've talked myself into a wrong solution. When a start point is moved from the middle of the square to the corner, we've eliminated some possible moves. For instance, consider the simple diagonal move from d4 to e5. That can be done in two moves (d4 - c6 - e5). But when we shift to the origin (a1 to b2), that first move goes off the board, so we have to take four steps to get there.

Can this strategy be salvaged? In effect, what I've done here is pre-compute the breadth-first search tree, and encoded it into a two-dimensional array. I guess I could also figure out how many such pre-computed trees I'd need for the squares around the edges (taking advantage of symmetry), but this is rapidly devolving into something more complicated than BFS, and much worse in performance.

The better answer would be to change direction and implement the breadth-first search, but I'm going to stubbornly pursue this line of thought. Although it will be inefficient, I'll compute a table of move distances each time I'm given a new start position.

Anyway ...

So, let's start laying out a program.

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. The public interface is going to deal in chess notation, but internally, we're going to use numeric cartesian coordinates.

use v5.40;
use feature 'class'; no warnings "experimental::class";

class Board
{
    field $row :param //= 8;
    field $col :param //= 8;
    field $knight :param //= 'a1';
    field @board;
    ADJUST {
        # The board starts out as 8x8 undef values
        push @board, [ (undef) x $col ] for ( 1 .. $row );
        $self->_init( $self->_chessToGrid($knight) );
    }

    method at($square, ) { ... }

    # Private methods
    method _init() { ... }
    method _knightMoveFrom($r, $c) { ... }
    method _chessToGrid($chess) { }
}

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. In principal, I could deal with boards of other dimensions than 8x8, but I'm not really going to go that far today.
field $knight :param //= 'a' --- We will pass the knight's starting position (in chess notation) into the constructor. A constructor call will look like my $board = Board->new( knight => "g2" )
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 full of undef values, 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. Since it's public, the parameter is going to be in chess notation, like $board->at("g3").

method at($square) {
    my ($r, $c) = $self->_chessToGrid($square);
    return $board[$r][$c];
}

method _init() -- I'm using the ancient venerable convention that private methods have an underscore prefix. We'll get back to this in a moment.
Chess notation is annoying. We're quickly going to convert to using 0 to 7 as row and column indexes.

method _chessToGrid($chess)
{
    return ( substr($chess,1,1) - 1, ord(substr($chess, 0, 1)) - ord('a') )
}

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] < $row  &&  0 <= $_->[1] < $col }

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

method _knightMoveFrom($r, $c)
{
    grep { 0 <= $_->[0] < $row  &&  0 <= $_->[1] < $col }
    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. It took all of five minutes to generate the grid on a piece of graph paper, but I'll need to do the equivalent in code, from an arbitrary start position. Let's define a function that takes an initial row and column, place a 0 there, and then continue taking steps outward from there as long as knight moves are still covering new squares.

method _init($kr, $kc)
{
    $board[$kr][$kc] = 0;

    my $step = 0;
    my $touched = true;
    while ( $touched )
    {
        $touched = false;
        for my $r ( 0 .. $lastRow )
        {
            for my $c ( 0 .. $lastCol )
            {
                next unless ( defined $board[$r][$c] && $board[$r][$c] == $step );
                for my $mv ( $self->_knightMoveFrom($r,$c) )
                {
                    if ( ! defined $board[$mv->[0]][$mv->[1]] )
                    {
                        $board[$mv->[0]][$mv->[1]] = $step+1;
                        $touched = true;
                    }
                }
            }
        }
        $step++;
    }

    return $self;
}

Let's return to the main function of the program. It's suddenly collapsed into something quite simple. We need a new distance board, and as soon as it's constructed, we just read out the distance at the end square.

sub km($start, $end)
{
    return $Board->new(knight => $start)->at( $end);
}

This is very tidy. There's a bunch of inefficiency hidden in the _init() method, especially if we start from a different square every time we query for the move distance. This might be a more acceptable solution if we had a use case where we were asking for distance multiple times from the same start point; then we would build the board once and call the at() method up to 63 times, which is a better payoff.

At any rate, it was a fun programming exercise. The complete code is available on GitHub