# Perl Weekly Challenge 93.

My solutions (task 1 and task 2) to the The Weekly Challenge - 093.

Submitted by: Mohammad S Anwar 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.

Example 1:

``````|
|     x
|   x
| x
+ _ _ _ _

Input: (1,1), (2,2), (3,3)
Output: 3
``````

Example 2:

``````|
|
| x       x
|   x
| x   x
+ _ _ _ _ _

Input: (1,1), (2,2), (3,1), (1,3), (5,3)
Output: 3
``````

To solve this problem we simply add points, one at a time, to a set of lines. At the end we choose the one that has the most points. Seems simple.

First, some pragmas and packages.

``````# Perl weekly challenge 093
# Find maximum number of points on a line
use warnings;
use strict;
use v5.10;

use List::Util qw(all reduce);
use Scalar::Util qw(looks_like_number);
``````

Take the lines from strings in the command line. For simplicity, assume each line is input as a string of space separated points, and each point is a pair of numbers within round parenthesis. Add them one by one to the list of points as long as they are (numerically) unique.

``````usage() unless @ARGV; # Expect at least one argument
while(my \$points=shift @ARGV){ # for each input line
my @points;
my %seen;
foreach(split ' ', \$points){ # separate it in points
usage()
unless /^\((.*),(.*)\)\$/
and looks_like_number(\$1) and looks_like_number(\$2);
push @points, [\$1,\$2] unless \$seen{0+\$1}{0+\$2}++; # 0+ trick.
}
my @max_line=max_line(@points); # choose the line with most points
say "Input: \$points\nLongest line: ", # and print it sorted
join(" ", map {"(\$_->,\$_->)"}
sort {\$a-> <=> \$b->
|| (\$a-> == \$b-> && \$a-> <=> \$b->)}
@max_line),
"\nMax points: ", scalar @max_line, "\n"; # finally print the 'length'
}
``````

Each new point rn=(xn,yn) is the start of a new degenerate line, it forms a new two-element line with all the previous degenerate lines, and it may be added to other lines with points Rm if it is co-linear, that is, if R1-R0 is parallel to rn-R0, or equivalently, if (x1-x0)*(yn-x0)==(y1-y0)*(xn-x0). I’m using an exact comparison. For a realistic use, a test for approximate equality may be more useful.

``````sub max_line {
my @lines;
add_point(\$_, \@lines) foreach(@_); # build all lines
return @{my \$max=reduce {@\$a > @\$b?\$a:\$b } @lines}; #return longest line
}

my \$point=shift;
my \$lines=shift;
foreach(my @previous_lines=@\$lines){
push(@\$lines, [\$_->, \$point]), next if @\$_==1; # new two-point line
push(@\$_, \$point), next # add point to existing line if co-linear
if ((\$_->-\$_->)*(\$point->-\$_->)
==(\$_->-\$_->)*(\$point->-\$_->))
}
push @\$lines, [\$point]; # new one-point degenerate line
}
``````

Print usage in case of input errors.

``````sub usage {
say <<'END_USAGE';
Usage: ./ch-1.pl "(x0,y0) (x1,y1),..." ["(x'0,y'0)..." ...]
where xn and yn are numbers and there is no space within the parenthesis.

Find the maximum number of co-linear points rn=(xn,yn) on the plane.
END_USAGE
exit 1;
}
``````

Examples 1 and 2:

``````./ch-1.pl "(1,1) (2,2) (3,3)"\
"(1,1) (2,2) (3,1) (1,3) (5,3)"
``````

Results:

``````Input: (1,1) (2,2) (3,3)
Longest line: (1,1) (2,2) (3,3)
Max points: 3

Input: (1,1) (2,2) (3,1) (1,3) (5,3)
Longest line: (1,3) (2,2) (3,1)
Max points: 3
``````

Other examples:

``````./ch-1.pl "(0,0) (0,0) (1,0)"\
"(0,0) (1,0) (-2,2) (0,1) (-1,1)"
``````

Results:

``````Input: (0,0) (0,0) (1,0)
Longest line: (0,0) (1,0)
Max points: 2

Input: (0,0) (1,0) (-2,2) (0,1) (-1,1)
Longest line: (-2,2) (-1,1) (0,0)
Max points: 3
``````

You are given binary tree containing numbers 0-9 only.

Write a script to sum all possible paths from root to leaf.

Example 1:

``````Input:
1
/
2
/ \
3   4

Output: 13
``````

as sum two paths (1->2->3) and (1->2->4)

Example 2:

``````Input:
1
/ \
2   3
/   / \
4   5   6

Output: 26
``````

as sum three paths (1->2->4), (1->3->5) and (1->3->6)

I solve this problem recursively: The sum of all paths from a node is the sum for all its sub-trees plus the node times the number of sub-trees.

First I setup pragmas and packages.

``````# Perl weekly challenge 093
# Sum all possible paths from the root to the leafs.
use warnings;
use strict;
use v5.10;
use Data::Dumper;
``````

Read the trees as string arguments from the command line. Represent the trees simply as perl arrays, where the first element is the node and the rest are the sub-trees.

``````usage() unless @ARGV; # check there are arguments
foreach(@ARGV){
usage() unless /^[\]\[,\s0-9]*\$/; # check argument
my \$tree=eval \$_; # and assume the risks.
die "Couldn't evaluate \$_: \$@" if \$@;
my (\$sum_paths, \$number_of_paths)=sum_path(\$tree);
say "Input: \$_\nSum_path: \$sum_paths\nNumber of paths: \$number_of_paths\n";
}
``````

The work is done by the recursive routine for summing trees. It first extracts the node as the first element and calls itself for each sub-tree, each of which ought to be represented by a perl array. It returns the sum of all paths and the number of paths. In case of errors it gives some crude diagnostics, dumping the erroneous tree.

``````sub sum_path {
my \$tree=shift;
die Dumper(\$tree),  " is not an array" unless ref \$tree eq "ARRAY";
my @tree=@\$tree;
my \$node=shift @tree;
my \$sum_of_paths=0;
my \$number_of_paths=@tree?0:1; # 1 for leaves
foreach(@tree){
my (\$sum_of_subpaths, \$number_of_subpaths)=sum_path(\$_);
\$sum_of_paths+=\$sum_of_subpaths;
\$number_of_paths+=\$number_of_subpaths;
}
\$sum_of_paths+=\$node*\$number_of_paths;
return(\$sum_of_paths, \$number_of_paths);
}
``````

Usage instructions.

``````sub usage {
say <<'END_USAGE';
Usage: ./ch-2.pl "tree_0" "tree_1"...
where tree_n is a tree represented by a perl array of the form
[node_n, [subtree_0, subtree_1...]]
and the nodes are digits.
Find the sum of nodes along all paths through the given trees.
END_USAGE
exit 1;
}
``````

Examples 1-2:

``````./ch-2.pl "[1,[2,,]]"\
"[1,[2,],[3,,]]"
``````

Results:

``````Input: [1,[2,,]]
Sum_path: 13
Number of paths: 2

Input: [1,[2,],[3,,]]
Sum_path: 26
Number of paths: 3
``````

The tree need not be binary, as illustrated in some of the example below:

``````./ch-2.pl ""\
"[1,[2,[3,]]]"\
"[1,[1,,],[1,,]]"\
"[1,[1,,,],[1,,,],[1,,,]]"
``````

Results:

``````Input: 
Sum_path: 0
Number of paths: 1

Input: [1,[2,[3,]]]
Sum_path: 10
Number of paths: 1

Input: [1,[1,,],[1,,]]
Sum_path: 12
Number of paths: 4

Input: [1,[1,,,],[1,,,],[1,,,]]
Sum_path: 27
Number of paths: 9
``````
Written on December 28, 2020