laurent_r

These are some answers to the Week 112 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days (May 16, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

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.

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"

Although it can surely be done differently, this is obviously a job for regular expressions or regexes.

Canonical Path in Raku

It would certainly make sense to write a grammar for performing the necessary transformations, but this is simple enough for a few regexes to do the job. It is in fact probably possible to do everything with a single regex, but I usually find it more legible to transform the input string step by step.

Note that I’m not trying to validate the input paths, with just one exception: if there are too many /../ compared to the previous path items, the script dies, rather than printing something incorrect.

use v6

my @tests = </a/ /a/b//c/ /a/b/c/../.. /a/../../b/>;
for @tests <-> $path {
    my $p = $path;
    $path ~~ s:g|'//'+|/|;
    $path ~~ s:g!^'/' | '/'$!!;
    my @path-items;
    for split /'/'+/, $path -> $item {
        next if $item eq '.';
        if $item eq '..' {
            die "Invalid path $p" unless @path-items;
            pop @path-items;
        } else {
            push @path-items, $item;
        }
    };
    say "$p => /", @path-items.join('/');
}

The script displays the following output:

$ raku ./paths.raku
/a/ => /a
/a/b//c/ => /a/b/c
/a/b/c/../.. => /a
Invalid path /a/../../b/
  in block  at ./main.raku line 12
  in block <unit> at ./main.raku line 4

Canonical Path in Perl

This a port to Perl of the Raku program above, except that when there are too many /../ compared to the previous path items, the script issues a warning instead of dying, does not print any canonical path and proceeds with the next items.

use strict;
use warnings;
use feature "say";

my @tests = ('/a/', '/a/b//c/', '/a/b/c/../..', '/a/../../b/', '/a/././b/');
TEST: for my $path (@tests) {
    my $p = $path;
    $path =~ s|\/\/+|/|g;
    $path =~ s!^\/|\/$!!g;
    my @path_items;
    for my $item (split /\/+/, $path) {
        next if $item eq '.';
        if ($item eq '..') {
            warn "Invalid path $p" and next TEST unless @path_items;
            pop @path_items;
        } else {
            push @path_items, $item;
        }
    };
    say "$p => /", join '/', @path_items;
}

The script displays the following output:

$ perl paths.pl
/a/ => /a
/a/b//c/ => /a/b/c
/a/b/c/../.. => /a
Invalid path /a/../../b/ at paths.pl line 14.
/a/././b/ => /a/b

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.

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

It is not clear to me whether the output should contain all the information above, or just the number of possibilities, but since the assignment asks us “to find out the distinct ways to climb to the top”, I have decided to output the result in the format given above, although this leads to quite a bit of uninteresting boiler plate code.

Climb Stairs in Raku

I’ve decided to use a try-steps recursive subroutine to explore all possibilities. The script uses a @*result dynamic variable to store the various winning combinations of steps and to print them at the end.

use v6;

sub print-result {
    my $count = 0;  
    for  @*result -> @solution {
        print "\tOption ", ++$count, ": ";
        my @step_list;
        push @step_list, "$_ " ~ ($_ ~~ /1/ ?? "step " !! "steps") for @solution;
        say join " + ", @step_list;
    }
    say "";
}

sub try-steps ($nb-steps, @curr) {
    for 1, 2 -> $new-step {
        my @new-cur = (|@curr, $new-step);
        my $sum = [+] @new-cur;
        next if $sum > $nb-steps;
        if $sum == $nb-steps {
            push @*result, @new-cur;
            last;
        } else {
            try-steps $nb-steps, @new-cur;
        }
    }
}

for 3, 4, 5 -> $target {
    my @*result;
    try-steps $target, [];
    say 'Input: $n = ', $target;
    say "Output: ", @*result.elems;
    # say @*result;
    print-result;
}

The script displays the following output:

$ raku ./steps.raku
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: 1 step  + 2 steps + 1 step 
    Option 4: 2 steps + 1 step  + 1 step 
    Option 5: 2 steps + 2 steps

Input: $n = 5
Output: 8
    Option 1: 1 step  + 1 step  + 1 step  + 1 step  + 1 step 
    Option 2: 1 step  + 1 step  + 1 step  + 2 steps
    Option 3: 1 step  + 1 step  + 2 steps + 1 step 
    Option 4: 1 step  + 2 steps + 1 step  + 1 step 
    Option 5: 1 step  + 2 steps + 2 steps
    Option 6: 2 steps + 1 step  + 1 step  + 1 step 
    Option 7: 2 steps + 1 step  + 2 steps
    Option 8: 2 steps + 2 steps + 1 step

Note that, if you don’t want this verbose output, you can just remove the print-result subroutine definition, comment out the last line (with the print-result subroutine call), and uncomment the previous code line:

    say @*result;
    # print-result;

and obtain the following output:

$ raku ./steps.raku
Input: $n = 3
Output: 3
[[1 1 1] [1 2] [2 1]]
Input: $n = 4
Output: 5
[[1 1 1 1] [1 1 2] [1 2 1] [2 1 1] [2 2]]
Input: $n = 5
Output: 8
[[1 1 1 1 1] [1 1 1 2] [1 1 2 1] [1 2 1 1] [1 2 2] [2 1 1 1] [2 1 2] [2 2 1]]

Climb Stairs in Perl

This is a port to Perl of the above Raku program, with a try_steps recursive subroutine:

use strict;
use warnings;
use feature "say";

my @result;

sub print_result {
    my $count = 0;
    for  my $solution (@result) {
        print "\tOption ", ++$count, ": ";
        my @step_list;
        push @step_list, "$_ " . ($_ =~ /1/ ? "step " : "steps") for @$solution;
        say join " + ", @step_list;
    }
    say "";
}

sub try_steps  {
    my ($nb_steps, $sum, @curr) = @_;
    for my $new_step (1, 2) {
        my $new_sum =  $sum + $new_step;
        next if $new_sum > $nb_steps;
        my @new_cur = (@curr, $new_step);
        if ($new_sum == $nb_steps) {
            push @result, \@new_cur;
            last;
        } else {
            try_steps($nb_steps, $new_sum, @new_cur);
        }
    }
}

for my $target (3, 4, 5) {
    @result = ();
    try_steps $target, 0, ();
    say 'Input: $n = ', $target;
    say "Output: ", scalar @result;
    print_result;
}

This script displays the following output:

$ perl  ./steps.pl
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: 1 step  + 2 steps + 1 step
        Option 4: 2 steps + 1 step  + 1 step
        Option 5: 2 steps + 2 steps

Input: $n = 5
Output: 8
        Option 1: 1 step  + 1 step  + 1 step  + 1 step  + 1 step
        Option 2: 1 step  + 1 step  + 1 step  + 2 steps
        Option 3: 1 step  + 1 step  + 2 steps + 1 step
        Option 4: 1 step  + 2 steps + 1 step  + 1 step
        Option 5: 1 step  + 2 steps + 2 steps
        Option 6: 2 steps + 1 step  + 1 step  + 1 step
        Option 7: 2 steps + 1 step  + 2 steps
        Option 8: 2 steps + 2 steps + 1 step

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, May 23, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.