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

About James Curtis-Smith

user-pic Perl developer for nearly 30 years now, mainly in maintenance scripts and web pages, using mod_perl.