I’ve been doing the Perl Weekly
Challenges. The
latest
involved path canonicalisation and numerical compositions. (Note that
this is open until 16 May 2021.)
TASK #1 › Canonical Path
You are given a string path, starting with a slash ‘/'.
Write a script to convert the given absolute path to the simplified
canonical path.
More detail follows, but in short: "/" is the element separator, start
with a "/", don't end with a "/", "//" counts as "/", "." is ignored,
".." deletes previous element.
(There are uses for the case where a/b/..
is not the same directory
as a
, but I don't think any of them is a good use.)
Anyway, I saw two ways of doing this: one is to iterate through the
path evaluating each element and pushing/popping the output list, and
the other is to do most of the preprocessing up front and then mangle
the list for occurrences of "..". The second amused me more.
sub cp {
my $i=shift;
my @p=grep {$_ ne '.'} grep /./,split /\//,$i;
Most of the work is now done. We have a list with no null entries, and
no "." entries. So everything's canonical except for any ".." entries.
my $d=1;
while ($d) {
$d=0;
foreach my $pi (1..$#p) {
if ($p[$pi] eq '..') {
splice @p,$pi-1,2;
$d=1;
last;
}
}
}
return '/'.join('/',@p);
}
The while
lets me use a normal foreach
; otherwise I'd have to
build my own loop structure and step the index variable back as
needed. This may be fractionally slower, but using standard constructs
makes it easier for someone else to debug.
Python uses its pleasantly odd for
construction to mangle the list,
and array slicing to replace the splice
.
p=[x for x in i.split('/') if x != '' and x != '.']
[...]
p=p[0:pi-2]+p[pi+1:-1]
Ruby uses find_all
which I still have to look up, and array slicing.
p=i.split('/').find_all {|i| i != '' && i != '.'}
[...]
p=p[0..pi-2]+p[pi+1..-1]
And Rust uses filter
and a fiddly borrow, slice and concatenate.
let mut p=i.split("/").filter(|x| *x != "" && *x != ".").collect::<Vec<_>>();
[...]
p=[&p[0..pi-2],&p[pi+1..p.len()-1]].concat();
TASK #2 › Climb Stairs
You are given $n steps to climb
Write a script to find out the distinct ways to climb to the top.
You are allowed to climb either 1 or 2 steps at a time.
(So 3 is 1,1,1 or 1,2 or 2,1 = 3; 4 is 1,1,1,1 or 1,1,2 or 1,2,1 or
2,1,1 or 2,2 = 5, etc.)
Well now this smells remarkably Fibonacci-like. And sure enough when I
check the OEIS I see "F(n) = number of
compositions of n-1 with no part greater than 2." (Always check the
OEIS.)
Now obviously I could work through all the possible compositions in
an iterative search, but I've done a lot of that sort of thing for
previous challenges and I don't think I've written a straightforward
Fibonacci calculator for one of these yet. It probably even runs
faster than the exhaustive search. (Minutes of thought can save
seconds of run-time!) Recursion is a mocker, and one might as well do
it iteratively.
Raku:
sub cs($i) {
my ($a,$b,$c)=(0,1,0);
for 1..$i {
$c=$a+$b;
($a,$b)=($b,$c);
}
return $c;
}
and all the other languages follow the same approach.
Full code on
github.