diff options
| -rw-r--r-- | challenge-129/adam-russell/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-129/adam-russell/perl/ch-1.pl | 101 | ||||
| -rw-r--r-- | challenge-129/adam-russell/perl/ch-2.pl | 133 |
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 |