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.

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

Solution

See below for explanation and any implementation-specific comments.

First Attempt

``````sub challenge(@pairs) {
my %lines;

for @pairs -> @pair {
my @pairs-to-compare = @pairs.grep(* ne @pair);

for @pairs-to-compare -> @other-pair {
my (\$x1, \$y1) = @pair;
my (\$x2, \$y2) = @other-pair;

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 x-intercept for uniqueness
my \$b = \$m eq 'undefined' ?? @pair[1] !! @pair[1] - (\$m * @pair[0]);

# Slope and y-intercept (or x-intercept) are unique, so this is all we need
%lines{"\$m:\$b"}++;                                                           # [2]

}
}
%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);
}

done-testing;
}
``````

This program runs as such:

``````\$ raku ch-1.raku 1 1 2 2 3 3
3

\$ raku ch-1.raku --test
ok 1 -
ok 2 -
not ok 3 -
1..3
# Failed test at /home/asmith/perlweeklychallenge-club/challenge-093/aaronreidsmith/raku/ch-1.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 \$.x-intercept;
has \$.y-intercept;
has Set \$.points is rw;
}

sub challenge(@points) {
my %lines;
for @points.kv -> \$index, \$point {
for @points[\$index+1..*] -> \$other-point {
my \$numerator = \$other-point.y - \$point.y;
my \$denominator = \$other-point.x - \$point.x;

my \$slope = \$denominator == 0 ?? 'undefined' !! \$numerator / \$denominator;

my \$y-intercept;
if \$slope eq 'undefined' {
\$y-intercept = \$point.y == 0 ?? 0 !! 'undefined';
} else {
\$y-intercept = \$point.y - (\$slope * \$point.x);
}

my \$x-intercept;
if \$slope eq 'undefined' {
\$x-intercept = \$point.x;
} elsif \$slope == 0 {
\$x-intercept = 'undefined'
} else {
\$x-intercept = -\$y-intercept / \$slope;
}

my \$points = Set.new("{\$point.x},{\$point.y}", "{\$other-point.x},{\$other-point.y}");

my \$key = "\$slope,\$x-intercept,\$y-intercept"; # [5]

if %lines{\$key}:exists {
%lines{\$key}.points ∪= \$points;
} else {
%lines{\$key} = Line.new(:\$slope, :\$x-intercept, :\$y-intercept, :\$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);
}

done-testing;
}
``````

This program runs as such:

``````\$ raku ch-1.raku 1 1 2 2 3 3
3

\$ raku ch-1.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:

1. For each point, compare it to each other point.
2. During the comparison calculate both the slope and (`\$m`) and the y-intercept (`\$b`)
3. Store the slope/y-intercept combo in a Hash called `%lines`.
• Increment if it exists, otherwise, set to `1`.
4. Comparing `(1, 1) <-> (2, 2)` and `(2, 2) <-> (1, 1)` is the same thing, so we store that in a `Set` to save ourselves a few cycles.
5. 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, 1)` and `(2, 1)` – m = 0, b = 1. New line – set to 1
2. `(1, 1)` and `(3, 1)` – m = 0, b = 1. Existing line – increment to 2
3. `(1, 1)` and `(4, 1)` – m = 0, b = 1. Existing line – increment to 3
4. `(2, 1)` and `(1, 1)` – Same as number 1 – skip
5. `(2, 1)` and `(3, 1)` – m = 0, b = 1. Existing line – increment to 4
6. `(2, 1)` and `(4, 1)` – m = 0, b = 1. Existing line – increment to 5
7. `(3, 1)` and `(1, 1)` – Same as number 2 – skip
8. `(3, 1)` and `(2, 1)` – Same as number 5 – skip
9. `(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 de-duplicate if necessary. Once those are defined, the logic is as follows:

1. Compare each point to each subsequent point.
• There is no need to look at past points, as it results in the “skips” shown above
2. During each comparison we calculate the slope, x-intercept and y-intercept.
• The reason for this is because if we have an undefined slope (vertical line), we need to know where along the x-axis it falls.
3. Once we have the above calculated, we create a joint key of all 3 to use in a Hash.
4. 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 the `Line` object (since it is a set, it will de-duplicate itself automatically). Otherwise, we create a new `Line` object and store it with the key from #3.
5. Finally, we find the `Line` with the most `Point`s and return the number of `Point`s.

1. 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 go-to solution.
2. `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 to `1`.
3. 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`.
4. 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`.
5. 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.

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

Solution

See below for explanation and any implementation-specific 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 build-tree(@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  = build-tree(@array, \$root.left, 2 * \$i + 1);
\$root.right = build-tree(@array, \$root.right, 2 * \$i + 2);
}
\$root;
}

sub challenge(Node \$root, @path is copy = ()) {
my \$path-sum = 0;
with \$root {
@path.push(\$root.value);

if !\$root.left.defined && !\$root.right.defined {
\$path-sum = @path.sum;
} else {
\$path-sum += challenge(\$root.left, @path);
\$path-sum += challenge(\$root.right, @path);
}
}
\$path-sum;
}

multi sub MAIN(*@N where all(@N) ~~ NodeValue) {
my \$root = build-tree(@N);
say challenge(\$root);
}

multi sub MAIN(Bool :\$test) {
use Test;

my @tests = (
(build-tree(('1', '2', 'Nil', '3', '4')), 13),
(build-tree(('1', '2', '3', '4', 'Nil', '5', '6')), 26),
(build-tree(('2', '7', '5', '2', '6', 'Nil', '9', 'Nil', '5', '11', '4', 'Nil')), 77)
);

for @tests -> (\$tree, \$expected) {
is(challenge(\$tree), \$expected);
}

done-testing;
}
``````

This program runs as such:

``````\$ raku ch-2.raku 1 2 Nil 3 4
13

\$ raku ch-2.raku 1 2 3 4 Nil 5 6
26

\$ raku ch-2.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 `build-tree` 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:

1. 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.
2. Push the current node’s value into our `@path` list.
3. If we are at a leaf node (no `left` or `right`), then calculate the sum of the path and return.
4. Otherwise, recurse both left and right ith the existing path and add it to the `\$path-sum` variable.

1. This line ensures that, even though we are expecting `Str` types, that all of them are either digits or `'Nil'`.
2. 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.