## Perl weekly challenge 93

These are some answers to the Week 93 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

*Spoiler Alert:* This weekly challenge deadline is due in a few days (January 3, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

I'm not a great blogger - but I will try and explain my solutions to the Perl weekly challenge each week. I always try and look for interesting solutions to the problems at hand.

# Part 1

Not sure on the correct way to do this... I first looked at all the pairs of points - and looked to see what the direction was between the points. For those where the y-coordinates are different you can just use (x1-x2)/(y1-y2) to represent the slope. We also that flipping the order of the points gives the same value. For those canses where y is the same - the slop can be represented by an "infinity value" in my case i use "-"

We now keep a list keyed by points and directions, with the value being the number of times that point/direction combination has been seen

Finding the solution is simply finding the largest value in this list - this gives the max-number of points colinear to a single points

The answer is then this value + 1

sub most_points_in_line { my @nodes = @_; my %lines; foreach my $i (0..(@nodes-2)) { foreach my $j (($i+1)..(@nodes-1)) { my $dir = $nodes[$i][1] == $nodes[$j][1] ## Y values the same so division will fail ? '-' ## use "-" to represent infintiy. : ($nodes[$i][0]-$nodes[$j][0])/($nodes[$i][1]-$nodes[$j][1]); $lines{$i.':'.$dir}++; ## Add 1 to both the two nodes { as swapping the nodes over $lines{$j.':'.$dir}++; ## makes no difference we don't need to compute twice } } my $max = 0; ## Now we just need to find the maximum value. foreach (values %lines) { $max = $_ if $_ > $max; } return $max+1; }

**Note:** - this "trick" will fail if the direction calculation has rounding errors - in the examples this isn't the case - but care should be taken.

If we take the assumption from the examples that all the points on the plane are in fact integers - we can remove some of the issues with rounding errors by returning a slope as a ratio of integers. We do this by computing the gcd of the two values, and dividing dx & dy by this value.

```
sub most_points_in_line {
my @nodes = @_;
my %lines;
foreach my $i (0..(@nodes-2)) {
foreach my $j (($i+1)..(@nodes-1)) {
my $dir = '-';
my( $dx,$dy) = ( $nodes[$i][0]-$nodes[$j][0], $nodes[$i][1]-$nodes[$j][1] );
if( $dx && $dy ) {
my $gcd = gcd( $dx,$dy );
$dir = $dx/$gcd.'-'.$dy/$gcd;
} else {
$dir = $dx ? '-' : '|';
}
$lines{$i.':'.$dir}++;
$lines{$j.':'.$dir}++;
}
}
my $max = 0;
foreach (values %lines) {
$max = $_ if $_ > $max;
}
return $max+1;
}
## Note this gcd function works when n & m can have -ve values
## We convert them to positive values and remember the sign of
## the differences.
sub gcd {
my( $n,$m,$s ) = (@_,1);
($n,$m) = (-$n,-$m) if $n < 0;
if( $m < 0 ) {
$s = -1;
$m = -$m;
}
($n,$m) = ($m,$n) if $m>$n;
($n,$m) = ( $m, $n % $m ) while $n % $m;
return $m*$s;
}
```

# Part 2

Like last week I think Part 2 is easier than Part 1.

Not really sure what the input should be - but will by representing the tree as a series of nodes:

- Each node is an array consisting of up to 3 values;
- The value of the node
- The left and right sub-trees if they exists

So for example 1 we have:

[ 1, [ 2, [ 3 ], [ 4 ], ], ];

and for example 2 we have:

[ 1, [ 2, [ 4 ], ] [ 3, [ 5 ], [ 6 ], ], ];

To compute the sum of each route through the tree we start at the top, and work our way down the tree using recursion to find the sum of the sub-trees. As we work our way down the tree we remember the sum of the nodes that we have traversed through:

So in example 1.

- Start at node (1) - the sum of ancestors is 0
- We then look at the child trees (2) - the sum of it's ancestors is 1
- Then we look at the leaves (3) & (4) - the value they contribute are 6 and 7 respectively [the ancestor node total is 3 {1+2}]

This is relatively easy to convert to a simple algorithm:

```
sub tree_sum {
my ( $node,$sum ) = @_;
$sum||=0;
return $node->[0] + $sum if @{$node} < 2; ## This is a leaf!
return tree_sum( $node->[1], $node->[0] + $sum ) + ## Left tree total
( @{$node} == 3 ? tree_sum( $node->[2], $node->[0] + $sum ) : 0 );
## + right tree total if exists
}
```

## Leave a comment