CY's Puzzle Created for The Weekly Challenge #118 ‐ Pre-processing
If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).
Do tell me, if I am wrong or you strongly oppose my statements!
It's time for challenges in Week #118 !
Task 2: Adventure of Knight
TL;DR: I have demostrated the logic of getting the (length of) the shortest paths in a 4 × 4 board on the beginning POD section of ch-2.pl .
Puzzle Creation
This week I am not only one of the participants, but also a coding puzzle creator! I was quite excited about it.
Many people recognized that this task can be related to Knight's tour. It is really one of inspirations ‐ other important source of inspirations is "checkmate" exercises for chess players.
Let's explain a bit on checkmate exercises. A checkmate exercise asks the chess player moves one of its pieces to checkmate the opponent in a few steps ("a few", normally for newbie). Here is a Twitter account providing these puzzles: @HourlyChess. Sometimes a form of related exercise may be presented, it is "capture an important piece" exercise. I found a nice collection by Mr David Petty. (Sorry for the site is commerical, as I could not find a non-commerical site having these exercises.)
Yes, having experience of practising chess gains advantage in this task. Since there are tasks which people familiar with number theory have advantage, I put this puzzle to submit. Isn't chess a popular game?
Warm-Up
The Knight's Property
N 3 2 3 1 2 1 4
The above small box often appears on my mind this week. It indicates number of steps of a knight to move towards the other squares. In this 3 × 3 chessboard, the knight cannot move to the diagonal immediate neighbour.
So imagine there are paddings that the knight can move to:
~ ~ ~ ~ N 3 2 ~ 3 2^ 1 ~ 2 1 4
Here ^ temporarily indicates a value appears only when there are paddings.
Move from A Square to Another Square
The main purpose of this section is a discussion of how to get a shortest path to another square.
(I have thought of whether using a smaller distance table can solve the puzzle exactly. Like, since 5 × 5 distance tables of two knights will ultimately overlap a rectangle. It guarantees a solution, but may not be the shortest solution(s).)
my $dist_tbl =
[[0,3,2,3,2,3,4,5],
[3,2,1,2,3,4,3,4],
[2,1,4,3,2,3,4,5],
[3,2,3,2,3,4,3,4],
[2,3,2,3,4,3,4,5],
[3,4,3,4,3,4,5,4],
[4,3,4,3,4,5,4,5],
[5,4,5,4,5,4,5,6]] ;Caution for a special case: [1][1] = 2 only if neither departure point nor destination point is a corner; [1][1] = 4 if the starting point is a corner. My code uses a subroutine is_corner to work-around it.
Caution: Don't confuse $dist_tbl with the chessboard for this task! They are only related when the number of squares having treasure is 1 (and $dist_tbl->[1][1] = 4) .
How the Distance Table is Generated
The pre-processing is in pre-ch-2.pl.
The core of the pre-processing codes is only roughly 40 lines, let us see:
for my $k (1..63) {
$board->[int $k / 8][$k % 8] = -1;
}
$board->[0][0] = 0;
$board->[1][1] = 2;
my $total = 62;
my $t = 0;
while ($total > 0) {
for my $i (0..7) {
for my $j (0..7) {
if ($board->[$i][$j] == $t) {
for my $a ( [-2,-1], [-1,-2], [-2, 1], [ 1,-2],
[-1, 2], [ 2,-1], [ 1, 2], [ 2, 1])
{
my $ai = $i+$a->[0];
my $aj = $j+$a->[1];
if ( $ai >= 0 && $aj >= 0 #no negative index
&& defined($board->[$ai][$aj])
# no running outside board
&& $board->[$ai][$aj] == -1) {
$board->[$ai][$aj] = 1 + $t;
$total--;
}
}
}
}
}
$t++;
}
for my $i (0..7) {
for my $j (0..7) {
print $board->[$i][$j], " " if $board->[$i][$j] >= 0;
print "*", " " if $board->[$i][$j] == -1;
}
print "\n";
}
Yup, there are so many nested blocks hence 4-space-indentation has to be replaced by 2-space-indentation.
When it comes to squares reachable within 3 steps, $board in pre-ch-2.pl, corresponds to $dist_tbl in ch-2.pl, is like this:
0 3 2 3 2 3 * * 3 2 1 2 3 * 3 * 2 1 * 3 2 3 * * 3 2 3 2 3 * 3 * 2 3 2 3 * 3 * * 3 * 3 * 3 * * * * 3 * 3 * * * * * * * * * * * *
By luck(?), the number of steps to reach every square is consecutive from 0 to 6… This part may have to be “aggressively” modified if the chessboard is irregular.
The original I coded
if ( defined($board->[$ai][$aj])
&& $board->[$ai][$aj] == -1)
The code crashed. After I discovered it was caused by the negative index for array feature, I changed it into
if ( $ai >= 0 && $aj >= 0
&& $board->[$ai][$aj] == -1)
It was still "featured" with bugs ‐ luckily, the interpreter told that the bug was related to uninitialized values.
As you can see the final version above, I omit it here.
(Much earlier: I created a $visited variable for saving whether a square is traversed and whether a square computes its possible next step.)
Main Dish
Since a large part of problem-solving is done by pre-ch-2.pl, the main code consists of only 6 subroutines:
dist_fun compare_mini alphanumeric binumeric_position is_corner expand
- (Supportive:) &alphanumeric and &binumeric_position interchange the
notation of a position. For example,
a6→[0,2],b2→[1,6],d4→[3,4], etc.. - &expand will return a knight's path with a pre-set number of steps between two positions. Its internal is very similar to pre-ch-2.pl.
- &dist_fun uses $dist_tbl as a reference and handle the corner case. It returns the minimum number of steps between two position.
- &is_corner is a supportive subroutine to &dist_fun. It returns whether a position is one of the chessboard four corners.
- &compare_mini compares a path with information of positions having treasure, sees whether the order of traversing the positions with treasure is a candidate for the shortest path.
use strict; use warnings; use Algorithm::Combinatorics qw/permutations/; die "Give me positions with treasure!\n" unless $ARGV[0]; my @treasures = map { binumeric_position($_) } @ARGV; my $min_path_length = 1000; my @min_paths = (); my $dist_tbl = #[[],[],...]; my $iter = permutations( \@treasures ); while (my $p = $iter->next) { my $path_length = dist_fun([0,0], $p->[0]); my $i = 0; while ($i < $p->$#*) { $path_length += dist_fun($p->[$i], $p->[$i+1]); $i++; } compare_mini($path_length, $p); } my $total = scalar @min_paths; print "The number of minimum path(s) is more than or equal to $total.\n"; print "Path length: $min_path_length.\n"; my $gd = int(rand($total)); print "Treasure spots shown only: "; print join "=>", map {alphanumeric($_)} $min_paths[$gd]->@*; print "\n\n"; print "A full path:\n"; print " ", join "->", map {alphanumeric($_)} expand([0,0], $min_paths[$gd]->[0])->@*; print "\n"; for my $s (0..$#treasures-1) { print "=> "; print join "->", map {alphanumeric($_)} expand($min_paths[$gd]->[$s], $min_paths[$gd]->[$s+1])->@*; print "\n"; }
$ time perl ch-2.pl a2 b1 b2 b3 c4 e6 The number of minimum path(s) is more than or equal to 1. Path length: 11. Treasure spots shown only: e6=>b3=>a2=>b1=>c4=>b2 A full path: a8->c7->e6 => e6->c5->b3 => b3->c1->a2 => a2->c3->b1 => b1->a3->c4 => c4->b2 real 0m0.025s user 0m0.024s sys 0m0.000s
Performance and Extensibility
I have randomly generated some chessboard positions for testing.Case I: (9 spots)
$ time perl ch-2.pl h3 d7 g7 h4 b4 c2 g2 b6 d4 The number of minimum path(s) is more than or equal to 2. Path length: 14. Treasure spots shown only: d7=>b6=>b4=>c2=>d4=>g7=>h4=>g2=>h3 A full path: a8->b6->d7 => d7->b6 => b6->d5->b4 => b4->c2 => c2->d4 => d4->e6->g7 => g7->f5->h4 => h4->g2 => g2->f4->h3 real 0m2.760s user 0m2.759s sys 0m0.000s
Case II: (10 spots)
$ time perl ch-2.pl h3 d7 g7 h4 b4 c2 g2 b6 d4 d1 The number of minimum path(s) is more than or equal to 4. Path length: 16. Treasure spots shown only: b6=>d7=>b4=>c2=>d4=>g7=>h4=>g2=>h3=>d1 A full path: a8->b6 => b6->d7 => d7->b8->a6->b4 => b4->c2 => c2->d4 => d4->e6->g7 => g7->f5->h4 => h4->g2 => g2->f4->h3 => h3->f2->d1 real 0m30.563s user 0m30.550s sys 0m0.004s
Case III: (12 spots)
$ time perl ch-2.pl h3 d7 g7 h4 b4 c2 g2 b6 d4 d1 c5 e4 The number of minimum path(s) is more than or equal to 2. Path length: 17. Treasure spots shown only: b6=>d7=>c5=>e4=>d1=>h3=>g2=>h4=>g7=>d4=>c2=>b4 A full path: a8->b6 => b6->d7 => d7->c5 => c5->e4 => e4->c3->d1 => d1->f2->h3 => h3->f4->g2 => g2->h4 => h4->f5->g7 => g7->e6->d4 => d4->c2 => c2->b4 real 76m50.364s user 76m49.594s sys 0m0.052s
| Case | Number of Spots | Time | Number of Permutations |
|---|---|---|---|
| Task specific | 6 | 0.025 sec | 720 |
| I | 9 | 2.760 sec | 362,880 |
| II | 10 | 30.563 sec | 3,628,800 |
| III | 12 | 76 min 50.364 sec | 479,001,600 |
12! = 10! × 132 = 479,001,600; the time of Case III is 77 min and the time of Case II is approximately half of 1 min; not surprisingly, the implementation is ϴ(nn+0.5 exp(1/(12*n)) ) (may multiply one more n) [ref].
Farewell Messages
Insight from Others
Peeking at the team's GitHub, I found a submission using Algorithm::Permute and Memoize, within 85 lines of code, brought a faster solution for the task specific data set! Of course, I quickly kept my arrogance: it is approx. 10% slower than my code with respect to 9 spots and spent 1 min on 10 spots.
Differences of the two permutation algorithms seems unlikely the source of power burst. What makes his faster than mine for those 6 spots with treasure!?
It is Memoize. RJT has recommended the free book “Higher-Order Perl”(published in 2005) to me long time ago and the book has a whole chapter on “Caching and Memoization”. Ooops. I quickly put use Memoize; and memoize("expand"); into my code, and mine runs faster than his now (... not wasting the effort of extra dozens of codes on pre-processing) now.
Note that memoize("dist_fun") has an opposite effect & it slows the script:
$ time perl ch-2-memo_dist_fun.pl a2 b1 b2 b3 c4 e6 The number of minimum path(s) is more than or equal to 1. Path length: 11. Treasure spots shown only: e6=>b3=>a2=>b1=>c4=>b2 ... real 0m0.029s user 0m0.029s sys 0m0.000s
$ time perl ch-2-memo_dist_fun.pl h3 d7 g7 h4 b4 c2 g2 b6 d4 ... real 0m4.535s user 0m4.529s sys 0m0.004s
$ time perl ch-2-memo_dist_fun.pl h3 d7 g7 h4 b4 c2 g2 b6 d4 d1 ... real 0m49.803s user 0m49.775s sys 0m0.001s
Why?...
mathematics of Knight's tour
Using Knight's tour seems not a promising approach for a reasonably short path. But it solves the challenge, anyway. :)
Here is just a short summary compiled from the Wikipedia page Knight's (tour) graph: It has 64 vertices (it's kind of obvious, arrr) and 168 edges. How fast will we get if we enter the data to some mathematicians' softwares (the most famous one must be Mathematica, and if you prefer FOSS, I could name Maxima and PARI/GP)?
It could be a small project on getting familiar with the computer algebra system. (Sorry that I am not experienced enough for trying it on Maxima as a dumb math enthusiast.)
a shortest path, or a reasonably short path
As the puzzle creator, what I dream to see is a script which is very creative or compact but providing reasonably short paths.
For a "shortest" path solution, are there any ways besides listing the permutations?
As a puzzle creator, maybe I should have better or more detailed wordings for a bonus next time.
Stay alert and healthy! □
Update on 28th June
Yesterday night I was impressed by, as usual for a relatively complex or complicated task, Abigail's (upping the ante) solution on the task. I did some performance tests against E. Choroba's and found Abigail's faster by a factor of 2 to 4.
Abigail's script is essentially composed of less than 65 lines. Impressive.
This morning I took a look on the team's repository and found "CY" mentioned in a pull request comment. James Smith, another experienced coder in the team, has written a new solution using the idea of pre-processing the distance and other techniques. Thank Mr Smith for reading my blogpost.
Note that this round I tested the scripts on Windows, which usually runs slower Perl, because Abigail's solution requests features in Perl 5.32 but my Linuxmint has only Perl 5.30 installed. I think the choice of the operating system is not a big deal because they won't give me 2-hour solutions. X)
Here are test results on Abigail's script and James Smith's script.
DATA: h3 d7 g7 h4 b4 c2 g2 b6 d4 d1 c5 e4 h8 Number of spots: 13 C:\work-now>perl abigail-ch-2.pl < data.1 a8 h3 f2 d1 c3 e4 c5 d7 b6 d5 b4 c2 d4 e6 g7 e6 f4 g2 h4 g6 h8 Overall time: 10.199467 C:\work-now>perl smith-ch-2.pl Minimal length: 21 Minimal route: a8 b6* d7* b6* d5 b4* c2* d4* f5 g7* e6 c5* e4* f2 h3* f2 d1* e3 g2* h4* g6 h8* Permutations: 6227020800 Function calls: 319502 Cache entries: 53249 Speed up: 116941.553831997 Timings: Pre^2-compute: 0.000116 Pre-compute: 0.005239 Find path: 1.712727 Overall time: 1.718082 --- DATA: h3 d7 g7 h4 b4 c2 g2 b6 d4 d1 c5 e4 h8 a1 h1 a3 Number of spots: 16 C:\work-now>perl abigail-ch-2.pl < data.2 a8 h3 f2 d1 f2 h1 f2 e4 c5 d7 b6 c4 a3 c2 a1 c2 b4 c6 d4 e6 g7 e6 f4 g2 h4 g6 h8 Overall time: 107.617590 C:\work-now>perl smith-ch-2.pl Minimal length: 27 Minimal route: a8 b6* d7* b6* c4 a3* c2* b4* c2* a1* c2* d4* f5 g7* e6 c5* e4* f2 h1* f2 h3* f2 d1* e3 g2* h4* g6 h8* Permutations: 20922789888000 Function calls: 3932177 Cache entries: 524289 Speed up: 39906978.570979 Timings: Pre^2-compute: 0.000623 Pre-compute: 0.013825 Find path: 31.986586 Overall time: 32.001034 ---
James Smith's implementation is really, FAST and EXACT! Bravo for Abigail and James Smith. □
Note that I am not trying to take on the job of code reviewer as my Perl programming is still weak, for two instances among many instances, I haven't understood the use of %CACHE in James's code or which new features from Perl 5.32 are used by Abigail's script.
Update on 27th June
Soon after a cry on Twitter, E. Choroba invited us to take a look on his A* search solution [code here]. It does not list out all permutations but finds a shortest path. And it is much faster ‐ for cases on 6 to 12 spots, it does its responsibility within 10 seconds It finishes a 16-spot case in 4 minute and 9.199 second. Bravo. □
The image of the knight (horse head) is from Wikimedia Commons; the image is released under GNU Lesser General Public License. Its author is Maurizio Monge. See the file details.
link for CY's full codes: pre-ch-2.pl (pre-processing), ch-2.pl
link to my blogpost for Task 1 "Binary Palindrome"
Contact on twitter: @e7_87.
Created Date: 26th June, 2021; last updated: 28th June, 12:00 HKT (28th June, 04:00 UTC).
[27th Jun 16:00 HKT] I found the team Clojure script contributor is trying to use the wholy mathematical approach: build a Knight's graph...!
[27th Jun 15:00 HKT] A major update: I have improved my code by a very trivial action (reducing calling to &compare_mini by moving a conditional). The performance significantly improves from 130 min to 77 min (Case III), 46 sec to 31 sec (Case II), 4.263 to 2.760 sec (Case I) and 0.066 to 0.025 sec (Task Specific Case).
[27th Jun 12:10 HKT] A major update and apology on the bound of n!.
$ cat data a b c d e f g h 8 N * * * * * * * 8 7 * * * x * * x * 7 6 * x * * * * * * 6 5 * * x * * * * * 5 4 * x * x x * * x 4 3 * * * * * * * x 3 2 * * x * * * x * 2 1 * * * x * * * * 1 a b c d e f g h $ time perl choroba-ch-2.pl < data Steps: 154299 17: a8, b6, d7, c5, e4, g5, h3, f2, d1, e3, g2, h4, f5, g7, f5, d4, c2, b4 real 0m8.672s user 0m8.636s sys 0m0.032s $ time perl choroba-ch-2.pl < data Steps: 154299 17: a8, b6, d7, c5, e4, g5, h3, f2, d1, e3, g2, h4, f5, g7, f5, d4, c2, b4 real 0m8.784s user 0m8.744s sys 0m0.036s $ time perl choroba-ch-2.pl < data Steps: 154299 17: a8, b6, d7, c5, e4, g5, h3, f2, d1, e3, g2, h4, f5, g7, f5, d4, c2, b4 real 0m8.779s user 0m8.735s sys 0m0.040s
[26th Jun 20:10 HKT] A major update and apology: The paths we are seeking are usually not Hamiltonian paths.