RabbitFarm

2024-08-10

Checking Out the Knight’s Moves

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

File Index

"ch-1.pl" Defined by 1.

"ch-2.pl" Defined by 6.

Part 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.

The complete solution is contained in one file that has a simple structure.

"ch-1.pl" 1≡


⟨preamble 2 ⟩
⟨check the color of a given square 3 ⟩
⟨main 5 ⟩
◇

For this problem we do not need to include very much. We’re just specifying to use the current version of Perl, for all the latest features in the language. This fragment is also used in Part 2.

⟨preamble 2 ⟩≡


use v5.38;
◇

Fragment referenced in 1, 6.

The color of a given square is determined by calculating its color number. If the color number is positive the square is dark. If the color number is negative then it is light.

⟨check the color of a given square 3 ⟩≡


sub check_color{
my($s) = @_;
my $a = [split //, $s];
⟨convert co-ordinates to a number 4 ⟩
return q/true/ if $color_number < 0;
return q/false/;
}
◇

Fragment referenced in 1.

Defines: $a 4.

Uses: $color_number 4.

We determine the color number in the following code fragment. Here we compute $n as -1 raised tot he power of the letter’s index. In this way we get alternating -1/1 starting with ’a’. We do the same with the second part of the co-rdinate to get an alternating -1/1 for the chessboard row. These are multiplied together to get the color number.

⟨convert co-ordinates to a number 4 ⟩≡


my $n = (-1) ** (ord($a->[0]) - ord(q/‘/));
my $color_number = $n * ((-1) ** join q//, @{$a}[1 .. @{$a} - 1]);
◇

Fragment referenced in 3.

Defines: $color_number 3, $n Never used.

Uses: $a 3.

Now all we need are a few lines of code for running some tests.

⟨main 5 ⟩≡


MAIN:{
say check_color q/d3/;
say check_color q/g5/;
say check_color q/e6/;
say check_color q/b1/;
say check_color q/b8/;
say check_color q/h1/;
say check_color q/h8/;
}
◇

Fragment referenced in 1.

Sample Run
$ perl perl/ch-1.pl 
true 
false 
true 
true 
false 
true 
false

Part 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.

"ch-2.pl" 6≡


⟨preamble 2 ⟩
use Graph;
⟨build knight’s graph 7 ⟩
⟨shortest path a knight needs to traverse from $start to $end 9 ⟩
⟨main 10 ⟩
◇

The bulk of the code is just setting up the main data structure, a graph. For each square of the chessboard we add an edge to all the squares that are reachable by a knight.

⟨build knight’s graph 7 ⟩≡


sub build_graph{
my $graph = Graph->new();
do {
my $c = $_;
do {
my $r = $_;
my($s, $t);
##
# up
##
$s = $r + 2;
$t = chr(ord(qq/$c/) - 1);
⟨add edge if legal move 8 ⟩
$t = chr(ord(qq/$c/) + 1);
⟨add edge if legal move 8 ⟩
##
# down
##
$s = $r - 2;
$t = chr(ord(qq/$c/) - 1);
⟨add edge if legal move 8 ⟩
$t = chr(ord(qq/$c/) + 1);
⟨add edge if legal move 8 ⟩
##
# left
##
$s = $r - 1;
$t = chr(ord(qq/$c/) - 2);
⟨add edge if legal move 8 ⟩
$s = $r + 1;
⟨add edge if legal move 8 ⟩
##
# right
##
$s = $r - 1;
$t = chr(ord(qq/$c/) + 2);
⟨add edge if legal move 8 ⟩
$s = $r + 1;
⟨add edge if legal move 8 ⟩
} for 1 .. 8;
} for q/a/ .. q/h/;
return $graph;
}
◇

Fragment referenced in 6.

Defines: $c Never used, $graph 8, 9, 10, $r 8.

For convenience I use a little bit of nuweb hackery instead of a new subroutine to seperate out this code which is repeated in the final generated code file.

⟨add edge if legal move 8 ⟩≡


$graph->add_edge(qq/$c$r/, qq/$t$s/) if $s >= 1 &&
$s <= 8 &&
$t =~ m/[a-h]/;
◇

Fragment referenced in 7.

Uses: $graph 7, $r 7.

After we go through the work of setting up the graph the result can be easily gotten via use of Djikstra’s shortest path algorithm.

⟨shortest path a knight needs to traverse from $start to $end 9 ⟩≡


sub shortest_knight_path{
my($graph, $start, $end) = @_;
my @path = $graph->SP_Dijkstra($start, $end);
say qq/$start ---> $end/;
print @path - 1 . q/: /;
say join q/ -> /, @path;
}
◇

Fragment referenced in 6.

Uses: $graph 7.

Finally, here’s a few tests to confirm everything is working right.

⟨main 10 ⟩≡


MAIN:{
my $graph = build_graph;
shortest_knight_path($graph, q/g2/, q/a8/);
shortest_knight_path($graph, q/g2/, q/h2/);
}
◇

Fragment referenced in 6.

Uses: $graph 7.

Sample Run
$ perl ch-2.pl 
g2 ---> a8
4: g2 -> e3 -> c4 -> b6 -> a8
g2 ---> h2
3: g2 -> e1 -> f3 -> h2

References

The Weekly Challenge 281
Generated Code
Graph.pm
Knight’s Tours

posted at: 16:52 by: Adam Russell | path: /perl | permanent link to this entry