Merge pull request #4866 from adamcrussell/challenge-129

solutions to challenge 129

3 files changed, 235 insertions, 0 deletions

diff --git a/challenge-129/adam-russell/blog.txt b/challenge-129/adam-russell/blog.txt
new file mode 100644
index 0000000000..c486933b08
--- /dev/null
+++ b/challenge-129/adam-russell/blog.txt
@@ -0,0 +1 @@
+http://www.rabbitfarm.com/cgi-bin/blosxom/perl/2021/09/12
diff --git a/challenge-129/adam-russell/perl/ch-1.pl b/challenge-129/adam-russell/perl/ch-1.pl
new file mode 100644
index 0000000000..63f8c70296
--- /dev/null
+++ b/challenge-129/adam-russell/perl/ch-1.pl
@@ -0,0 +1,101 @@
+use strict;
+use warnings;
+##
+# 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.   
+##
+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";
+} 
diff --git a/challenge-129/adam-russell/perl/ch-2.pl b/challenge-129/adam-russell/perl/ch-2.pl
new file mode 100644
index 0000000000..966a6343ff
--- /dev/null
+++ b/challenge-129/adam-russell/perl/ch-2.pl
@@ -0,0 +1,133 @@
+use strict;
+use warnings;
+##
+# 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.
+##
+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();
+}
\ No newline at end of file