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 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
# Task 1: Max points.
# Find maximum number of points on a line
# See https:/wlmb.github.io/2020/12/28/PWC93/#task-1-max-points
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 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
}
sub add_point {
my $point=shift;
my $lines=shift;
foreach(my @previous_lines=@$lines){
push(@$lines, [$_->[0], $point]), next if @$_==1; # new two-point line
push(@$_, $point), next # add point to existing line if co-linear
if (($_->[1][0]-$_->[0][0])*($point->[1]-$_->[0][1])
==($_->[1][1]-$_->[0][1])*($point->[0]-$_->[0][0]))
}
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
Task 2: Sum Path
Submitted by: Mohammad S Anwar
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
# Task 2: Sum path.
# Sum all possible paths from the root to the leafs.
# See https:/wlmb.github.io/2020/12/28/PWC93/#task-2-sum-path
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;
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: ./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,[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:
./ch-2.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