RogerBW's Blog

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.