RabbitFarm

Part 1

You are given set of co-ordinates @N. Write a script to count maximum points on a straight line when given co-ordinates plotted on 2-d plane.

Solution

use strict;
use warnings;
##
# You are given set of co-ordinates @N.
# Write a script to count maximum points 
# on a straight line when given co-ordinates 
# plotted on 2-d plane.
##
sub triangle_area{
    my($i, $j, $k) = @_;
    return ($i->[0] * ($j->[1] - $k->[1])) 
         + ($j->[0] * ($k->[1] - $i->[1]))
         + ($k->[0] * ($i->[1] - $j->[1]));
}

sub collinear_points{
    my(@points) = @_;
    my @collinear;
    for my $i (@points){
        for my $j (@points){
            for my $k (@points){
                if(triangle_area($i, $j, $k) == 0){
                    my $i_string = join(",", @{$i});
                    my $j_string = join(",", @{$j});
                    my $k_string = join(",", @{$k});
                    if(($i_string ne $j_string) && ($i_string ne $k_string) && ($j_string ne $k_string)){
                        my $has_i = grep { $i_string eq join(",", @{$_}) } @collinear;
                        push @collinear, $i if !$has_i;
                        my $has_j = grep { $j_string eq join(",", @{$_}) } @collinear;
                        push @collinear, $j if !$has_j;
                        my $has_k = grep { $k_string eq join(",", @{$_}) } @collinear;
                        push @collinear, $k if !$has_k;
                    }
                }
            }
        }
    }
    return @collinear;
}

MAIN:{
    my @N;
    @N = ([5,3], [1,1], [2,2], [3,1], [1,3]);
    my @collinear = collinear_points(@N);
    print "There are a maximum of " . @collinear . " collinear points.\n"
}

Sample Run

$ perl perl/ch-1.pl
There are a maximum of 3 collinear points.

Notes

Keep in mind that any two points determine a line. Therefore to consider all possible non-trivial lines we need to review all triples of points. This method will work in the most general case when the starting data may contain multiple lines with a larger number of points.

In determining collinearity I calculate the area of a triangle using the triple of points. If the area is zero we know that all the points lay on the same line.

Part 2

You are given a binary tree containing only the numbers 0-9. Write a script to sum all possible paths from root to leaf.

Solution

use strict;
use warnings;
##
# You are given a binary tree containing 
# only the numbers 0-9.
# Write a script to sum all possible paths 
# from root to leaf.
##
use Graph;

sub travserse_sum{
    my($tree) = @_;
    my @paths = build_paths($tree);
    my $path_sum = 0;
    for my $path (@paths){
        $path_sum +=  unpack("%32C*", pack("C*", @{$path})); 
    }
    return $path_sum;
}

sub build_paths {
   my ($graph) = @_;
   my @paths;
   local *_helper = sub{
      my $v = $_[-1];
      my @successors = $graph->successors($v);
      if(@successors){
         _helper(@_, $_) for @successors;
      } 
      else{
         push @paths, [@_];
      }
   };
   _helper($_) for $graph->source_vertices();
   return @paths;
}

MAIN:{
    my $Tree;
    $Tree = new Graph();
    $Tree->add_vertices(1, 2, 3, 4);
    $Tree->add_edge(1, 2);
    $Tree->add_edge(2, 3);
    $Tree->add_edge(2, 4);
    print travserse_sum($Tree) . "\n";
    
    $Tree = new Graph();
    $Tree->add_vertices(1, 2, 3, 4, 5, 6);
    $Tree->add_edge(1, 2);
    $Tree->add_edge(1, 3);
    $Tree->add_edge(2, 4);
    $Tree->add_edge(3, 5);
    $Tree->add_edge(3, 6);
    print travserse_sum($Tree) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
13
26

Notes

This is straightforward enough, at a high level anyway: (1) Get all paths and then (2) sum all the nodes on the paths.

• I am always happy to have a chance to use the Graph module!
• The Graph module has a bunch of nice algorithms implemented but what we want here is not a shortest path but all paths. The Graph module doesn’t have anything for us to use for that. Implementing a recursive Depth First Search and collecting all the paths is not such a hard thing to do, but in the Holiday Spirit (i.e. laziness) I just re-used Ikegami’s code. See the References section.
• I first used the pack/unpack trick for summing array back in Challenge 007.

References

Collinear Points

All Paths