Perl Weekly Challenge 93.
My solutions (task 1 and task 2) to the The Weekly Challenge  093.
Task 1: Max Points
Submitted by: Mohammad S Anwar
You are given set of coordinates @N
.
Write a script to count maximum points on a straight line when given coordinates plotted on 2d 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
# Task 1: Max points.
# Find maximum number of points on a line
# See https:/wlmb.github.io/2020/12/28/PWC93/#task1maxpoints
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 {"($_>[0],$_>[1])"}
sort {$a>[0] <=> $b>[0]
 ($a>[0] == $b>[0] && $a>[1] <=> $b>[1])}
@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 twoelement line with all the previous degenerate lines, and it may be added to other lines with points Rm if it is colinear, that is, if R_{1}R_{0} is parallel to rnR0, or equivalently, if (x1x0)*(ynx0)==(y1y0)*(xnx0). 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
}
sub add_point {
my $point=shift;
my $lines=shift;
foreach(my @previous_lines=@$lines){
push(@$lines, [$_>[0], $point]), next if @$_==1; # new twopoint line
push(@$_, $point), next # add point to existing line if colinear
if (($_>[1][0]$_>[0][0])*($point>[1]$_>[0][1])
==($_>[1][1]$_>[0][1])*($point>[0]$_>[0][0]))
}
push @$lines, [$point]; # new onepoint degenerate line
}
Print usage in case of input errors.
sub usage {
say <<'END_USAGE';
Usage: ./ch1.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 colinear points rn=(xn,yn) on the plane.
END_USAGE
exit 1;
}
Examples 1 and 2:
./ch1.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:
./ch1.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
Task 2: Sum Path
Submitted by: Mohammad S Anwar
You are given binary tree containing numbers 09 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 subtrees plus the node times the number of subtrees.
First I setup pragmas and packages.
# Perl weekly challenge 093
# Task 2: Sum path.
# Sum all possible paths from the root to the leafs.
# See https:/wlmb.github.io/2020/12/28/PWC93/#task2sumpath
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 subtrees.
usage() unless @ARGV; # check there are arguments
foreach(@ARGV){
usage() unless /^[\]\[,\s09]*$/; # 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 subtree, 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;
die Dumper($tree), " doesn't start with a number" if ref $node;
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: ./ch2.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 12:
./ch2.pl "[1,[2,[3],[4]]]"\
"[1,[2,[4]],[3,[5],[6]]]"
Results:
Input: [1,[2,[3],[4]]]
Sum_path: 13
Number of paths: 2
Input: [1,[2,[4]],[3,[5],[6]]]
Sum_path: 26
Number of paths: 3
The tree need not be binary, as illustrated in some of the example below:
./ch2.pl "[0]"\
"[1,[2,[3,[4]]]]"\
"[1,[1,[1],[1]],[1,[1],[1]]]"\
"[1,[1,[1],[1],[1]],[1,[1],[1],[1]],[1,[1],[1],[1]]]"
Results:
Input: [0]
Sum_path: 0
Number of paths: 1
Input: [1,[2,[3,[4]]]]
Sum_path: 10
Number of paths: 1
Input: [1,[1,[1],[1]],[1,[1],[1]]]
Sum_path: 12
Number of paths: 4
Input: [1,[1,[1],[1],[1]],[1,[1],[1],[1]],[1,[1],[1],[1]]]
Sum_path: 27
Number of paths: 9