Color of Knight with Raku

[302] Published 11. August 2024.

This is my response to The Weekly Challenge #281.

Challenge #281.1: Check Color

You are given coordinates, a string that represents the coordinates of a square of the chessboard as shown below:

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

Example 1:

Input: $coordinates = "d3"
Output: true

Example 2:

Input: $coordinates = "g5"
Output: false

Example 3:

Input: $coordinates = "e6"
Output: true

We can do something boring like this:

File: check-color-boring

#! /usr/bin/env raku

subset BOARDPOS where * ~~ /^<[a..h]><[1..8]>$/;  # [1]

unit sub MAIN (BOARDPOS $coordinate);             # [2]

my %l;                                            # [3]

%l<a2> = %l<a4> = %l<a6> = %l<a8> = True;         # [3a]
%l<b1> = %l<b3> = %l<b5> = %l<b7> = True;
%l<c2> = %l<c4> = %l<c6> = %l<c8> = True;
%l<d1> = %l<d3> = %l<d5> = %l<d7> = True;

%l<e2> = %l<e4> = %l<e6> = %l<e8> = True;
%l<f1> = %l<f3> = %l<f5> = %l<f7> = True;
%l<g2> = %l<g4> = %l<g6> = %l<g8> = True;
%l<h1> = %l<h3> = %l<h5> = %l<h7> = True;

say so %l{$coordinate};                           # [4]

[1] We start pretty unboringly with a custom type declared with subset for legal chessboard positions.

See docs.raku.org/language/typesystem#subset for more information about subset.

[2] Then we apply that type to the input (a board position), causing a run time error if the user tries something stupid.

[3] Then the boredom kicks in, with hardcoding of all the light squares.

[4] Is the given square light? Note the boolean coercer so, so that undefined values (i.e. dark squares, which we have not set up) will be coerced to False.

See docs.raku.org/routine/so for more information about so.

Running it gives the correct result:

$ ./check-color-boring d3
True

$ ./check-color-boring g5
False

$ ./check-color-boring e6
True

Let us approach this like a true programmer (whishful thinking).

File: check-color

#! /usr/bin/env raku

subset BOARDPOS where * ~~ /^<[a..h]><[1..8]>$/;

unit sub MAIN (BOARDPOS $coordinate, :v(:$verbose));

my ($col, $row) = $coordinate.comb;       # [1]

say ": Row $row, Col $col" if $verbose;

say $col eq any(<a c e g>)                # [2]
  ?? $row %% 2                            # [2a]
  !! $row !%% 2;                          # [2b]

[1] Get the column and row.

[2] Does the column start with (at the bottom) a black square? If so, return True if the row is even (with the %% divisibility operator), and False otherwise. If the row does not start with a black square, we negate the result (with !) of the boolean test.

See docs.raku.org/routine/%% for more information about the Divisibility Operator %%.

Running it gives the expected result, shown here with verbose mode:

$ ./check-color -v d3
: Row 3, Col d
True

$ ./check-color -v g5
: Row 5, Col g
False

$ ./check-color -v e6
: Row 6, Col e
True

Challenge #281.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. So in the diagram below, if it starts a S, it can move to any of the squares marked E.

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'
Ouput: 4

g2 -> e3 -> d5 -> c7 -> a8

Example 2:

Input: $start = 'g2', $end = 'h2'
Ouput: 3

g2 -> e3 -> f1 -> h2

This is a breadth-first search, or «shortest path» as it is known in graph theory. Hold on, you may say. A chess board is nothing like a graph... Oh, yes it is. We are traversing a board, following a graph...

See Wikpedia: Breadth First Search for a gentle introduction.

In Binary Knight with Raku (and Perl), my answer to The Weekly Challenge #118 we actually did a similar board traversal, with a knight.

See my Amazingly Raku Part 2: The Path article for a description of the shortest path applied to a maze (the program «maze-solver-spa-simple»).

The general idea when looking for the shortest path is to start off in all possible directions (at once), adding the new one-step-away positions to the end of a queue. Then we go on until we have reached the target (success) or have an empty queue (failure). Note that this will give us a shortest path; there may be more of them.

We can illustrate this with a walk through of the first example.

First Move: The green box (marked 0, as in zero steps to get here) is the start position, the red box (marked X, as we do not know the number of steps to get there yet) is the target. The orange boxes (marked 1) are the positions we can get to with 1 step.

Second move: The blue boxes (marked 2) are all the positions we can reach from the orange positions, except already visited positions (just the green box in this case).

Third move: We are getting closer...

Fourth move: We have reached the target.

Then the program

File: knightmover

#! /usr/bin/env raku

subset BOARDPOS where * ~~ /^<[a..h]><[1..8]>$/;                 # [1]
subset MOVE of Int where -7 <= * <= 7;                           # [2]

unit sub MAIN (BOARDPOS $start, BOARDPOS $end, :v(:$verbose));   # [3]

my %seen = ( $start => True );                                   # [4]

my @queue = \{ steps => 0, pos => $start, path => ($start,) };   # [5]

while @queue                                                     # [6]
{
  my %curr = @queue.shift;                                       # [7]

  say ": Steps %curr<steps>: at pos %curr<pos> (path: %curr<path>)"
    if $verbose;

  if (%curr<pos> eq $end)                                        # [8]
  {
    say ": Arrived at target after %curr<steps> steps (path: %curr<path>)"
      if $verbose;

    say %curr<steps>;                                            # [8a]
    last;                                                        # [8b]
  }

  for ( (-2,-1), (-2,1), (2,-1), (2,1), (-1,-2), (-1,2), (1,-2), (1,2))
    -> ($row-offset, $col-offset)                                # [9]
  {
   my $new-pos = new-pos-knight(%curr<pos>, c => $col-offset,    # [10]
                                            r => $row-offset) // next;

   next if %seen{$new-pos}++;                                    # [11]

   @queue.push: { pos => $new-pos,
                  steps => %curr<steps> +1,
		  path => ( %curr<path>, $new-pos).flat };      # [12]
  }
}

sub new-pos-knight (BOARDPOS $pos,                               # [13]
                   MOVE :r(:$row-offset),
  		   MOVE :c(:$col-offset))
{
  my ($col, $row) = $pos.comb;                                   # [14]

  my $new-row = $row + $row-offset;                              # [15]
  return unless 1 <= $new-row <= 8;                              # [16]

  my $new-col = (ord($col) + $col-offset).chr;                   # [17]
  return unless $new-col eq any(<a b c d e f g h>);

  return $new-col ~ $new-row;                                    # [18]
}

[1] A custom type for the positions (again).

[2] A custiom type for the legal offset values (moves). This is future proofed for other chess pieces as well, thus the range.

[3] Enforce the custom types on the input.

[4] Already visited positions are kept here (and tested for in [11]).

[5] We start with a queue with one postional element; the start. Note the use of a hash for simplicity, rather than a class. We need the actual number of steps, as the challenge asked for that. The path is used by verbose mode only, and we could actually have calculated the number of steps from this array.

[6] As long as we have unfinished business.

[7] Retrieve the first element from the queue.

[8] Have we reached the target (end) position? If so, print the number of steps to get there [8a] and exit (the loop, and thus the program) [8b].

[9] Iterate over all the legal moves for a knight (as offset values for the row and column) at a generic position.

[10] Get the new position, and skip the current one if it is undefined (i.e. off the board).

[11] Skip the position if we have visited it already. Mark is as visited.

[12] Add the new position to the queue. Note the increased step value, and the groving path.

[13] Get us a new position, if possible.

[14] Split the position into column and row.

[15] Add the row offset to the row.

[16] Return if we are off the board.

[17] As for the column, but we must convert the letter to a number (with ord) before adding the offset and back to a letter afterwards (with chr. We are well inside the Unicode alphabet, so subtracting or adding 7 does not pose a potential problem. (This is why I have a custom type for the move; subtracting e.g. 1000 would not have worked.)

See docs.raku.org/routine/ord for more information about ord.

See docs.raku.org/routine/chr for more information about chr.

[18] Return the new position.

Running it:

$ ./knightmover g2 a8
4

$ ./knightmover g2 h2
3

Looking good.

With verbose mode:

$ ./knightmover -v g2 a8
: Steps 0: at pos g2 (path: g2)
: Steps 1: at pos f4 (path: g2 f4)
: Steps 1: at pos h4 (path: g2 h4)
: Steps 1: at pos e1 (path: g2 e1)
: Steps 1: at pos e3 (path: g2 e3)
: Steps 2: at pos e2 (path: g2 f4 e2)
: Steps 2: at pos e6 (path: g2 f4 e6)
: Steps 2: at pos g6 (path: g2 f4 g6)
: Steps 2: at pos d3 (path: g2 f4 d3)
: Steps 2: at pos h3 (path: g2 f4 h3)
: Steps 2: at pos d5 (path: g2 f4 d5)
: Steps 2: at pos h5 (path: g2 f4 h5)
: Steps 2: at pos f3 (path: g2 h4 f3)
: Steps 2: at pos f5 (path: g2 h4 f5)
: Steps 2: at pos c2 (path: g2 e1 c2)
: Steps 2: at pos d1 (path: g2 e3 d1)
: Steps 2: at pos f1 (path: g2 e3 f1)
: Steps 2: at pos c4 (path: g2 e3 c4)
: Steps 2: at pos g4 (path: g2 e3 g4)
: Steps 3: at pos d4 (path: g2 f4 e2 d4)
: Steps 3: at pos c1 (path: g2 f4 e2 c1)
: Steps 3: at pos g1 (path: g2 f4 e2 g1)
: Steps 3: at pos c3 (path: g2 f4 e2 c3)
: Steps 3: at pos g3 (path: g2 f4 e2 g3)
: Steps 3: at pos d8 (path: g2 f4 e6 d8)
: Steps 3: at pos f8 (path: g2 f4 e6 f8)
: Steps 3: at pos c5 (path: g2 f4 e6 c5)
: Steps 3: at pos g5 (path: g2 f4 e6 g5)
: Steps 3: at pos c7 (path: g2 f4 e6 c7)
: Steps 3: at pos g7 (path: g2 f4 e6 g7)
: Steps 3: at pos h8 (path: g2 f4 g6 h8)
: Steps 3: at pos e5 (path: g2 f4 g6 e5)
: Steps 3: at pos e7 (path: g2 f4 g6 e7)
: Steps 3: at pos b2 (path: g2 f4 d3 b2)
: Steps 3: at pos f2 (path: g2 f4 d3 f2)
: Steps 3: at pos b4 (path: g2 f4 d3 b4)
: Steps 3: at pos b6 (path: g2 f4 d5 b6)
: Steps 3: at pos f6 (path: g2 f4 d5 f6)
: Steps 3: at pos d2 (path: g2 h4 f3 d2)
: Steps 3: at pos h2 (path: g2 h4 f3 h2)
: Steps 3: at pos d6 (path: g2 h4 f5 d6)
: Steps 3: at pos h6 (path: g2 h4 f5 h6)
: Steps 3: at pos a1 (path: g2 e1 c2 a1)
: Steps 3: at pos a3 (path: g2 e1 c2 a3)
: Steps 3: at pos a5 (path: g2 e3 c4 a5)
: Steps 4: at pos c6 (path: g2 f4 e2 d4 c6)
: Steps 4: at pos b3 (path: g2 f4 e2 d4 b3)
: Steps 4: at pos b5 (path: g2 f4 e2 d4 b5)
: Steps 4: at pos a2 (path: g2 f4 e2 c1 a2)
: Steps 4: at pos b1 (path: g2 f4 e2 c3 b1)
: Steps 4: at pos a4 (path: g2 f4 e2 c3 a4)
: Steps 4: at pos e4 (path: g2 f4 e2 c3 e4)
: Steps 4: at pos h1 (path: g2 f4 e2 g3 h1)
: Steps 4: at pos b7 (path: g2 f4 e6 d8 b7)
: Steps 4: at pos f7 (path: g2 f4 e6 d8 f7)
: Steps 4: at pos d7 (path: g2 f4 e6 f8 d7)
: Steps 4: at pos h7 (path: g2 f4 e6 f8 h7)
: Steps 4: at pos a6 (path: g2 f4 e6 c5 a6)
: Steps 4: at pos a8 (path: g2 f4 e6 c7 a8)
: Arrived at target after 4 steps (path: g2 f4 e6 c7 a8)
4

$ ./knightmover -v g2 h2
: Steps 0: at pos g2 (path: g2)
: Steps 1: at pos f4 (path: g2 f4)
: Steps 1: at pos h4 (path: g2 h4)
: Steps 1: at pos e1 (path: g2 e1)
: Steps 1: at pos e3 (path: g2 e3)
: Steps 2: at pos e2 (path: g2 f4 e2)
: Steps 2: at pos e6 (path: g2 f4 e6)
: Steps 2: at pos g6 (path: g2 f4 g6)
: Steps 2: at pos d3 (path: g2 f4 d3)
: Steps 2: at pos h3 (path: g2 f4 h3)
: Steps 2: at pos d5 (path: g2 f4 d5)
: Steps 2: at pos h5 (path: g2 f4 h5)
: Steps 2: at pos f3 (path: g2 h4 f3)
: Steps 2: at pos f5 (path: g2 h4 f5)
: Steps 2: at pos c2 (path: g2 e1 c2)
: Steps 2: at pos d1 (path: g2 e3 d1)
: Steps 2: at pos f1 (path: g2 e3 f1)
: Steps 2: at pos c4 (path: g2 e3 c4)
: Steps 2: at pos g4 (path: g2 e3 g4)
: Steps 3: at pos d4 (path: g2 f4 e2 d4)
: Steps 3: at pos c1 (path: g2 f4 e2 c1)
: Steps 3: at pos g1 (path: g2 f4 e2 g1)
: Steps 3: at pos c3 (path: g2 f4 e2 c3)
: Steps 3: at pos g3 (path: g2 f4 e2 g3)
: Steps 3: at pos d8 (path: g2 f4 e6 d8)
: Steps 3: at pos f8 (path: g2 f4 e6 f8)
: Steps 3: at pos c5 (path: g2 f4 e6 c5)
: Steps 3: at pos g5 (path: g2 f4 e6 g5)
: Steps 3: at pos c7 (path: g2 f4 e6 c7)
: Steps 3: at pos g7 (path: g2 f4 e6 g7)
: Steps 3: at pos h8 (path: g2 f4 g6 h8)
: Steps 3: at pos e5 (path: g2 f4 g6 e5)
: Steps 3: at pos e7 (path: g2 f4 g6 e7)
: Steps 3: at pos b2 (path: g2 f4 d3 b2)
: Steps 3: at pos f2 (path: g2 f4 d3 f2)
: Steps 3: at pos b4 (path: g2 f4 d3 b4)
: Steps 3: at pos b6 (path: g2 f4 d5 b6)
: Steps 3: at pos f6 (path: g2 f4 d5 f6)
: Steps 3: at pos d2 (path: g2 h4 f3 d2)
: Steps 3: at pos h2 (path: g2 h4 f3 h2)
: Arrived at target after 3 steps (path: g2 h4 f3 h2)
3

And that's it.

Links

About me
Keyword Index
Beginning Raku (book)
RSS Feed
Code (zip)
Reddit Comments