## 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