I’ve been doing the Perl Weekly
Challenges. The
latest
involved file analysis and combinatorial explosion. (Note that this is
open until 20 June 2021.)
TASK #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
[etc.]
Write a script to find the missing row number.
I assume that any row which starts with a number is the row of that
number. The filename is the parameter to my function. This basically
happens in two stages:
- read each line, find the number, list that as "a number which is not
missing"
- look for each positive integer in that list of non-missing numbers,
return for the first one which isn't there.
Here's the Raku:
sub mr($n) {
my $f=SetHash.new;
my $fh=open :r,$n or die "Cant open file\n";
for $fh.lines {
.chomp;
if (/^(<[0..9]>+)/) {
$f{$0+0}=1;
}
}
my $a=1;
while (1) {
unless ($f{$a}:exists) {
return $a;
}
$a++;
}
}
You could probably do something clever with first
but I didn't.
This version finds the first missing number from 1 up, however large
the file; a more sophisticated but less general approach would be to
assume that the missing number isn't the first or the last, and look
for gaps between the found numbers. Or just start with a set of 1..15
and delete rows as observed.
TASK #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.
Since I'm required to find the paths, not just return a count of them,
I'll use my standard non-recursive search pattern. (I looked at ways
of mutating the always-valid solution of R×n
, but it seemed too much
like work.)
Each entry in chain
is a tuple of (string of path so far, x
position, y position). (Except in Raku where I couldn't get it to do a
list of lists, so I used a list of hashes. But this is the first time
I've explicitly used the "tuple" type in Rust.) My x and y are
slightly unexpected, though. Here's my coordinate system for n=2:
(First time I've used a diagram in a PWC blog post…)
Each valid path starts at (0,0) and ends at (0,4). Each node can
generate up to three new path entries. For the y value reachable from
the current node, I work out the maximum possible x (the minimum is
always 0), and add the path entries that will remain within those
bounds. Here's the Ruby version:
def fpp(n)
o=Set.new
chain=[["",0,0]]
lim
is the maximum y value, which goes up by 4 per +1 except that
n=1 has a maximum y of 2.
lim=(n-1)*4
if n==1 then
lim=2
end
while chain.length() > 0
p=chain.pop
These are just convenience aliases.
x=p[1]
y=p[2]
If we have a valid solution, add it to the solution set.
if y >= lim then
o.add(p[0])
else
Otherwise, work out the maximum x for the next row.
mxx=y+1
if y >= n then
mxx=lim-y-1
end
And then for each direction, H, R and L, see if it fits, then generate
the path and add it. (There's a bug here - when I'm going to y+2 I
should really use a different mxx value because it's one row further
down. But it works anyway, because an R-path can only exist where an
L-path is possible.)
0.upto(2) do |txi|
tx=x-1+txi
if tx>=0 && tx<=mxx then
if txi==0 then
chain.push([p[0]+'H',x-1,y+1])
elsif txi==1 then
chain.push([p[0]+'R',x,y+2])
else
chain.push([p[0]+'L',x+1,y+1])
end
end
end
end
end
Then get the result set, and sort it (because I also sort the
test-case answers for easy verification).
return o.to_a.sort
end
The number of possible paths for each size is in the
OEIS, except for the first term, and that
gives a formula to generate it. (Interesting that that's every second
value of another sequence which gives the number of routes across a
square grid allowing diagonal movement.)
sub fpp {
my $n=shift;
my $s=0;
foreach my $i (0..$n*2) {
$s+=ncr(2*$n+1,$i+1)*ncr(2*$n+$i,$i);
}
$s/=(2*$n+1);
return $s;
}
(ncr
is the number of r-combinations to be made out of n, the usual
n!/r!(n-r)!
for which the actual functions are quite standard or may
be available in libraries. I used Memoize
a lot.)
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.