## Perl Weekly Challenge 112: Canonical Path and Climb Stairs

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.

## Leave a comment