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!

It's time for challenges in Week #118 !

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?

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:

my \$board;

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],  [-21],  [ 1,-2],
[-12],  [ 2,-1],  [ 12],  [ 21])
{
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.

Story on logical errors:

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.
The code is written in the procedural style:
```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";
}

```
The given condition in the task statement has only one permutation of visiting the spots is minimum; see the output of the program:
```\$ 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
```
I92.760 sec362,880
II1030.563 sec3,628,800
III1276 min 50.364 sec479,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.

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

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

[26th Jun 22:00 HKT] A major update: It must be unfair to E. Choroba if I do not share it: E. Choroba's solution, employing the object-oriented paradigm, using the A* search Algorithm, finishes the 12-spot case within 8~9 seconds on my machine! I have to be more hard-working.
```\$ 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.