Perl Weekly Challenge 93
I was going to stop adding my test cases (to the blog, not the code) this week, but after writing a solution that passed the provided test cases for part one, I wrote a new test that it failed and had to rewrite the whole thing. Because of that, today’s solutions still have the tests included. Additionally, in part one, I will go through both the failing solution and the corrected one.
Task 1: Max Points
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
Solution
See below for explanation and any implementationspecific comments.
First Attempt
sub challenge(@pairs) {
my %lines;
my $alreadycompared = Set.new;
for @pairs > @pair {
my @pairstocompare = @pairs.grep(* ne @pair);
for @pairstocompare > @otherpair {
my ($x1, $y1) = @pair;
my ($x2, $y2) = @otherpair;
next if "$x1,$y1:$x2,$y2" ∈ $alreadycompared  "$x2,$y2:$x1,$y1" ∈ $alreadycompared; # [1]
my $numerator = $y2  $y1;
my $denominator = $x2  $x1;
# Find the slope
my $m = $denominator == 0 ?? 'undefined' !! $numerator / $denominator;
# If it is a vertical line, use the xintercept for uniqueness
my $b = $m eq 'undefined' ?? @pair[1] !! @pair[1]  ($m * @pair[0]);
# Slope and yintercept (or xintercept) are unique, so this is all we need
%lines{"$m:$b"}++; # [2]
$alreadycompared ∪= "$x1,$y1:$x2,$y2";
}
}
%lines.max(> $entry { $entry.value }).value;
}
multi sub MAIN(*@N where all(@N) ~~ Int && @N.elems %% 2) { # [3]
my @pairs = @N.map(> $x, $y { ($x, $y) });
say challenge(@pairs);
}
multi sub MAIN(Bool :$test) {
use Test;
my @tests = (
(((1, 1), (2, 2), (3, 3)), 3),
(((1, 1), (2, 2), (3, 1), (1, 3), (5, 3)), 3),
(((1, 1), (2, 1), (3, 1), (4, 1)), 4)
);
for @tests > (@pairs, $expected) {
is(challenge(@pairs), $expected);
}
donetesting;
}
This program runs as such:
$ raku ch1.raku 1 1 2 2 3 3
3
$ raku ch1.raku test
ok 1 
ok 2 
not ok 3 
1..3
# Failed test at /home/asmith/perlweeklychallengeclub/challenge093/aaronreidsmith/raku/ch1.raku line 47
# expected: '4'
# got: '6'
# You failed 1 test of 3
Corrected Solution
As you can see, the above solution fails for my added test case. We will explore this below, but here is the corrected version (with an additional test case):
class Point {
has $.x;
has $.y;
multi method new($x, $y) { # [4]
self.bless(:$x, :$y);
}
}
class Line {
has $.slope;
has $.xintercept;
has $.yintercept;
has Set $.points is rw;
}
sub challenge(@points) {
my %lines;
for @points.kv > $index, $point {
for @points[$index+1..*] > $otherpoint {
my $numerator = $otherpoint.y  $point.y;
my $denominator = $otherpoint.x  $point.x;
my $slope = $denominator == 0 ?? 'undefined' !! $numerator / $denominator;
my $yintercept;
if $slope eq 'undefined' {
$yintercept = $point.y == 0 ?? 0 !! 'undefined';
} else {
$yintercept = $point.y  ($slope * $point.x);
}
my $xintercept;
if $slope eq 'undefined' {
$xintercept = $point.x;
} elsif $slope == 0 {
$xintercept = 'undefined'
} else {
$xintercept = $yintercept / $slope;
}
my $points = Set.new("{$point.x},{$point.y}", "{$otherpoint.x},{$otherpoint.y}");
my $key = "$slope,$xintercept,$yintercept"; # [5]
if %lines{$key}:exists {
%lines{$key}.points ∪= $points;
} else {
%lines{$key} = Line.new(:$slope, :$xintercept, :$yintercept, :$points);
}
}
}
%lines.max({ $_.value.points.elems }).value.points.elems;
}
multi sub MAIN(*@N where all(@N) ~~ Int && @N.elems %% 2) {
my @pairs = @N.map(> $x, $y { Point.new($x, $y) });
say challenge(@pairs);
}
multi sub MAIN(Bool :$test) {
use Test;
my @tests = (
((Point.new(1, 1), Point.new(2, 2), Point.new(3, 3)), 3),
((Point.new(1, 1), Point.new(2, 2), Point.new(3, 1), Point.new(1, 3), Point.new(5, 3)), 3),
((Point.new(1, 1), Point.new(2, 1), Point.new(3, 1), Point.new(4, 1)), 4),
((Point.new(1, 1), Point.new(1, 2), Point.new(2, 1), Point.new(3, 1), Point.new(4, 1)), 4)
);
for @tests > (@points, $expected) {
is(challenge(@points), $expected);
}
donetesting;
}
This program runs as such:
$ raku ch1.raku 1 1 2 2 3 3
3
$ raku ch1.raku test
ok 1 
ok 2 
ok 3 
ok 4 
1..4
Explanation
For both of these there is some logic in MAIN
that I will explain once. Basically, we expect the user to pass us one or more integers, and they have to pass us an even number of integers so that we can split it into pairs. We then pass this to the challenge
subroutine.
First Attempt
The logic here is as follows:
 For each point, compare it to each other point.
 During the comparison calculate both the slope and (
$m
) and the yintercept ($b
)  Store the slope/yintercept combo in a Hash called
%lines
. Increment if it exists, otherwise, set to
1
.
 Increment if it exists, otherwise, set to
 Comparing
(1, 1) <> (2, 2)
and(2, 2) <> (1, 1)
is the same thing, so we store that in aSet
to save ourselves a few cycles.  Finally, find the maximum entry by value and return it.
This logic breaks down in the case of a horizontal line (see test number 3). The reason it breaks down is because the pairs are evaluated like this:
(1, 1)
and(2, 1)
– m = 0, b = 1. New line – set to 1(1, 1)
and(3, 1)
– m = 0, b = 1. Existing line – increment to 2(1, 1)
and(4, 1)
– m = 0, b = 1. Existing line – increment to 3(2, 1)
and(1, 1)
– Same as number 1 – skip(2, 1)
and(3, 1)
– m = 0, b = 1. Existing line – increment to 4(2, 1)
and(4, 1)
– m = 0, b = 1. Existing line – increment to 5(3, 1)
and(1, 1)
– Same as number 2 – skip(3, 1)
and(2, 1)
– Same as number 5 – skip(3, 1)
and(4, 1)
– m  0, b = 1. Existing line – increment to 6
As you can see, even with four points, we generate an answer of six. My first though was to just take the minimum of the number of points and the longest run we found, which would yield four. However, if we had any points not on the line (look at test 4 the corrected solution), then it would yield the wrong answer as well.
Corrected Solution
The logic here is similar, but accounts for the above situation. First, you will notice I added a Point
and Line
class, to make things a little easier. The Line
class also contains a set of points along that line that we can use to deduplicate if necessary. Once those are defined, the logic is as follows:
 Compare each point to each subsequent point.
 There is no need to look at past points, as it results in the “skips” shown above
 During each comparison we calculate the slope, xintercept and yintercept.
 The reason for this is because if we have an undefined slope (vertical line), we need to know where along the xaxis it falls.
 Once we have the above calculated, we create a joint key of all 3 to use in a Hash.
 Using the above key, we look up our string in the
%lines
Hash. If it exists, we add the points used to find it to the points contained in theLine
object (since it is a set, it will deduplicate itself automatically). Otherwise, we create a newLine
object and store it with the key from #3.  Finally, we find the
Line
with the mostPoint
s and return the number ofPoint
s.
Specific Comments
 We need to use a string here or else the
Set
will erroneously combine some of our points. Sets flatten their arguments in Raku, which makes it tricky to store nested items. This has been my goto solution. Hash
objects behave kind of like default dicts in Python in that if you use++
on a key that does not exist, it will create the key and increment it to1
. Raku has an operator specifically for “divisible by.” In other languages, you might see
x % 2 == 0
to check if something is divisible by 2, but in Raku you can say$x %% 2
.  Raku, like some other languages, allows us to define multiple constructors. The default one is created for us and takes named arguments. This one takes positional arguments and passes them to the default constructor via
self.bless
.  Similar to #1,
Hash
objects always use string keys. So if we need some kind of compound key, we need to cast it to a string as seen here.
Task 2: Sum Path
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)
Solution
See below for explanation and any implementationspecific comments.
subset NodeValue of Str where { $_ ~~ /^<digit>$/  $_ eq 'Nil' } # [1]
class Node {
has Node $.left is rw = Nil; # [2]
has Node $.right is rw = Nil;
has Int $.value = 0;
}
sub buildtree(@array, $root is copy = Nil, Int $i = 0) {
if $i < @array.elems && @array[$i] ne 'Nil' {
$root = Node.new(value => @array[$i].Int);
$root.left = buildtree(@array, $root.left, 2 * $i + 1);
$root.right = buildtree(@array, $root.right, 2 * $i + 2);
}
$root;
}
sub challenge(Node $root, @path is copy = ()) {
my $pathsum = 0;
with $root {
@path.push($root.value);
if !$root.left.defined && !$root.right.defined {
$pathsum = @path.sum;
} else {
$pathsum += challenge($root.left, @path);
$pathsum += challenge($root.right, @path);
}
}
$pathsum;
}
multi sub MAIN(*@N where all(@N) ~~ NodeValue) {
my $root = buildtree(@N);
say challenge($root);
}
multi sub MAIN(Bool :$test) {
use Test;
my @tests = (
(buildtree(('1', '2', 'Nil', '3', '4')), 13),
(buildtree(('1', '2', '3', '4', 'Nil', '5', '6')), 26),
(buildtree(('2', '7', '5', '2', '6', 'Nil', '9', 'Nil', '5', '11', '4', 'Nil')), 77)
);
for @tests > ($tree, $expected) {
is(challenge($tree), $expected);
}
donetesting;
}
This program runs as such:
$ raku ch2.raku 1 2 Nil 3 4
13
$ raku ch2.raku 1 2 3 4 Nil 5 6
26
$ raku ch2.raku test
ok 1 
ok 2 
ok 3 
1..3
Explanation
The hardest part of this, for me, was giving the user some kind of command line interface to be able to define their own trees (something that wasn’t explicitly part of the problem). We basically just use the array implementation of a binary tree where @array[0]
is the root, @array[1]
and @array[2]
are the second row, etc. Anything that is Nil
is recognized as an empty node (i.e., an unbalanced tree). So, for example, 1 2 Nil 3 4
represents the first example shown above.
MAIN
does some validation to make sure everything is either a number or Nil
and then let’s buildtree
convert the array into an actual tree (by creating Node
objects). Once we have a tree, we give it to challenge
which implements the following logic:
 If the node is
Nil
return 0. Technically unnecessary since we check if we are at a terminal node before recursing, but doesn’t hurt to have.
 Push the current node’s value into our
@path
list.  If we are at a leaf node (no
left
orright
), then calculate the sum of the path and return.  Otherwise, recurse both left and right ith the existing path and add it to the
$pathsum
variable.
Specific Comments
 This line ensures that, even though we are expecting
Str
types, that all of them are either digits or'Nil'
.  By default, class attributes are read only, so by defining them as
is rw
(read/write), we say that they are mutable. Additionally, we assign these attributes default values.
Final Thoughts
This challenge is a good case study in testdriven development! Be sure to write edgecase tests to make sure everything is behaving as expected. In the case of part one, it was not behaving as expected and required a rewrite.