# RabbitFarm

### 2021-05-16

#### The Weekly Challenge 112

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

## Part 1

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

### Solution

``````
use strict;
use warnings;
##
# Write a script to convert the given absolute path to the simplified canonical path.
# 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
##
my(\$path) = @_;
\$path = "/" . \$path if substr(\$path, 0, 1) ne "/";
return \$path;
}

sub single_seperator{
my(\$path) = @_;
\$path =~ s#\/\/#\/#;
return \$path;
}

sub trailing_slash{
my(\$path) = @_;
chop(\$path) if substr(\$path, length(\$path) - 1, 1) eq "/";
return \$path;
}

sub up_stay{
my(\$path) = @_;
my @directories = split(/\//, substr(\$path, 1));
my @temp_path;
for my \$d (@directories){
push @temp_path, \$d if \$d ne "." && \$d ne "..";
pop @temp_path if \$d eq "..";
next if \$d eq ".";
}
return "/" . join("/", @temp_path);
}

sub canonical_path{
my(\$path) = @_;
}

MAIN:{
while(){
chomp;
print canonical_path(\$_) . "\n";
}
}

__DATA__
/a/
/a/b//c/
/a/b/c/../..
``````

### Sample Run

``````
\$ perl perl/ch-1.pl
/a
/a/b/c
/a
``````

### Notes

The challenge I set for myself here was to completely avoid any use of regular expressions! I think I pulled it off, more or less. I am not quite sure I covered every possible corner case, but it works for the examples given.

## Part 2

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.

### Solution

``````
use strict;
use warnings;
##
# 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.
##
use Array::Compare;
use Algorithm::Combinatorics q/variations_with_repetition/;

sub steps{
my(\$k) = @_;
my @data = (0, 1, 2);
my @steps;
my \$comparison = new Array::Compare();
my \$iterator = variations_with_repetition(\@data, \$k);
while(my \$combination = \$iterator->next()){
if(unpack("%32C*", pack("C*", @{\$combination})) == \$k){
my \$step = [grep {\$_ != 0} @{\$combination}];
push @steps, \$step if(!grep {\$comparison->compare(\$_, \$step)} @steps);
}
}
return @steps;
}

MAIN:{
my @steps;
@steps = steps(3);
print "k = 3\n";
for my \$steps (@steps){
my \$option;
for my \$step (@{\$steps}){
\$option .=  "\$step step + "  if \$step == 1;
\$option .=  "\$step steps + " if \$step == 2;
}
chop(\$option);
chop(\$option);
print "\$option\n";
}
@steps = steps(4);
print "\nk = 4\n";
for my \$steps (@steps){
my \$option;
for my \$step (@{\$steps}){
\$option .=  "\$step step + "  if \$step == 1;
\$option .=  "\$step steps + " if \$step == 2;
}
chop(\$option);
chop(\$option);
print "\$option\n";
}
@steps = steps(5);
print "\nk = 5\n";
for my \$steps (@steps){
my \$option;
for my \$step (@{\$steps}){
\$option .=  "\$step step + "  if \$step == 1;
\$option .=  "\$step steps + " if \$step == 2;
}
chop(\$option);
chop(\$option);
print "\$option\n";
}
}
``````

### Sample Run

``````
\$ perl perl/ch-2.pl
k = 3
1 step + 2 steps
2 steps + 1 step
1 step + 1 step + 1 step

k = 4
2 steps + 2 steps
1 step + 1 step + 2 steps
1 step + 2 steps + 1 step
2 steps + 1 step + 1 step
1 step + 1 step + 1 step + 1 step

k = 5
1 step + 2 steps + 2 steps
2 steps + 1 step + 2 steps
2 steps + 2 steps + 1 step
1 step + 1 step + 1 step + 2 steps
1 step + 1 step + 2 steps + 1 step
1 step + 2 steps + 1 step + 1 step
2 steps + 1 step + 1 step + 1 step
1 step + 1 step + 1 step + 1 step + 1 step
``````

### Notes

Rather than pursue some sort of algorithmic elegance and optimization I decided to try what is effectively a brute force approach. For small values of `\$k` this works quite nicely with the above example output generated in about a second on very modest hardware (an approximately 20 year old 450Mhz G4 Power Macintosh). Naturally we face a combinatorial explosion for larger values of `\$k`. For larger input values consider a graph search with memoization!

Overview of this brute force approach:

• Generate all arrays of numbers of length `\$k` using digits 0, 1, and 2.
• Keep all those arrays that sum to `\$k`
• Remove zeroes from these matching arrays
• Remove duplicate arrays

Combinations are generated using Algorithm::Combinatorics.

Duplicate array removal is facilitated by Array::Compare.

## References

Challenge 112

posted at: 18:10 by: Adam Russell | path: /perl | permanent link to this entry