After Finding Our Bearings: One, Two and Up We Go!

Wherein we sort through the misdirection to find the one true way to the mountain, and then, after doing so, find a bunch of different ways to make the climb.

THE WEEKLY CHALLENGE – PERL & RAKU #112

---

episode one:
“Where am I? Where are my friends?”

---

Task 1

Canonical Path

Submitted by: Mohammad S Anwar

You are given a string path, starting with a slash ‘/’.

Write a script to convert the given absolute path to the simplified canonical path.

In a Unix-style file system:

- A period '.' refers to the current directory
- A double period '..' refers to the directory up a level
- Multiple consecutive slashes ('//') are treated as a single slash '/'

The canonical path format:

• The path starts with a single slash: “/“.
• Any two directories are separated by a single slash: “/“.
• The path does not end with a trailing: “/“.
• The path only contains the directories on the path from the root directory to the target file or directory

Example

Input: "/a/"
Output: "/a"

Input: "/a/b//c/"
Output: "/a/b/c"

Input: "/a/b/c/../.."
Output: "/a"

BAckground

In a world of stuff, sometimes some of that stuff needs to find other stuff, to, you know, do stuff.

This is a profound and heady statement, to be sure, indicating we’re in for a wild ride.

I’m phrasing things in the vaguest manner possible because it doesn’t really matter exactly what is looking for what: a message may need delivering; a phone may need to ring; a human may need to find its home, or food, or a bar; a blood-lusting robot may need to find out where all the humans are hiding. A subject needs an object to perform an action, either to the object or with the object. And to do this the subject needs to find the object.

After eliminating random dumb luck as a survival strategy, to get predictability we need a generalized concept of where things are in order to find them. We may not always have the whole picture, and that’s fine; sometimes we just need to know how to get from here to there. But if either we or our stuff are likely to move about it becomes increasingly unlikely we will always be able to keep whatever it is we need close by and within reach. What we really could use in that case is a map. We can then position ourselves and the object of our desires within a common context sufficiently large to encompass both. By developing the idea of coordinates, or an address, things can then move around without the need to update what may be increasingly complex relative directions — by consulting the map we can quickly reorient our schema at any time. Third parties can even make reference to the same map as you, allowing, for example, aerial spotter drones to mark the locations of heat signatures on the map, indicating to you where the humans are likely to be gathered. Different processes can work together within a common system.

In a general-purpose computer these ideas are much less abstract. Programs, themselves stored as binary data, require resources — configuration files, input and output files, all of this more data — to act, and need a consistent way to locate all of these things. There can be multiple ways to define the location of an object: relative relationships between items, such as “two blocks down and on the right”, or “right next to you”, or absolute placements, akin to a mailing address in the memory where we can find the item: city, street, building, floor and room.

Whereas the idea of a location is a specific position on a map containing it, the idea of directions to a location is not as well fixed. Locations are often derived from a combination of absolute and positional referencing, yielding a path, that while accurately identifying a specific location, may not describe the best and clearest way to get there. Paths may end up including redundant information, backtracking or even, in the case of filesystems that support them, shortcuts cross-linking one area to another. The absolute path given may not be the best path, but there are generally ways to clarify an absolute path so that there remains a single identifier that best specifies a particular place in the filesystem. This is known as the “canonical” path.

Method

In the world of UNIX, there are two special relative file locations: “.” – the current directory, “right here”, and “..” – the enclosing directory, which the current directory sits inside. Put another way, in an absolute path “..” is back one level to the one before.

However converting to canonical path form is not always quite as simple as restructuring any ./ and ../ notation into real directories and normalizing superfluous chaff such as //, because a canonical path is always an absolute path and the given path may not be. To get an absolute path from a relative path you need an idea of where you are to center the reference. This would be the current working directory, or cwd.

Although there exist ways to query the operating system to obtain the cwd, fortunately for us today the task is defined as having been given an absolute path, neatly sidestepping that mess.

It also should be noted that a canonical path also resolves soft links, which remains a difficulty, as Perl is not in itself a shell. We do have the -l file test operator, and there are always ways involving a module to address this, but I’m going to assume that particular edge case is outside the scope of the problem.

That said, a partial solution is provided in Perl and Python.

PERL 5 SOLUTION

This properly resolves the relative expressions ./ and ../, also removing redundant and trailing slashes. We need to futz at the end to make sure we start with a leading slash, even if there’s no path left, say in the case we gave it ../../../ to resolve.

sub canonical ($path) {
    $path =~ s{//+}{/}g;
    $path =~ s{/\./}{/}g;
    $path =~ s{/$}{};
    
    my @parts = split '/', $path;
    
    my $pos = 0;
    while ($pos < @parts) {
        if ($parts[$pos] eq '..') {
            if ($pos > 0) {
                splice @parts, $pos-1, 2;
                $pos -= 2;                       
            }
            else {
                splice @parts, $pos, 1;
                $pos--;
            }
        }
        $pos++;
    }
    @parts = (undef, undef) unless scalar @parts; 
    unshift @parts, '' if $parts[0] ne '';
    join '/', @parts;
    
}

The Cwd core module has a function abs_path() which seems quite handy, but only works relative to the current working directory. If the location given exists, and the script has sufficient privileges, we could chdir to the path location and then this will work to resolve soft links to reveal the canonical path:

use Cwd qw( abs_path );

sub canonical_softlinks ($path) {
    chdir $path;
    return abs_path( $path );
}

But that’s quite a workaround; incomplete and fraught with peril. Not really a robust way to proceed, but sometimes that’s all you get.

A better way would be to ask the system directly:

sub canon_sys ($path) {
    my $cur = `pwd`;
    chdir '/';
    my $out = `realpath -m $path` ;
    chomp $out;
    chdir $cur;
    return $out;
}

The only problem here is if you don’t have proper permissions to chdir down to root and switch back. We could avoid this detail but the cwd would be prepended to the result.

raku solution

In Raku, as is often the case, there’s a built-in function for that. It should be noted that this makes no attempt to resolve soft links either, nor remove /../ directives. Here we take a second step to resolve those using a regex, repeated substituting out any directory followed by a .. directory and then resetting the position counter until no more substitutions can be made.

unit sub MAIN () ;


sub canonical($path) {
    my $clean = IO::Spec::Unix.canonpath("$path");
    
    repeat {} while $clean ~~ s| '/' <-[/]>* '/..' ||;
    return $clean;
}

Python Solution

In Python we have it perhaps easiest of all. Here we’ve created a default option for the command line interface and brought in a nice complex example. This successfully resolves the soft link I inserted from d -> e, to yield /Users/colincrain/a/b/c/e

import os
import sys

if len(sys.argv) > 1:
    path = sys.argv[1]
else:
    path = '../../a/b/c///f/../d';

canonical = os.path.realpath(path)
  
print(canonical )

---

episode two:
“A One and Two and One and Two…”

---

task 2

Climb Stairs

Submitted by: Mohammad S Anwar

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.

Example

Input: $n = 3
Output: 3

    Option 1: 1 step + 1 step + 1 step
    Option 2: 1 step + 2 steps
    Option 3: 2 steps + 1 step

Input: $n = 4
Output: 5

    Option 1: 1 step + 1 step + 1 step + 1 step
    Option 2: 1 step + 1 step + 2 steps
    Option 3: 2 steps + 1 step + 1 step
    Option 4: 1 step + 2 steps + 1 step
    Option 5: 2 steps + 2 steps

Method

This was a fun one to think through. The first step involved looking at the results for the example input “5” as ordered groups of elements summed together:

(1+1+1+1), (1+1+2), (2+1+1), (1+2+1), (2+2)

What this looks like are integer compositions of the input value, with the added constraint that the maximum value is 2. A little thinking-through validates this hypothesis, as we want every combination, in every ordering, of 1 and 2 that adds up to the correct number of steps. Oh, and before anyone asks: we’re going to ignore the possibility of launching yourself off into space from the next-to-last step as though there were still two left to jump up, even though with enough exuberance you could probably land it and not break your neck. Pretending there is more than one remaining step does not make it so. The sum must be exact.

Next some further analysis with a pencil and paper:

input       compositions        count, or C_2(n)
1           1                   1
2           1,1                 2
            2
3           1,1,1               3
            2,1
            1,2
4           1,1,1,1             5
            2,1,1
            1,2,1
            1,1,2
            2,2
5           1,1,1,1,1           8
            2,1,1,1
            1,2,1,1
            1,1,2,1
            2,2,1          __________ change here from 1 to 2
            1,1,1,2       
            2,1,2
            1,2,2
6           1,1,1,1,1,1         13
            2,1,1,1,1
            1,2,1,1,1
            1,1,2,1,1
            2,2,1,1
            1,1,1,2,1
            2,1,2,1
            1,2,2,1        __________ change here from 1 to 2
            1,1,1,1,2              
            2,1,1,2
            1,2,1,2
            1,1,2,2
            2,2,2

And yes, although I didn’t include it here, the count of compositions, enumerated, for the next term is 21.

So wait one cotton-picking minute — (1, 2, 3, 5, 8, 13, 21, …) — is that the Fibonacci sequence? And if so, why?

Why yes, yes it is, and if you notice I’ve rearranged the sets to more clearly show the association. First separate each composition part into a head and a tail, with the tail being the last value. Now look at the head, and notice it is repeated in some set for a previous value. I’ve also gone and sorted the compositions in each sequence entry so all the parts ending in 1 are followed by those ending in 2. But I’m getting ahead of myself.

There are only two available values for a member of a composition part: 1 or 2. Thus each part in a composition for a new number will be that of a previously calculated composition with either an additional 1 or 2 added. To make the sums total correctly, the previous compositions referenced will be those for C(n-1), plus an additional 1, and C(n-2), with an additional 2.

Remember that at every stage, every composition set for that value is already an exhaustive enumeration of all possible arrangements for that number.

So to propagate every part of the composition set forward from a previous value, we add the new element, 1 or 2, to the end to create a new part. It can be seen that any other placement of the new item will produce a duplication that will need to be later removed, for although different orderings of the elements produces different parts, the parts that are counted are required to be unique. This is the fundimantal difference between partitions and compositions, that the order of the elements matters.

It now follows that for every number in the sequence we have the complete sets of composition parts created by combining the immediately previous number with 1, and the second previous with 2. In other words, with respect to the counts:

C(n) = C(n-1) + C(n-2)

which is the Fibonacci recurrence relation. With

C(1) = 1
C(2) = 2

the recurrence then follows, setting the pattern. Further, these values are themselves part of the Fibonacci sequence. So in other words:

C(n) = F(n+1) ∀ n > 0

So we’ll make a memoized Fibonacci generator to calculate our values and call it a day. Pack it in boys, we’re done here.

That’s the beauty of mathematics: sometimes the most ridiculously complicated things turn out to be super simple. It just works out that way sometimes.

Sometimes.

PERL 5 SOLUTION

Even though we could build an array and just reference that, we’re going to use Memoise to remember the states for the fib() function and reuse them without recalculating should they come up again. Oh, and once I saw it I couldn’t not include a little Natural Language Processing, preforming the proper pluralization for the written report.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use Lingua::EN::Inflexion;


use Memoize;
memoize qw( fib );

sub fib ($n) {
    return $n if $n < 2;
    return fib($n-1) + fib($n-2);
}


for (1..21) {   
    my $str = inflect("<#d:$_>for $_ <N:steps> there <V:is> ");
    $str .= fib($_+1) . ' ';
    $str .= inflect("<#d:$_>possible <N:ways> to climb <N:them>.");
    say $str; 
}

The results:

For 1 step there is 1 possible way to climb it.
For 2 steps there are 2 possible ways to climb them.
For 3 steps there are 3 possible ways to climb them.
For 4 steps there are 5 possible ways to climb them.
For 5 steps there are 8 possible ways to climb them.
For 6 steps there are 13 possible ways to climb them.
For 7 steps there are 21 possible ways to climb them.
For 8 steps there are 34 possible ways to climb them.
For 9 steps there are 55 possible ways to climb them.
For 10 steps there are 89 possible ways to climb them.
For 11 steps there are 144 possible ways to climb them.
For 12 steps there are 233 possible ways to climb them.
For 13 steps there are 377 possible ways to climb them.
For 14 steps there are 610 possible ways to climb them.
For 15 steps there are 987 possible ways to climb them.
For 16 steps there are 1597 possible ways to climb them.
For 17 steps there are 2584 possible ways to climb them.
For 18 steps there are 4181 possible ways to climb them.
For 19 steps there are 6765 possible ways to climb them.
For 20 steps there are 10946 possible ways to climb them.
For 21 steps there are 17711 possible ways to climb them.

Raku Solution

Raku has a Memoize module we could import, but we’ll do this one the other way, assembling our own list of already-defined results and using the list values preferentially. If we do need to calculate a new value, we assign the index to the list and the assignment value becomes the last operation in the block and is returned.

unit sub MAIN () ;

sub fib ( $n ){ 
    state @fib;
    return @fib[$n] when @fib[$n].defined;
    return @fib[$n] = $n if $n < 2;
    @fib[$n] = fib($n-1) + fib($n-2);
}

for 1..20 {
    my $s = $_ > 1 ?? 's' !! ' ';
    my $v = $_ > 1 ?? 'are' !! 'is ';
    printf "for %2d step%s there %s %5d way%s to climb them\n", $_, $s, $v, fib($_+1), $s;
}

the result looks a little different with the NLP done this way. I think this is clearer.

for  1 step  there is      1 way  to climb it
for  2 steps there are     2 ways to climb them
for  3 steps there are     3 ways to climb them
for  4 steps there are     5 ways to climb them
for  5 steps there are     8 ways to climb them
for  6 steps there are    13 ways to climb them
for  7 steps there are    21 ways to climb them
for  8 steps there are    34 ways to climb them
for  9 steps there are    55 ways to climb them
for 10 steps there are    89 ways to climb them
for 11 steps there are   144 ways to climb them
for 12 steps there are   233 ways to climb them
for 13 steps there are   377 ways to climb them
for 14 steps there are   610 ways to climb them
for 15 steps there are   987 ways to climb them
for 16 steps there are  1597 ways to climb them
for 17 steps there are  2584 ways to climb them
for 18 steps there are  4181 ways to climb them
for 19 steps there are  6765 ways to climb them
for 20 steps there are 10946 ways to climb them

Python Solution

In Python we get memoization as well, in the form of the the lru_cache() function decorator to do our memoizing for us.

from functools import lru_cache

@lru_cache(maxsize = 1000)
def fib(n):
    if n < 0:
        return None
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)


for i in range(2, 21):
    ways = fib(i+1)
    print(f"for {i} steps there are {ways} ways to climb them")