Triangular Rectangle with Raku
[170] Published 20. February 2022.This is my response to the Perl Weekly Challenge #152.
Challenge #152.1: Triangle Sum Path
Write a script to find the minimum sum path from top to bottom.
Example 1:
Input: $triangle = [ [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8] ]
1
5 3
2 3 4
7 1 0 2
6 4 5 2 8
Output: 8
Minimum Sum Path = 1 + 3 + 2 + 0 + 2 => 8
Input: $triangle = [ [5], [2,3], [4,1,5], [0,1,2,3], [7,2,4,1,9] ]
5
2 3
4 1 5
0 1 2 3
7 2 4 1 9
Output: 9
Minimum Sum Path = 5 + 2 + 1 + 0 + 1 => 9
I would assume that the path could only go to the child directly below (i.e. slightly to the left, or slightly to the right of) any given node, but it seems that we can go from any value in one row to any value in the row below it. So this boils down to selecting the lowest value in each row, and adding them, together.
The red paths are the ones requested by the challenge, and the green ones (and yes, the colour choice was deliberate) are the ones I would go for; choosing children nodes only.
The input matrix format from last week can be used here, giving a very compact program:
File: triangle-sum-path
#! /usr/bin/env raku
unit sub MAIN (Str $tree = "1 | 3 5 | 2 3 4 | 7 1 0 2 | 6 4 5 2 8"); # [1]
say $tree.split("|")>>.words>>.min.sum; # [2]
[1] Note the default tree, and the total lack of type checking - both the values and the number of items in each row.
[2]
Split the string into one string for each row (with .split("|"),
then split each of those strings into a list of values (with >>.words),
and then collapse each list of values (the rows) into a single value woth the lowest
value (with >>.min. The result so far is a list of the lowest value in each
row, and applying .sum on this list gives the desired result.
See
docs.raku.org/routine/min
for more information about min.
See
docs.raku.org/routine/sum
for more information about sum.
Running it:
$ ./triangle-sum-path
8
$ ./triangle-sum-path "5 | 2 3 | 4 1 5 | 0 1 2 3 | 7 2 4 1 9"
9
Looking good, if we accept the excessive zigzag movement (the red paths in the illustrations).
Note the total lack of error checking; the types of values, and the incremental number of items in each row.
Let us have a go at fixing the problems, including the zigzag-problem.
The following program is based on «binary-tree-depth» from last week, but without the class.
File: triangle-sum-path-child
#! /usr/bin/env raku
unit sub MAIN (Str $tree = "1 | 5 3 | 2 3 4 | 7 1 0 2 | 6 4 5 2 8",
:v(:$verbose), :m($max)); # [1]
my @tree = $tree.split("|")>>.words>>.Numeric; # [2]
my $rows = @tree.elems;
for 1 .. $rows -> $row
{
die "Wrong number of elements in row $row ({ (@tree[$row - 1]).elems } \
instead of $row)" unless @tree[$row - 1] == $row; # [3]
}
say ": Tree height: $rows";
my @paths; # [4]
my @values; # [5]
traverse(0, (), ()); # [6]
sub traverse ($current, @path is copy, @value is copy) # [6]
{
@value.push: @tree[@path.elems][$current]; # [7]
@path.push: $current; # [8]
if (@path.elems < $rows) # [9]
{
traverse($current, @path, @value); # [9a]
traverse($current +1, @path, @value); # [9b]
}
else
{
say ": Values: [{ @value.join(", ") }] (indices [{ @path.join(", ") }) \
- sum { @value.sum }" if $verbose;
@paths.push: @path;
@values.push: @value;
return;
}
}
say $max ?? @values>>.sum.max !! @values>>.sum.min; # [1a]
[1] Why the minimum value? The maximum is just as easy, enabled with the «--max» command line argument.
See
docs.raku.org/routine/max
for more information about max.
[2] Coerce the arguments to numeric values. This will blow up if they are not numeric, but that is ok.
[3] Ensure that we have a pyramid, with the same number of items in the row as the row number (starting at 1).
[4] All the paths, as indices from each row, will end up here.
[5] The actual values (instead of the indices). This is done so that we can get the sum easily.
[6] Off we go, recursively. The first value is the index (zero based) of the value on the current row.
[7] Save the value at the current index,
[8] and the index itself.
[9] Have we reached the last (bottom) row? If not, recursively follow the two child nodes. The left child has the same index, and the right one has the index added by 1.
[10] We are at the last row. Save the path (both the index and value path).
Running it:
$ ./triangle-sum-path-child -v
9
$ ./triangle-sum-path-child -m
21
$ ./triangle-sum-path-child -v
: Tree height: 5
: Values: [1, 5, 2, 7, 6] (indices [0, 0, 0, 0, 0) - sum 21
: Values: [1, 5, 2, 7, 4] (indices [0, 0, 0, 0, 1) - sum 19
: Values: [1, 5, 2, 1, 4] (indices [0, 0, 0, 1, 1) - sum 13
: Values: [1, 5, 2, 1, 5] (indices [0, 0, 0, 1, 2) - sum 14
: Values: [1, 5, 3, 1, 4] (indices [0, 0, 1, 1, 1) - sum 14
: Values: [1, 5, 3, 1, 5] (indices [0, 0, 1, 1, 2) - sum 15
: Values: [1, 5, 3, 0, 5] (indices [0, 0, 1, 2, 2) - sum 14
: Values: [1, 5, 3, 0, 2] (indices [0, 0, 1, 2, 3) - sum 11
: Values: [1, 3, 3, 1, 4] (indices [0, 1, 1, 1, 1) - sum 12
: Values: [1, 3, 3, 1, 5] (indices [0, 1, 1, 1, 2) - sum 13
: Values: [1, 3, 3, 0, 5] (indices [0, 1, 1, 2, 2) - sum 12
: Values: [1, 3, 3, 0, 2] (indices [0, 1, 1, 2, 3) - sum 9
: Values: [1, 3, 4, 0, 5] (indices [0, 1, 2, 2, 2) - sum 13
: Values: [1, 3, 4, 0, 2] (indices [0, 1, 2, 2, 3) - sum 10
: Values: [1, 3, 4, 2, 2] (indices [0, 1, 2, 3, 3) - sum 12
: Values: [1, 3, 4, 2, 8] (indices [0, 1, 2, 3, 4) - sum 18
9
$ ./triangle-sum-path-child "5 | 2 3 | 4 1 5 | 0 1 2 3 | 7 2 4 1 9"
: Tree height: 5
11
$ ./triangle-sum-path-child -m "5 | 2 3 | 4 1 5 | 0 1 2 3 | 7 2 4 1 9"
: Tree height: 5
25
$ ./triangle-sum-path-child -v "5 | 2 3 | 4 1 5 | 0 1 2 3 | 7 2 4 1 9"
: Tree height: 5
: Values: [5, 2, 4, 0, 7] (indices [0, 0, 0, 0, 0) - sum 18
: Values: [5, 2, 4, 0, 2] (indices [0, 0, 0, 0, 1) - sum 13
: Values: [5, 2, 4, 1, 2] (indices [0, 0, 0, 1, 1) - sum 14
: Values: [5, 2, 4, 1, 4] (indices [0, 0, 0, 1, 2) - sum 16
: Values: [5, 2, 1, 1, 2] (indices [0, 0, 1, 1, 1) - sum 11
: Values: [5, 2, 1, 1, 4] (indices [0, 0, 1, 1, 2) - sum 13
: Values: [5, 2, 1, 2, 4] (indices [0, 0, 1, 2, 2) - sum 14
: Values: [5, 2, 1, 2, 1] (indices [0, 0, 1, 2, 3) - sum 11
: Values: [5, 3, 1, 1, 2] (indices [0, 1, 1, 1, 1) - sum 12
: Values: [5, 3, 1, 1, 4] (indices [0, 1, 1, 1, 2) - sum 14
: Values: [5, 3, 1, 2, 4] (indices [0, 1, 1, 2, 2) - sum 15
: Values: [5, 3, 1, 2, 1] (indices [0, 1, 1, 2, 3) - sum 12
: Values: [5, 3, 5, 2, 4] (indices [0, 1, 2, 2, 2) - sum 19
: Values: [5, 3, 5, 2, 1] (indices [0, 1, 2, 2, 3) - sum 16
: Values: [5, 3, 5, 3, 1] (indices [0, 1, 2, 3, 3) - sum 17
: Values: [5, 3, 5, 3, 9] (indices [0, 1, 2, 3, 4) - sum 25
11
We have the current node index (the first argument to the procedure), which we need to derive the child indices, so the actual path is not really needed (except for the verbose output), so we could drop collecting it.
Challenge #152.2: Rectangle Area
Write a script to find the total area covered by the two rectangles.
Example 1:
Input: Rectangle 1 => (-1,0), (2,2)
Rectangle 2 => (0,-1), (4,4)
Output: 22
Input: Rectangle 1 => (-3,-1), (1,3)
Rectangle 2 => (-1,-3), (2,2)
Output: 25
The problem is that the two rectangles may overlap, as shown here for the first example (with the first rectangle in blue, and the second one in red):
The Big Argument
Let us look at the arguments, before we do the actual program. We can either use a a single argument string (and split it up later), or individual arguments:
$ ./rectangle-area '1 2 3 4 5 6 7 8'
$ ./rectangle-area 1 2 3 4 5 6 7 8
Both approaches will work. But shat happens when the first value is negative, as is the case with both examples from the challenge? Here is the first one:
$ ./rectangle-area -1 0 2 2 0 -1 4 4
$ ./rectangle-area '-1 0 2 2 0 -1 4 4'
The first minus sign is interprted as the beginning of a named argument, in both cases, and the program crashes.
The solution: Avoid a minus sign as the first character. The easiest way of doing that
is simply to add a space before it (as the words method happily will get
rid of it for us):
$ ./rectangle-area ' -1 0 2 2 0 -1 4 4'
The following program has shamelessly been copied from www.geeksforgeeks.org, as I am utterly unable to solve this on my own. The variable names are my own, though.
File: rectangle-area
#! /usr/bin/env raku
unit sub MAIN ($string, :v(:$verbose));
my ($Ax1, $Ay1, $Ax2, $Ay2, $Bx1, $By1, $Bx2, $By2)
= $string.words>>.Numeric; # [1]
my $A-area = ($Ax2 - $Ax1).abs * ($Ay2 - $Ay1).abs;
my $B-area = ($Bx2 - $Bx1).abs * ($By2 - $By1).abs;
my $x-dist = min($Ax2, $Bx2) - max($Ax1, $Bx1);
my $y-dist = min($Ay2, $By2) - max($Ay1, $By1);
my $i-area = ($x-dist > 0 && $y-dist > 0) ?? $x-dist * $y-dist !! 0;
if $verbose
{
say ": First rectangle has area: $A-area";
say ": Second rectangle has area: $B-area";
say ": Intersection has area: $i-area";
}
say $A-area + $B-area - $i-area;
[1] Ensure that the arguments are numeric. This will cause a run time error if they are not, which is fine.
Running it:
$ ./rectangle-area '-1 0 2 2 0 -1 4 4'
Usage:
./rectangle-area [-v|--verbose[=Any]] <string>
$ ./rectangle-area ' -1 0 2 2 0 -1 4 4'
22
$ ./rectangle-area ' -3 -1 1 3 -1 -3 2 2'
25
This also works:
$ ./rectangle-area -- '-1 0 2 2 0 -1 4 4'
22
With verbose mode:
$ ./rectangle-area -v ' -1 0 2 2 0 -1 4 4'
: First rectangle has area: 6
: Second rectangle has area: 20
: Intersection has area: 4
22
$ ./rectangle-area -v ' -3 -1 1 3 -1 -3 2 2'
: First rectangle has area: 16
: Second rectangle has area: 15
: Intersection has area: 6
25
Looking good.
And that's it.