Perl Weekly Challenge: Week 117
I've just realized that this week marks the two-year anniversery of this blog. I started regularly blogging about Perl and Raku weekly challenges with Week 13 though that wasn't one of my best efforts.
Challenge 1:
Missing Row
You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.
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
Write a script to find the missing row number.
I suspect there is a more concise way to solve this challenge in Raku but this worked so I didn't investigate further.
First we read all the lines in the file. The number of each row follows a strict format so it is easy to extract it
with a regular expression. The number at that point is a string so it has to be converted to a number with .Int. These
line numbers are added to an array which is then sorted.
my @lines = $filename.IO.lines.map({
/ ^ (\d+) /;
$/[0].Int;
}).sort;
Now a counter is set to 1. The array of line numbers is read and with each element the counter is incremented by 1.
If the line number contained in an element is not equal to the current value of the counter, that value must be the missing
line number. In that case, the value of $counter is printed and we can exit the script.
my $counter = 1;
for @lines -> $line {
if $line != $counter {
say $counter;
last;
}
$counter++;
}
This is the Perl version. It is more verbose because for efficiency we slurp the entire file in one go (by setting the
line separator $RS to undef) and then split it back up into lines.
open my $file, '<', $filename or die "$OS_ERROR\n";
local $RS = undef;
my $contents = <$file>;
close $file;
my @lines =
sort { $a <=> $b }
map { / ^ (\d+) /x; int ${^CAPTURE}[0]; }
split /\n/, $contents;
my $counter = 1;
for my $line (@lines) {
if ($counter != $line) {
say $counter;
last;
}
$counter++;
}
Challenge 2:
Find Possible Paths
You are given size of a triangle.
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
Example 2
Input: $N = 1
S
/ \
/ _ \ E
Output: R, LH
Based on the information given in the spec, we can envision the triangle as a set of row and column
coordinates. The apex will be 0,0. The bottom right corner will be $N,$N. We can use that
information to make a function like this. The first four parameters are the current (starting at 0,0) and end
coordinates. The last parameter is where we will be building the path by calling this function recursively.
makePath(0, 0, $N, $N, q{});
It looks like this:
sub makePath($currRow, $currCol, $endRow, $endCol, $path) {
Any recursive function must have a halting condition or it will continue for ever. We will stop when the current coordinates equal the end coordinates. Then we can print out the path and return.
if $currRow == $endRow && $currCol == $endCol {
say $path;
return;
}
If we are not at the end we can make one of three moves as per the spec.
if we are not on the last row we can go left. In that case the column coordinate will stay the same
(because the next row is bigger) and the row coordinate will be increased by one. An L will be added
to the path. With these changed parameters, makePath() will be called again.
if ($currRow < $endRow) {
makePath($currRow + 1, $currCol, $endRow, $endCol, $path ~ 'L');
}
Or if we are not at the end of the row, we can go horizontally. In this case the row coordinate will
stay the same and the column coordinate will be incremented. An H will be appended to the path and
with these parameters, makePath() will be called again.
if ($currCol < $currRow) {
makePath($currRow, $currCol + 1, $endRow, $endCol, $path ~ 'H');
}
If we are not on the last row and we are not on the last column of the row, we have the ability to go right.
This time both the row and column coordinates are incremented and the path has an R appended to it before
makePath() is called again.
if $currRow < $endRow && $currCol < $endCol {
makePath($currRow + 1, $currCol + 1, $endRow, $endCol, $path ~ 'R');
}
This is the Perl version. It's a straight copy of the Raku version.
makePath(0, 0, $N, $N, q{});
sub makePath {
my ($currRow, $currCol, $endRow, $endCol, $path) = @_;
if ($currRow == $endRow && $currCol == $endCol) {
say $path;
return;
}
if ($currRow < $endRow) {
makePath($currRow + 1, $currCol, $endRow, $endCol, $path . 'L');
}
if ($currCol < $currRow) {
makePath($currRow, $currCol + 1, $endRow, $endCol, $path . 'H');
}
if ($currRow < $endRow && $currCol < $endCol) {
makePath($currRow + 1, $currCol + 1, $endRow, $endCol, $path . 'R');
}
}
Incidently with $N = 10, there are 1037718 possible paths. With $N = 20 I don't know because the script is still
chugging away several hours after I started it.