RabbitFarm

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

You are given a tree and a node of the given tree. Write a script to find out the distance of the given node from the root.

Solution

use strict;
use warnings;
package Tree129{
    use boolean;  
    use Tie::RefHash;
    use Class::Struct; 

    package Node{
        use boolean;  
        use Class::Struct; 
        struct(
            value => q/$/,
        );  
        true; 
    }  

    package Edge{
        use boolean;  
        use Class::Struct; 
        struct(
            weight => q/$/,
            source => q/Node/,
            target => q/Node/
        );  
        true; 
    }  

    struct(
        root => q/Node/,
        edges => q/%/
    );   

    sub print_tree{ 
        my($self) = @_;   
        for my $edge_source (keys %{$self->edges()}){
            for my $target (@{$self->edges()->{$edge_source}}){
                print $edge_source->value() . "->" . $target->value() . "\n";
            }
        }
    }  

    sub distance{
        my($self, $target) = @_;
        my $distance = 0;
        return $distance if($self->root()->value() == $target);
        my @nodes = @{$self->edges()->{$self->root()}};
        my @edge_sources = keys %{$self->edges()};
        do{
            $distance++;
            return $distance if((grep {$_->value() == $target} @nodes) > 0);
            my @child_nodes;
            for my $node (@nodes){
                my @k = grep {$_->value() == $node->value()} @edge_sources;
                push @child_nodes, @{$self->edges()->{$k[0]}} if $k[0] && $self->edges()->{$k[0]};
            }
            @nodes = @child_nodes;
        }while(@nodes);
        return -1;
    }

    sub insert{
        my($self, $source, $target) = @_;   
        if(!$self->root()){      
            $self->root(new Node(value => $source));  
            tie %{$self->edges()}, "Tie::RefHash";
            $self->edges($self->root() => [new Node(value => $target)]);          
        }   
        else{
            my $found = false;
            for my $edge_source (keys %{$self->edges()}){
                if($edge_source->value() == $source){
                    push @{$self->edges()->{$edge_source}}, new Node(value => $target);
                    $found = true;
                }
            }
            if(!$found){
                $self->edges()->{new Node(value => $source)} = [new Node(value => $target)];
            }
        }
    }  
    true; 
}

package main{
    my $tree = new Tree129(); 
    $tree->insert(1, 2); 
    $tree->insert(1, 3); 
    $tree->insert(3, 4); 
    $tree->insert(4, 5); 
    $tree->insert(4, 6); 
    print $tree->distance(6) . "\n";
    print $tree->distance(5) . "\n";
    print $tree->distance(2) . "\n";
    print $tree->distance(4) . "\n";
} 

Sample Run

$ perl perl/ch-1.pl
3
3
1
2

Notes

In the past, for this sort of problem, I would separate out the Tree package into its own file . Here I decided to keep everything in one file, but still divide everything into the proper packages.

While creating a Tree package from scratch was fun, getting that data structure correct is just half the battle. Still need to solve the problem! To that end we need to start at the root of the tree and then descend and count how many levels down the node is found, if it exists. If not return -1.

One issue is that to store the edges I use a hash with Nodes as keys. To use a Node instance as a key we need to use Tie::RefHash. There is a slight trick here though, to properly retrieve the value we need to access the keys using keys. Here I store the keys in an array and grep for a match. A slightly awkward requirement, but the work around is easy enough.

Part 2

You are given two linked list having single digit positive numbers. Write a script to add the two linked list and create a new linked representing the sum of the two linked list numbers. The two linked lists may or may not have the same number of elements.

Solution

use strict;
use warnings;
package LinkedList129{
    use boolean;
    use Class::Struct;

    package Node{
        use boolean;
        use Class::Struct;
        struct(
            value => q/$/,
            previous => q/Node/,
            next => q/Node/
        );
        true;
    }

    struct(
        head => q/Node/,
        tail => q/Node/,
        length => q/$/
    );

    sub stringify{
        my($self) = @_;
        my $s = $self->head()->value();
        my $next = $self->head()->next();
        while($next && $next->next()){
            $s .= " -> " if $s; 
            $s = $s . $next->value();
            $next = $next->next();
        }
        $s = $s . " -> " . $next->value() if $next->value();
        $s .= "\n"; 
        return $s;
    }

    sub stringify_reverse{
        my($self) = @_;
        my $s = $self->tail()->value();
        my $previous = $self->tail()->previous();
        while($previous && $previous->previous()){
            $s .= " -> " if $s; 
            $s = $s . $previous->value();
            $previous = $previous->previous();
        }
        $s = $s . " -> " . $self->head()->value();
        $s .= "\n"; 
        return $s;
    }

    sub insert{
        my($self, $value) = @_;
        if(!$self->head()){
            $self->head(new Node(value => $value, previous => undef, next => undef));
            $self->tail($self->head());
            $self->length(1);
        }
        else{
            my $current = $self->head();
            my $inserted = false;
            do{
                if(!$current->next()){
                    $current->next(new Node(value => $value, previous => $current, next => undef));
                    $inserted = true; 
                }
                $current = $current->next();
            }while(!$inserted);
            $self->tail($current);
            $self->length($self->length() + 1);
        }
        return $value;
    }

    sub add{
        my($self, $list) = @_;
        my $shortest = [sort {$a <=> $b} ($self->length(), $list->length())]->[0];
        my($x, $y) = ($self->tail(), $list->tail());
        my $sum = new LinkedList129();
        my $carry = 0;
        do{
            my $z;
            if($x && $x->value() && $y && $y->value()){
                $z = $x->value() + $y->value() + $carry;
                ($x, $y) = ($x->previous(), $y->previous());
            }
            elsif($x && $x->value() && !$y){
                $z = $x->value() + $carry;
                ($x, $y) = ($x->previous(), undef);
            }
            elsif(!$x->value() && $y->value()){
                $z = $y->value() + $carry;
                ($x, $y) = (undef, $y->previous());
            }
            if(length($z) == 2){
                $carry = 1;
                $sum->insert(int(substr($z, 1, 1)));
            }
            else{
                $carry = 0;
                $sum->insert($z);
            }

        }while($x || $y);
        return $sum;
    }
    true;
}

package main{
    my $l0 = new LinkedList129();
    $l0->insert(1);
    $l0->insert(2);
    $l0->insert(3);
    $l0->insert(4);
    $l0->insert(5);
    my $l1 = new LinkedList129();
    $l1->insert(6);
    $l1->insert(5);
    $l1->insert(5);
    my $sum = $l0->add($l1);
    print "    " . $l0->stringify();
    print "+\n";
    print "              " . $l1->stringify();
    print "---" x ($l0->length() * 2) . "\n";  
    print "    " . $sum->stringify_reverse();
}

Sample Run

$ perl perl/ch-2.pl
    1 -> 2 -> 3 -> 4 -> 5
+
              6 -> 5 -> 5
------------------------------
    1 -> 3 -> 0 -> 0 -> 0

Notes

My opinion on LinkedList problems may not be shared by the majority of Team PWC. I love Linked List problems!

Similar to the first part of Challenge 129 Class::Struct is used to create the data structure central tot he problem. This LinkedList implementation just has an insert() and two stringify functions, along with the required add().

The problem asks to sum two linked lists of single digit numbers. The add() function works in the same way that one would manually add the numbers. The sum of the two lists is represented as a new Linked List, but to represent it properly it is output in reverse. That should be fine for the purposes of this challenge. Other options are:

• a function for inserting at the end of the list, insert at each addition step
• holding the sum in an array and when add() is finished with all list elements use the existing insert() and create a LinkedList instance to return by shifting off the array.

References

Challenge 129

Class::Struct

Tie::RefHash