Perl Weekly Challenge: Week 152
Challenge 1:
Triangle Sum Path
You are given a triangle array.
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
Example 2
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
This weeks problems were pretty easy. This one for example we can do as a Raku one-liner.
We input the triangle array in the command-line arguments like this for example 1:
"1" "5,3" "2,3,4" "7,1,0,2" "6,4,5,2,8" Then using .map(), we split each argument (i.e. row)
into elements with .split() and find the smallest one with .min(). Then we total the minimum
values for each row with .sum() and print the result with .say().
@*ARGS.map({ $_.split(q{,}).min }).sum.say
For the Perl version, we must supply our own versions of min() and sum() but then the
rest of the code is one-line.
say sum (map { min(split /,/, $_) } @ARGV);
Challenge 2:
Rectangle Area
You are given coordinates bottom-left and top-right corner of two rectangles in a 2D plane.
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
Example 2
Input: Rectangle 1 => (-3,-1), (1,3)
Rectangle 2 => (-1,-3), (2,2)
Output: 25
This one requires more code but conceptually it is quite simple.
Each rectangle is brought in to the script in comma-delimited command-line arguments like
this for example 1: "-1,0,2,2" "0,-1,4,4
So the first thing we need to do is reconstitute them.
my ($x1a, $y1a, $x2a, $y2a) = $rect1.split(',');
my ($x1b, $y1b, $x2b, $y2b) = $rect1.split(',');
The area of a rectangle is easy to calculate with a formula from high school geometry. my $area1 = ($x2a - $x1a) * ($y2a - $y1a); my $area2 = ($x2b - $x1b) * ($y2b - $y1b);
And that ought to be enough to get the answer but there is one complication; the two rectangles might overlap and in that case we will be counting the area of the overlapped part twice.
This is how we calculate the area of the overlap if it exists.
my $overlapx1 = $x1a max $x1b;
my $overlapy1 = $y1a max $y1b;
my $overlapx2 = $x2a min $x2b;
my $overlapy2 = $y2a min $y2b;
my $overlapArea = 0;
if $overlapx2 > $overlapx1 && $overlapy2 > $overlapy1 {
$overlapArea =
($overlapx2 - $overlapx1) * ($overlapy2 - $overlapy1);
}
Now the answer is the area of the two rectangles minus the overlap.
say $area1 + $area2 - $overlapArea;
The Perl version is exactly the same as Raku.
my ($x1a, $y1a, $x2a, $y2a) = split /,/, $rect1;
my ($x1b, $y1b, $x2b, $y2b) = split /,/, $rect2;
my $area1 = ($x2a - $x1a) * ($y2a - $y1a);
my $area2 = ($x2b - $x1b) * ($y2b - $y1b);
my $overlapx1 = max($x1a, $x1b);
my $overlapy1 = max($y1a, $y1b);
my $overlapx2 = min($x2a, $x2b);
my $overlapy2 = min($y2a, $y2b);
my $overlapArea = 0;
if ($overlapx2 > $overlapx1 && $overlapy2 > $overlapy1) {
$overlapArea =
($overlapx2 - $overlapx1) * ($overlapy2 - $overlapy1);
}
say $area1 + $area2 - $overlapArea;