A couple of days ago I published a straightforward solution to the Task 2 of Week 75 of The Weekly Challenge.
Despite that solution perfectly works, I wasn’t satisfied with it and wanted a more Raku-ish code. Here is the next iteration of it.
my @hist = 3, 2, 3, 5, 7, 5; my $max = 0; for (^@hist).combinations(2) -> ($x, $y) { $max = max($max, min(@hist[$x .. $y]) * ($y - $x + 1)); } say "The area of a biggest rectangle is $max.";
If you looked at the output of the previous variant, you may have noticed that the ranges in the loop resemble the number combinations from Task 1 of Week 67. And that’s the hart of this solution:
(^@hist).combinations(2)
This simple line gives us what we need: all the possible sub-histograms (well, maybe except the single-column ones):
0 .. 1 0 .. 2 0 .. 3 0 .. 4 0 .. 5 1 .. 2 1 .. 3 1 .. 4 1 .. 5 2 .. 3 2 .. 4 2 .. 5 3 .. 4 3 .. 5 4 .. 5
The rest is simple. Find the area of a rectangle by multiplying the width of the window by the maximum common height of the histogram bins in it:
$max = max($max, min(@hist[$x .. $y]) * ($y - $x + 1));
Run the program to confirm it works and prints the correct result:
$ raku ch-2a.raku The area of a biggest rectangle is 15.
* * *
→ GitHub repository
→ Navigation to the Raku challenges post series
Did you know, max can also take a closure?
( 1..@A ).map({ |@A.rotor($_ => 1 – $_) }).max({ .min * .elems });
I like the way use applied `rotor` here, this is what I wanted to use originally but did not get how to.