## 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] == \$nodes[\$j]  ## Y values the same so division will fail
? '-'                             ## use "-" to represent infintiy.
:  (\$nodes[\$i]-\$nodes[\$j])/(\$nodes[\$i]-\$nodes[\$j]);
\$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]-\$nodes[\$j], \$nodes[\$i]-\$nodes[\$j] );
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-> + \$sum if @{\$node} < 2; ## This is a leaf!
return tree_sum( \$node->, \$node-> + \$sum ) + ## Left tree total
( @{\$node} == 3 ? tree_sum( \$node->, \$node-> + \$sum ) : 0 );
## + right tree total if exists
}
`````` Perl developer for nearly 30 years now, mainly in maintenance scripts and web pages, using mod_perl. I also code a lot in PHP (20+yrs), and also extensive experience in HTML (27+yrs), Javascript(25+yrs), CSS (24+yrs) and SASS.