RabbitFarm

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
##
sub leading_slash{
    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) = @_; 
    return up_stay(trailing_slash(single_seperator(leading_slash($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