# 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-> * (\$j-> - \$k->))
+ (\$j-> * (\$k-> - \$i->))
+ (\$k-> * (\$i-> - \$j->));
}

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.
``````

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.

Collinear Points

All Paths