Rafraîchissoir

By Shahed Nooshmand

The Weekly Challenge: week 75

Challenge, indeed.

Task #1

You are given a set of coins @C, assuming you have infinite amount of each coin in the set.

Write a script to find how many ways you make sum $S using the coins from the set @C.

This is a popular counting problem and has a recursive solution:

#!/usr/bin/env raku

my $S = 6;
my @C = 1, 2, 4;
say (@C Zxx @$_).map: |* for change $S, @C;

sub change($total, @coins is copy) {
	my $coin = @coins.shift;
	my $max-count = $total ÷ $coin;

	return $total %% $coin ?? $max-count !! [] if @coins == 0;

	my @solutions = [];
	for 0..$max-count -> $count {
		@solutions.push: [$count, |$_] for change $total − $count × $coin, @coins
	}
	return @solutions;
}

The change subroutine tries all probable counts associated with the first coin, and in each iteration calls itself with the remaining coins and the remaining total. The recursion goes on until only one coin remains, in which case that coin either has one solution for the given total, or it doesn’t have a solution at all.

The solutions are actually lists of the number of each coin, in order. So if one solution is (2 0 1), it means there are two of the first coin and one of the third coin. Since we want to show each and every coin, for each solution, we multiply each kind of coin by its count to show it in volume.

Running the script we get:

(2 4)
(2 2 2)
(1 1 4)
(1 1 2 2)
(1 1 1 1 2)
(1 1 1 1 1 1)

Which is correct.

Task #2

You are given an array of positive numbers @A.

Write a script to find the largest rectangle histogram created by the given array.

BONUS: Try to print the histogram as shown in the example, if possible.

I won’t paste the example here, because this already is very long:

#!/usr/bin/env raku

my @A = 2, 1, 4, 5, 3, 7;
my $max-area = 0;
my @rect-indices;
my $rect-height;

exit if @A == 0;

for 1..@A -> $length {
	my @indices = |(0..(@A − $length) Z.. ($length − 1)..^@A).max: { @A[|$_].min }
	my $height = @A[@indices].min;
	my $area = $length × $height;
	if $area > $max-area {
		$max-area = $area;
		$rect-height = $height;
		@rect-indices = @indices;
	}
}

print “$max-area\n\n”;

## Bonus ##
for @A.max...1 -> $height {
	print $height;
	for ^@A -> $index {
		print “\t”;
		my $number = @A[$index];
		if $number ≥ $height {
			## Extra bonus ##
			if $index ∈ @rect-indices and $height ≤ $rect-height {
				print “●”
			} else {
				print “○”
			}
		}
	}
	print “\n”;
}
print “\t” ~ @A.join(“\t”);

Let’s break it down.

We check @A == 1 in case some wiseass sets @A to an empty array. Then, we change the length — or width, depending on your point of view — of the rectangle we’re trying to make. For each length, we want that many consecutive elements of @A, such that the smallest value among these elements is still large enough to make a rectangle of the given length with maximum area.

After we’re done checking each length, we have $max-area which is the answer, @rect-indices which is the list of consecutive indices chosen from @A and $rect-height which is the height of the rectangle (obviously).

For the bonus, we just have to go through all height from the largest element in @A down to 1, and print something if we must. I took the liberty of giving myself Extra Bonus for using black and white circles to make the rectangle stand out.

In the end we print the numbers in @A and the histogram is complete. Here’s what the script prints:

12

7						○
6						○
5				○		○
4			○	○		○
3			●	●	●	●
2	○		●	●	●	●
1	○	○	●	●	●	●
	2	1	4	5	3	7

That’s it.