The Rowdy Path with Raku and Perl
[133] Published 20. June 2021.This is my response to the Perl Weekly Challenge #117.
Challenge #117.1: Missing Row
11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five
I have saved the text as «text-file.txt».
Let us start with a straight forward old school version, that does not take advantage of Raku's abilities:
File: missing-row-loops
#! /usr/bin/env raku
unit sub MAIN (Str $file where $file.IO.f && $file.IO.r, # [1]
:v(:$verbose));
my @ids; # [2]
for $file.IO.lines -> $line # [3]
{
my ($id, $content) = $line.split(',', 2); # [4]
say ": ID: $id" if $verbose;
@ids.push: $id.Int; # [5]
}
say ": IDs (sorted): { @ids.sort.join(", ") }" if $verbose;
my $expected = 1; # [6]
for @ids.sort -> $id # [7]
{
say ": $id (expected $expected)" if $verbose;
unless $id == $expected # [8]
{
say $expected; # [8a]
last; # [8b]
}
$expected++; # [9]
}
[1] Ensure that we get a file (.f) that we can read (.r).
[2] The IDs on the lines are ending up here.
[3] For each line in the file,
[4] • Get the ID (the digits before the comma). The rest (the content) isn't used.
[5] • Add the ID to the list. Note the coersion to an integer, so that the sort (in [7]) will sort the values numerically.
[6] The currently expected value in the sorted list.
[7] For each value in the sorted list,
[8] • Is it what we expcted? If not, the expected value is missing. Say so [8a] and exit [8b].
[9] Increase the expected value by one, ready for the next iteration.
Running it:
$ ./missing-row-loops text-file.txt
12
With verbose mode:
$ ./missing-row-loops -v text-file.txt
: ID: 11
: ID: 1
: ID: 9
: ID: 13
: ID: 2
: ID: 6
: ID: 8
: ID: 10
: ID: 7
: ID: 4
: ID: 14
: ID: 3
: ID: 15
: ID: 5
: IDs (sorted): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15
: 1 (expected 1)
: 2 (expected 2)
: 3 (expected 3)
: 4 (expected 4)
: 5 (expected 5)
: 6 (expected 6)
: 7 (expected 7)
: 8 (expected 8)
: 9 (expected 9)
: 10 (expected 10)
: 11 (expected 11)
: 13 (expected 12)
12
Note that the program will print the first missing value only. There may be more… (On the other hand, if none are missing, it will print nothing.)
It is easy to translate this to Perl:
File: missing-row-loops-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use File::Slurp; # [1]
use Getopt::Long;
my $verbose = 0;
GetOptions("verbose" => \$verbose);
my $file = $ARGV[0] // die "Please specify a file";
my @ids;
for my $line (read_file($file, chomp => 1)) # [1]
{
my ($id, $content) = split(',', $line, 2);
say ": ID: $id" if $verbose;
push(@ids, $id);
}
my $expected = 1;
for my $id (sort { $a <=> $b } @ids)
{
say ": $id (expected $expected)" if $verbose;
unless ($id == $expected)
{
say $expected;
last;
}
$expected++;
}
[1] I have used «read_file» from the File::Slurp module to read the entire file in one go (e.g. slurping it).
Running it gives exactly the same result as the Raku version:
$ ./missing-row-loops-perl text-file.txt
12
$ ./missing-row-loops-perl -v text-file.txt
: ID: 11
: ID: 1
: ID: 9
: ID: 13
: ID: 2
: ID: 6
: ID: 8
: ID: 10
: ID: 7
: ID: 4
: ID: 14
: ID: 3
: ID: 15
: ID: 5
: IDs (sorted): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15
: 1 (expected 1)
: 2 (expected 2)
: 3 (expected 3)
: 4 (expected 4)
: 5 (expected 5)
: 6 (expected 6)
: 7 (expected 7)
: 8 (expected 8)
: 9 (expected 9)
: 10 (expected 10)
: 11 (expected 11)
: 13 (expected 12)
12
Let us have a go at making the Raku program shorter. The first loop can be replaced with
a single map, and the second one can be replaced with a single Set difference
operator - all in one line:
#! /usr/bin/env raku
unit sub MAIN (Str $file where $file.IO.f && $file.IO.r, :l(:$limit) = 15);
# [1]
my $missing = (1 .. $limit) (-) $file.IO.lines.map({ /^(\d+)\,/ && $0.Int });
####################### # [3] # [2] #######################################
say "Missing row{ $missing.keys > 1 ?? "s" !! "" }: \ # [4]
{ $missing.keys.sort.join(", ") }"; # [5]
[1] Note the new «limit» argument, if the upper limit of 15 does not suit you.
[2] Use the regex on each line, and return the match (if any) coerced to an integer. The result is a list of integers.
[3] The Set Difference Operator. Note that it has a unicode version ∖
(which is not the same as a backspace character). I recommend using
(-) to avoid confusion. We start with all the values, remove those we
actually found, and the result is the missing ones. (Yes, there may be more than one
missing value.)
[4] Print «rows» if more than one missing value, and «row» if only one.
[5] Print the values, in sorted order. The result of the Set operation (in [3]) is a Set, so we must collect the keys to get the actual values.
See
docs.raku.org/routine/(-), infix ∖ for more
information about the Set difference operator (-).
Note that verbose mode has gone away, so running it is rather boring:
$ ./missing-row text-file.txt
Missing row: 12
We can do a version without loops in Perl as well. I have used «get_symmetric_difference» from List::Compare to mimic Set difference.
File: missing-row-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use File::Slurp;
use List::Compare;
my $file = $ARGV[0] // die "Please specify a file";
my @ids = map { /^(\d+)\,/ } read_file($file, chomp => 1);
my @all = (1..15);
my $lc = List::Compare->new('--unsorted', \@ids, \@all);
my @difference = $lc->get_symmetric_difference();
say join(", ", @difference);
Running it gives the same (boring) result as the Raku version:
$ ./missing-row-perl text-file.txt
Missing row: 12
With a user specified limit:
$ ./missing-row -l=20 text-file.txt
Missing rows: 12, 16, 17, 18, 19, 20
$ ./missing-row -l=10 text-file.txt
Missing row:
Challenge #117.2: Find Possible Paths
Write a script to find all possible paths from top to the bottom right corner.
In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).
BONUS: Try if it can handle triangle of size 10 or 20.
Example 1:
Input: $N = 2
S
/ \
/ _ \
/\ /\
/__\ /__\ E
Output: RR, LHR, LHLH, LLHH, RLH, LRH
Input: $N = 1
S
/ \
/ _ \ E
Output: R, LH
I find it easier to visualize this as a right-angled triangle, as this:
The arrows represent the available directions of travel.
(It can be argued that it really should be called a left-angled trangle…)
I have conceptually replaced the left turn with a turn straight down. Note the coordinates for the points (inside the blue boxes). We start at (0,0) and traverse all possible paths to the end; (2,2) in this case.
A recursive procedure is the obvious choice here, combined
with gather/take to collect the values, especially as I
did just that last week.
#! /usr/bin/env raku
unit sub MAIN (Int $N where $N >= 1, :v(:$verbose));
my $seq := gather # [1]
{
traverse(0, 0, "", $N); # [2]
sub traverse ($row, $col, $path, $size) # [3]
{
return take $path if $row == $col == $size; # [4]
traverse($row, $col +1, $path ~ "H", $size) if $col < $row; # [5]
traverse($row +1, $col +1, $path ~ "R", $size) if $col < $size; # [6]
traverse($row +1, $col, $path ~ "L", $size) if $row < $size; # [7]
}
}
say ": Number of paths: { $seq.elems } " if $verbose;
say $seq.join(", "); # [8]
[1] Set up the sequence.
[2] Off we go, recursively. We start at the top, with the raguments; row=0, column=0, path so far="", size=$N.
[3] The recursive procedure.
[4] Return (so to speak) the current path (with take) if we have reached
the end (the size is equal to the column and row numbers). The return statement does
not return anything, but it ensures that the current procedure call is ended.
[5] Continue in the "H" direction, if possible.
[6] Continue in the "R" direction, if possible.
[7] Continue in the "L" direction, if possible.
[8] Print the paths, comma separated.
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
Running it:
$ ./possible-paths 1
R, LH
$ ./possible-paths 2
RR, RLH, LHR, LHLH, LRH, LLHH
$ ./possible-paths 3
RRR, RRLH, RLHR, RLHLH, RLRH, RLLHH, LHRR, LHRLH, LHLHR, LHLHLH, LHLRH,
LHLLHH, LRHR, LRHLH, LRRH, LRLHH, LLHHR, LLHHLH, LLHRH, LLHLHH, LLRHH,
LLLHHH
$ ./possible-paths 4
RRRR, RRRLH, RRLHR, RRLHLH, RRLRH, RRLLHH, RLHRR, RLHRLH, RLHLHR, RLHLHLH,
RLHLRH, RLHLLHH, RLRHR, RLRHLH, RLRRH, RLRLHH, RLLHHR, RLLHHLH, RLLHRH,
RLLHLHH, RLLRHH, RLLLHHH, LHRRR, LHRRLH, LHRLHR, LHRLHLH, LHRLRH, LHRLLHH,
LHLHRR, LHLHRLH, LHLHLHR, LHLHLHLH, LHLHLRH, LHLHLLHH, LHLRHR, LHLRHLH,
LHLRRH, LHLRLHH, LHLLHHR, LHLLHHLH, LHLLHRH, LHLLHLHH, LHLLRHH, LHLLLHHH,
LRHRR, LRHRLH, LRHLHR, LRHLHLH, LRHLRH, LRHLLHH, LRRHR, LRRHLH, LRRRH,
LRRLHH, LRLHHR, LRLHHLH, LRLHRH, LRLHLHH, LRLRHH, LRLLHHH, LLHHRR, LLHHRLH,
LLHHLHR, LLHHLHLH, LLHHLRH, LLHHLLHH, LLHRHR, LLHRHLH, LLHRRH, LLHRLHH,
LLHLHHR, LLHLHHLH, LLHLHRH, LLHLHLHH, LLHLRHH, LLHLLHHH, LLRHHR, LLRHHLH,
LLRHRH, LLRHLHH, LLRRHH, LLRLHHH, LLLHHHR, LLLHHHLH, LLLHHRH, LLLHHLHH,
LLLHRHH, LLLHLHHH, LLLRHHH, LLLLHHHH
The second one has a different order of the paths than the example, but they are all there.
The number of paths are getting very big. Verbose mode will tell us the actual number of paths:
$ ./possible-paths -v 1
: Number of paths: 2
R, LH
$ ./possible-paths -v 2
: Number of paths: 6
RR, RLH, LHR, LHLH, LRH, LLHH
$ ./possible-paths -v 3
: Number of paths: 22
RRR, RRLH, RLHR, …
$ ./possible-paths -v 4
: Number of paths: 90
RRRR, RRRLH, RRLHR, …
$ ./possible-paths -v 5
: Number of paths: 394
RRRRR, RRRRLH, RRRLHR, …
$ ./possible-paths -v 6
: Number of paths: 1806
RRRRRR, RRRRRLH, RRRRLHR, …
$ ./possible-paths -v 7
: Number of paths: 8558
RRRRRRR, RRRRRRLH, RRRRRLHR, …
$ ./possible-paths -v 8
: Number of paths: 41586
RRRRRRRR, RRRRRRRLH, RRRRRRLHR, …
$ ./possible-paths -v 9
: Number of paths: 206098
RRRRRRRRR, RRRRRRRRLH, RRRRRRRLHR, …
$ ./possible-paths -v 10
: Number of paths: 1037718
RRRRRRRRRR, RRRRRRRRRLH, RRRRRRRRLHR, …
Looking good so far.
Perl
This is a straight forward translation of the Raku version. File: possible-paths-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
use Getopt::Long;
no warnings qw(experimental::signatures);
my $verbose = 0;
GetOptions("verbose" => \$verbose);
my $N = shift(@ARGV);
die "Specify a positive integer" unless $N =~ /^[1-9]\d*$/;
my @result;
traverse(0, 0, "", $N);
sub traverse ($row, $col, $path, $size)
{
if ($row == $col && $row == $size)
{
push(@result, $path);
return;
}
traverse($row, $col +1, $path . "H", $size) if $col < $row;
traverse($row +1, $col +1, $path . "R", $size) if $col < $size;
traverse($row +1, $col, $path . "L", $size) if $row < $size;
}
say join(", ", @result);
say ": Number of paths: " . scalar @result if $verbose;
Running it gives the same result as the Raku version:
$ ./possible-paths-perl 2
RR, RLH, LHR, LHLH, LRH, LLHH
$ ./possible-paths-perl 3
RRR, RRLH, RLHR, RLHLH, RLRH, RLLHH, LHRR, LHRLH, LHLHR, LHLHLH, LHLRH,
LHLLHH, LRHR, LRHLH, LRRH, LRLHH, LLHHR, LLHHLH, LLHRH, LLHLHH, LLRHH,
LLLHHH
A Non-Recursive Version
It is possible to avoid recursion, by using a queue to store the unfinished paths: File: possible-paths-loop
#! /usr/bin/env raku
unit sub MAIN (Int $N where $N >= 1, :v(:$verbose));
my @result; # [1]
my @todo = ( [0, 0,"", $N], ); # [2]
while @todo # [3]
{
my $current = @todo.shift; # [3a]
my ($row, $col, $path, $size) = @($current); # [4]
if $row == $col == $size # [5]
{
@result.push($path);
}
else # [6]
{
@todo.push( [$row, $col +1, $path ~ "H", $size] ) if $col < $row;
@todo.push( [$row +1, $col +1, $path ~ "R", $size] ) if $col < $size;
@todo.push( [$row +1, $col, $path ~ "L", $size] ) if $row < $size;
}
}
say @result.join(", ");
say ": Number of paths: { @result.elems }" if $verbose;
[1] The finished paths will end up here.
[2] A list of unfinished paths. We start with one element. Note the trailing comma, which is the list operator. Without it, we would end up with a list with 4 elements. (Parens or brackets does not make a list in Raku.)
[3] As long as we have more unfinished paths, get the first one in the queue [3a]
[4] • Get the individual values.
[5] • Finished? Add it to the list of finished paths.
[6] • If not, add one or more unfinished paths to the queue.
See
docs.raku.org/routine/,
for more information about the list operator ,.
Running it gives the expected result:
$ ./possible-paths-loop 2
RR, RLH, LHR, LHLH, LRH, LLHH
$ ./possible-paths-loop 3
RRR, RRLH, RLHR, RLHLH, RLRH, RLLHH, LHRR, LHRLH, LHLHR, LHLHLH, LHLRH,
LHLLHH, LRHR, LRHLH, LRRH, LRLHH, LLHHR, LLHHLH, LLHRH, LLHLHH, LLRHH,
LLLHHH
BONUS: Triangles of size 10 or 20
Let us have a go, starting with a lower size and timing the programs as we go along.| Program | $N | Time |
| possible-paths | 9 | 7.5 sec |
| possible-paths | 10 | 45 sec |
| possible-paths-loop | 9 | 1 min |
| possible-paths-loop | 10 | 8 min |
| possible-paths-perl | 9 | 1.5 sec |
| possible-paths-perl | 10 | 8 sec |
| possible-paths-perl | 20 | 65 min |
The recursive Raku version («possible-paths») is much faster than the Raku version using loops and a queue («possible-paths-loop»). I had actually expected it to be the other way round. The recursive Perl version is even faster, as expected.
And that's it.