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

}