The Weekly Challenge ‐ Perl and Raku

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!

Challenges Week #118 !

Task 2: Adventure of Knight

Link to the depreciated version.

public domain picture

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 exercises 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?

CY's solution

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 .

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.

CY's Solution: 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:

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 * * * * 
* * * * * * * * 

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 

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.

CY's Solution: 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

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

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 ϴ(n^n+0.5 exp(1/(12*n)) ) (may multiply by one more n) [ref].

My Encounter to "Memoize"

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

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

Miscellaneous

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

On Sunday, I found the team Clojure script contributor, Tyler Wardhaugh, is trying to use the wholly mathematical approach: build a Knight's graph...!

Other Members' Solutions for the Shortest Knight Path

Soon after a cry on Twitter, in Saturday evening, E. Choroba invited us to take a look on his A* search solution. It finds a shortest path. And it does its responsibility within 10 seconds It finishes a 16-spot case in about 4 minute. In addition, his approach is object-oriented. Bravo.

At 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 in Windows OS against E. Choroba's and found Abigail's faster by E. Choroba's a factor of 2 to 4.

Abigail's script is essentially composed of less than 65 lines and exact. Impressive. Bravo for Abigail.

In Sunday 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.

Note that at that moment 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. The unit of time is second.

Treasure spots: 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

Treasure spots: 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

This 16-spot case used here has more than one ways to get the shortest path length, therefore the two codes output are different.

James Smith's implementation is fast and exact! Bravo for 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 (kind of key components for the speed) in James's code or which new features from Perl 5.32 are used by Abigail's script.

Farewell Message... Back to the Role of a Puzzle Creator

As the puzzle creator, one of stuff what I dreamed to see is scripts which are very creative or compact but providing reasonably short paths. Before and after the official deadline settles, I do discover some solutions trying on this goal. However, in this blogpost, the description above is almostly all about solutions completing the "bonus part" (for generalized cases). I have to say a light apology to teammates attempting reasonably short paths as most of these solutions haven't been discussed in this blogpost. It's a surprise to see James Smith's pre-processing and caching Perl solution settles the cases for 16-spot within one minute.

I was afraid that the nature of this task will make a small amount of submissions, like the previous "chess task" N Queens in Week 062, but my worry soon settled around the Friday. The team members mentioned made fast and exact solutions. Then I feared another problem: would this task 2 make no "Star Contributors" for Week 118? Luckily when the RECAP came out and there are two; and Jaldhar H. Vyas provided EXACT solutions in Perl, Raku and C++ with the algorithmic technique "Iterative Deepening A*". For the sake of time I do not do performance test on Jaldhar's.

Do tell me if I have left out another brilliant exact solution which I should learn from.

Stay alert and healthy! □

Links to Perl Solutions and Blogposts of Team Members directly mentioned

(official) RECAP - Week 118

CY: pre-processing code, main code , blogpost here :)

E. Choroba: code , not blogged

Abigail: code , blogpost

James Smith: code , blogpost

Jaldhar H. Vyas: code, blogpost

Tyler Wardhaugh: Clojure code , not blogged

A good summary having related blogs is listed on the Weekly Challenge section on Perl Weekly.

Contact on twitter: @e7_87.

Created Date: 29th June, 2021 HKT 12:45 (UTC 12:45), fixed typo HKT 23:57; minor edit 5th July

Link to the depreciated version created on 26th June.