Perl Weekly Challenge: Week 112

Challenge 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.

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"

Canonicalising file paths is messy; even more so if you have to be portable accross different operating systems so in a "real" script you would want to use a tried and tested standard module for all that. But the spec given here is simple enough that we can implement it ourselves without outside help.

This is the Perl version.

my $path = shift // die "Must specify a path.";

We start by taking a path specification from the command line.

$path =~ s{ /+ }   {/}gmsx;

Multiple /s are reduced to one. I used {} as the regexp delimiter to avoid having to keep escaping /.

$path =~ s{ / \z } {}msx;

A / at the end of the path is removed if present.

my @dirs = split m{/}, $path;

The path is split into an array of directories using / as the split point. Then for each element...

for my $i (0 .. scalar @dirs - 1) {
    if ($dirs[$i] eq q{..}) {
        my $j = $i - 1;
        while ($j != 0 && $dirs[$j] eq q{}) {
            $j--;
        }
        $dirs[$j] = q{};
        $dirs[$i] = q{.};
    }

If it is .. we traverse backwards to find the last non-. or .. element. We also skip any elements which may be empty due to the next code block. When a suitable element has been found it is set to empty and the element we started from is set to ..

    if ($dirs[$i] eq q{.}) {
        $dirs[$i] = q{};
    }

If the current element is is ., either because it originally was that way in the path or as a result of the previous code block, it is set to empty.

}

say q{/} . (join q{/}, grep { $_ } @dirs);

(Full code on Github.)

Finally, we grep() all the non-empty elements of @dirs and join them back together into a string joined by /s. One more / is tacked on the front and this string is printed out.

This is the Raku version which works the same way.

sub MAIN(Str $p) {

    my $path = $p.subst(/ \/+ /, q{/}, :g).subst(/ \/ $ /, q{});

    my @dirs = $path.split(q{/});

    for 0 ..^ @dirs.elems -> $i {
        if @dirs[$i] eq q{..} {
            my $j = $i - 1;
            while $j != 0 && @dirs[$j] eq q{} {
                $j--;
            }
            @dirs[$j] = q{};
            @dirs[$i] = q{.};
        }

        if @dirs[$i] eq q{.} {
            @dirs[$i] = q{};
        }
    }

    say q{/}, @dirs.grep({ $_}).join(q{/});
}

(Full code on Github.)

Challenge 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.

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

I started my approach to this problem by doing the first few values of $n by hand. I was anticipating needing some sort of combinatorics algorithm but the results seemed to follow a pattern I'd seen before. I looked online and, yes, the number of distinct ways follows the Fibonacci sequence. Specifically, the answer is fibonacci($n + 1). This made the challenge easy to solve. In fact, in Raku it is a one-liner if you take advantage of "lazy lists".

(0, 1, -> $a, $b { $a + $b } ... *)[@*ARGS[0] + 1].say;

(Full code on Github.)

@*ARGS[0] is the first command-line argument. It represents $n in the spec.

For Perl, as usual, we need a bit more code but the standard recursive method for calculating the Fibonacci sequence is still quite easy.

sub fibonacci {
    my ($n) = @_;

    if ($n <= 1) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

my $stairs = shift // die "Must specify number of stairs to climb.";

say fibonacci($stairs + 1);

(Full code on Github.)