# Perl Weekly Challenge 129: trees and sums

One way to let me improve my knowledge about Raku (aka Perl 6) is to implement programs in it. Unluckily, I don’t have any production code to implement in Raku yet (sob!). So, why not try solving the Perl Weekly Challenge tasks?In the following, the assigned tasks for Challenge 110.

## PWC 129 - Task 1

The first task was about finding the distance from the*root*in a binary tree given a node tag (value). The tree, apparently is not a

*full binary*tree, meaning that a value could be on the left or the right of a node without any regard of its value.

The program results as follows:

```
class Node {
has Node $.left is rw;
has Node $.right is rw;
has Int $.value;
has Int $.level = 0;
method is-leaf() { ! $!left && ! $!right }
method find-from-here( Int $needle ) {
return self if $!value == $needle;
my $r = $!right.find-from-here( $needle ) if $!right;
return $r if $r;
my $l = $!left.find-from-here( $needle ) if $!left;
return $l if $l;
return Nil if self.is-leaf;
}
}
sub MAIN( Int $needle = 6 ) {
my $level = 1;
my $root = Node.new( value => 1,
left => Node.new( value => 2, level => $level ),
right => Node.new( value => 3, level => $level ) );
$root.right.right = Node.new( value => 4, level => ++$level );
$level++;
$root.right.right.right = Node.new( value => 6, level => $level );
$root.right.right.left = Node.new( value => 5, level => $level );
my $current = $root.find-from-here( $needle );
say "Found $needle at distance { $current.level }" if $current;
say "Not found $needle" if ! $current;
}
```

The whole program resides in the

`find-from-here`

method in the class `Node`

: such method returns the `Node`

object that has the same value of the searching for one, and this means a single node with a specific value can exist in the tree or the nearest one will be found.
Each node is initialized with a

*deep*

`level`

from the root, so once I found the right `Node`

it is trivial to get the distance from the root.
## PWC 129 - Task 2

The second task was about summing two linked list starting from the end (rightmost elements) even when the lists are unbalaced and keeping each sum value less than`10`

.
I created a

`LL`

class that implements a single node in the list, with the `next`

field for tracking the rightmost element of the current one.
To do the sum I created a

`pop-last`

method that removes and returns the rightmost one element from the list. More in detail, the element is not removed but made un-`available`

, but this is an internal detail. Therefore, I cycle for the `max`

length of the two lists, that means on all common elements, placing a default `0`

value where the element is absent in the list.
Then I do sum them usin a temporary variable `$sum`

and a `$carry`

depending on the final result.
The sum is placed into a `@sums`

array to build the final linked list.
The

`print`

method flies on the list to print it in the left-to-right order.
```
class LL {
has Int $.value = -1;
has Bool $.available is rw = True;
has LL $.next is rw = LL;
method length() {
my $counter = 1;
my $current = self;
$counter++ && $current = $current.next while ( $current.next );
return $counter;
}
method pop-last() {
my $current = self;
return Nil if ! $current.available;
while ( $current.available && $current.next && $current.next.available ) {
$current = $current.next;
}
$current.available = False;
return $current;
}
method print() {
print $!value;
if ( $!next ) {
print " -> ";
$!next.print;
}
}
}
sub MAIN() {
my $L1 = LL.new( value => 1 );
$L1.next = LL.new( value => 2 );
$L1.next.next = LL.new( value => 3 );
$L1.next.next.next = LL.new( value => 4 );
$L1.next.next.next.next = LL.new( value => 5 );
my $L2 = LL.new( value => 6 );
$L2.next = LL.new( value => 5 );
$L2.next.next = LL.new( value => 5 );
say "L1 = " ~ $L1.length;
say "L2 = " ~ $L2.length;
my ( $sum, $carry ) = 0, 0;
my @sums;
for 0 ..^ max( $L1.length, $L2.length ) {
my ( $a, $b ) = ( $L1.pop-last, $L2.pop-last );
my $sum = $carry
+ ( $a ?? $a.value !! 0 )
+ ( $b ?? $b.value !! 0 );
if ( $sum >= 10 ) {
$carry = ( $sum / 10 ).Int;
$sum %= 10;
}
else {
$carry = 0;
}
@sums.push: $sum;
}
my $R;
my $current;
my $previous;
for @sums {
$current = LL.new( value => $_, next => ( $previous ?? $previous !! Nil ) );
$previous = $current;
}
say $current.print;
}
```

After this implementation, I realized that it is possible to solve the same problem without the need for a specific class, that is using

`List`

or `Array`

as data structure:
```
sub MAIN() {
my @L1 = 1 , 2 , 3 , 4 , 5;
my @L2 = 6 , 5 , 5;
my @sums;
my $carry = 0;
for 1 .. max( @L1.elems, @L2.elems ) {
my $sum = ( @L1.elems >= $_ ?? @L1[ * - $_ ] !! 0 )
+ ( @L2.elems >= $_ ?? @L2[ * - $_ ] !! 0 )
+ $carry;
$carry = 0;
( $sum, $carry ) = ( $sum % 10, ( $sum / 10 ).Int ) if $sum >= 10;
@sums.push: $sum;
}
@sums.join( ' -> ' ).say;
}
```

The implementation is by far more compact, but the implementation alghoritm is the same.