This is my response to the Perl Weekly Challenge #112.
- 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 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
Input: "/a/"
Output: "/a"
Input: "/a/b//c/"
Output: "/a/b/c"
Input: "/a/b/c/../.."
Output: "/a"
The obvious approach (after looking through the documentation) is the built in
IO::Path class. Let us have a go:
> my $p = IO::Path.new('/a/b/');
> say $p.resolve; # -> "/a/b/".IO
> say $p.cleanup; # -> "/a/b".IO
Note that clenup got rid of the trailing slash, so we stick with that method.
The result is an IO object, but we can stringify it:
> say IO::Path.new('/a/b/').resolve.Str; # -> /a/b
> say IO::Path.new('/a//b/').resolve.Str; # -> /a/b
> say IO::Path.new('/a/./b/').resolve.Str; # -> /a/b
> say IO::Path.new('/a/../b/').resolve.Str; # -> /a/../b
It god rid of multiple slashes (the second line) and single spcaces (the third line), but not double spaces (the fourth line).
See
docs.raku.org/type/IO::Path#method_cleanup
for more information about cleanup.
So we are better off programming it manually.
File: canonical-path
#! /usr/bin/env raku
unit sub MAIN (Str $path where $path.substr(0,1) eq '/', :v($verbose)); # [1]
my @path = $path.split('/'); # [2]
@path.shift; # [3]
my @result; # [4]
for @path -> $current # [5]
{
say ":: current element $current" if $verbose;
next unless $current; # [6]
next if $current eq '.'; # [7]
if $current eq '..' # [8]
{
@result.pop; # [8a]
}
else
{
@result.push: $current; # [9]
}
}
say "/{ @result.join('/') }"; # [10]
[1] Ensure that the first character is a slash.
[2] Split the string on slashes.
[3] Get rid of the initial slash.
[4] We are going to store the parts of the final path (the result) here.
[5] For each part in the path;
[6] Skip empty elements (i.e. something between //).
[7] Skip ., as it does not mrean anything inside a path.
[8] Do we have a .., if so get rid of the previous part.
[9] If not, add the current part to the path.
[10] Print the path. Note the initial slash, as join inserts
it between the elemens only.
See
docs.raku.org/routine/split
for more information about split.
See
docs.raku.org/routine/join
for more information about join.
Running it:
$ ./canonical-path /a/
/a
$ ./canonical-path /a/b//c
/a/b/c
$ ./canonical-path /a/b/c/../..
/a
$ ./canonical-path /a/b/./c/d
/a/b/c/d
The last one is not part of the examples, but should be allowed anyway.
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use Getopt::Long;
my $verbose = 0;
GetOptions("verbose" => \$verbose);
my $path = $ARGV[0] // die "Please specify the path";
die 'Path must begin with "/"' unless substr($path, 0, 1) eq '/';
my @path = split('/', $path);
shift(@path);
my @result;
for my $current (@path)
{
say ":: current element $current" if $verbose;
next unless $current;
next if $current eq '.';
if ($current eq '..')
{
pop(@result);
}
else
{
push(@result, $current);
}
}
say '/' . join('/', @result);
Running it gives the same results as the Raku version:
$ ./canonical-path-perl /a/
/a
$ ./canonical-path-perl /a/b//c
/a/b/c
$ ./canonical-path-perl /a/b/c/../..
/a
$ ./canonical-path-perl /a/b/./c/d
/a/b/c/d
$n steps to climb
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
Recursion works well here, as long as the number of steps is low(ish):
File: climb-stairs
#! /usr/bin/env raku
unit sub MAIN (Int $n where $n > 0); # [1]
my $matches = 0; # [2]
climb(0); # [3]
sub climb ($sum) # [3a]
{
return if $sum > $n; # [4]
if $sum == $n # [5]
{
$matches++; # [5a]
return; # [5b]
}
climb($sum +1); # [6]
climb($sum +2); # [6a]
}
say $matches; # [7]
[1] Ensure that we got a positive integer.
[2] Number of mathes (i.e. solutions).
[3] Off we go, recursively. The number (zero, in this case) is the number of steps so far
[4] Get rid of this recursion if we have missed the length of the stairs (i.e. was standing on the last step by one, and added two steps).
[5] Are we done? If so, add 1 to the number of matches [5a] and return from this recursion [5b].
[6] Climb one more step.
[7] Climb two more steps.
Running it:
$ ./climb-stairs 1
1
$ ./climb-stairs 2
2
$ ./climb-stairs 3
3
$ ./climb-stairs 4
5
$ ./climb-stairs 5
8
$ ./climb-stairs 6
13
$ ./climb-stairs 7
21
$ ./climb-stairs 8
34
$ ./climb-stairs 9
55
$ ./climb-stairs 10
89
$ ./climb-stairs 11
144
$ ./climb-stairs 12
233
$ ./climb-stairs 13
377
$ ./climb-stairs 14
610
$ ./climb-stairs 15
987
$ ./climb-stairs 16
1597
$ ./climb-stairs 17
2584
$ ./climb-stairs 18
4181
$ ./climb-stairs 19
6765
$ ./climb-stairs 20
10946
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings "experimental::signatures";
my $n = $ARGV[0] // die "Please specify number of steps";
my $matches = 0;
climb(0);
sub climb ($sum)
{
return if $sum > $n;
if ($sum == $n)
{
$matches++;
return;
}
climb($sum +1);
climb($sum +2);
}
say $matches;
Running it gives the same results as the Raku version.
A stair with 40 steps gives us 165580141 combinations. That is the same number as the Raku version gave us, thankfully. The Perl program needed 1 minute and 18 seconds to compute the value on my pc. This is not exactly fast, but is much better than the Raku program that needed 7 and a half minute.
Trying to run the Perl program with the value 100 gives a lot of «Deep recursion on subroutine "main::climb"» warnings. Raku seems to be ok with it, but the program will probably run forever (seemingly at least).
Conclusision: Recursion is fun, but it does not scale well.
And that's it.