RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved chess-related problems. (Note that this ends today.)

Task 1: Check Color

You are given coordinates, a string that represents the coordinates of a square of the chessboard.

Write a script to return true if the square is light, and false if the square is dark.

Two parts to this, parsing the coordinates into X and Y, and (near trivially) working out the square colour.

The parser is quite straightforward (here in Python):

def cs2xy(a):
  x = ord(a[0]) - ord('a')
  y = ord(a[1]) - ord('1')
  return [x, y]

and the actual check is just a mod2 on the sum of the coordinates.

def checkcolor(a):
  xy = cs2xy(a)
  return (xy[0] + xy[1]) % 2 == 1

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.

Rather than do the full Dijkstra, I run a breadth-first search across the board space.

To avoid cycles, I keep a search-global seen set—which I can get away with because I'm going breadth-first: because the path costs at loop N are no lower than the path costs in all previous loops, the first time I see a cell will be a lowest-cost path to that cell.

Perl starts with the same coordinate reader:

sub cs2xy($a) {
  my @c = split('', $a);
  my $x = ord($c[0]) - ord('a');
  my $y = ord($c[1]) - ord('1');
  return [$x, $y];
}

sub knightsmove($from, $to) {

Turn the input parameters into coordinates.

  my $fc = cs2xy($from);
  my $tc = cs2xy($to);

Set up a FIFO queue and solution set.

  my @queue;
  push @queue, [$fc->[0], $fc->[1], 0];
  my %seen;

Iterate.

  while (@queue) {
    my $cc = shift @queue;

If we've found a solution, return its cost.

    if ($cc->[0] == $tc->[0] && $cc->[1] == $tc->[1]) {
      return $cc->[2];
    } else {

Otherwise, generate all possible moves…

      foreach my $offset (
        [2, 1],
        [1, 2],
        [2, -1],
        [1, -2],
        [-2, 1],
        [-1, 2],
        [-2, -1],
        [-1, -2]
          ) {
        my $x = $cc->[0] + $offset->[0];
        my $y = $cc->[1] + $offset->[1];

sieve for ones that stay on the board…

        if ($x >= 0 && $x <= 7 && $y >= 0 && $y <= 7) {

sieve more for ones that lead to squares we haven't already been to…

          my $cv = $x * 8 + $y;
          if (!exists $seen{$cv}) {

And push them onto the queue.

            push @queue,[$x, $y, $cc->[2] + 1];
            $seen{$cv} = 1;
          }
        }
      }
    }
  }
  return -1;
}

Full code on github.