by Arne Sommer

# Coins & Rectangles with Raku

[89] Published 27. August 2020.

This is my response to the Perl Weekly Challenge #075.

## Challenge #075.1: Coins Sum

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 \$SC using the coins from the set @C.

Example
Input:
@C = (1, 2, 4)
\$S = 6

Output: 6
There are 6 possible ways to make sum 6.
a) (1, 1, 1, 1, 1, 1)
b) (1, 1, 1, 1, 2)
c) (1, 1, 2, 2)
d) (1, 1, 4)
e) (2, 2, 2)
f) (2, 4)

This is easy-ish:

File: coins-sum
#! /usr/bin/env raku

subset NonNegativeInt of Int where * >= 0;       # [1]

unit sub MAIN (NonNegativeInt \$S where \$S >= 1,  # [2]
*@C where @C.elems >= 1     &&    # [2a]
all(@C) ~~ NonNegativeInt &&    # [2b]
all(@C) <= \$S,                  # [2c]
:v(:\$verbose));

my @source;                                      # [3]

for @C -> \$coin                                  # [4]
{
@source.push: \$coin for ^(\$S div \$coin);       # [5]
}

say ": " ~ @source.join(", ") if \$verbose;

.join(", ").say                                  # [6]
for @source.combinations(1..\$S).grep({ .sum == \$S }).unique(:with(&[eqv]));

[1] The denominations must be positive, and I have chosen to support integers only (as the given example uses integers only).

[2] The sum (\$S) must be a positive value. The list of denominations must have at least one element [2a], all of them must be positive integers [2b], and the program will abort if all the denominations are higher than the sum [2c].

[3] The array to pick values from.

[4] For each denomination,

[5] • Add the coin as many times as we can use it (by itself) without exceeding the sum. This gives us a long list (which we can use Verbose mode to see), but the answer is a (one or more) sublists. (And div is integer division.)

[6] Using combinations to get all the combinations of the list with 1 to \$S elemens. Then we use grep to get rid of lists with the wrong sum, and finally we use unique to get rid of duplicates. (The duplicate lists are caused by the duplicate values in @source.)

Running it:

\$ ./coins-sum -v 4 1
: 1, 1, 1, 1
1, 1, 1, 1

\$ ./coins-sum -v 4 1 2
: 1, 1, 1, 1, 2, 2
2, 2
1, 1, 2
1, 1, 1, 1

\$ ./coins-sum -v 4 1 2 3
: 1, 1, 1, 1, 2, 2, 3
1, 3
2, 2
1, 1, 2
1, 1, 1, 1

\$ ./coins-sum -v 4 1 2 3 4
: 1, 1, 1, 1, 2, 2, 3, 4
4
1, 3
2, 2
1, 1, 2
1, 1, 1, 1

\$ ./coins-sum -v 4 1 2 3 4 5
: 1, 1, 1, 1, 2, 2, 3, 4
4
1, 3
2, 2
1, 1, 2
1, 1, 1, 1

We should add an unique clause, early on, as this works with a lot of overhead:

\$ ./coins-sum -v 4 1 1 1
: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1

The result is correct, as the unique call removes duplicates. Of which there are many. But we can get rid of them earlier to speed things up.

File: coins-sum2
#! /usr/bin/env raku

subset NonNegativeInt of Int where * >= 0;

unit sub MAIN (NonNegativeInt \$S where \$S >= 1,
*@C where @C.elems >= 1     &&
all(@C) ~~ NonNegativeInt &&
all(@C) <= \$S,
:v(:\$verbose));

my @coins = @C.unique;                      # [1]
my @source;

for @coins -> \$coin
{
@source.append: \$coin xx (\$S div \$coin);  # [2]
}

if \$verbose                                 # [3]
{
say ": Sum: \$S";
say ": Coins: " ~ @C.join(", ");
say ": Unique coins: " ~ @coins.join(", ");
say ": Source: " ~ @source.join(", ");
}

.join(", ").say
for @source.combinations(1..\$S).grep({ .sum == \$S }).unique(:with(&[eqv]));

[1] Get rid of duplicates in the list of denominations, if any.

[2] Replacing the inner loop with the list repetition operator xx. Note that we must use append so that the list is added to the list as single elements, and not as a list. push worked in the original program, as we gave it one value at a time.

[3] A more verbose Verbose mode.

\$ ./coins-sum -v 4 1 1 1
: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1
\$ ./coins-sum2 -v 4 1 1 1
: Sum: 4
: Coins: 1, 1, 1
: Unique coins: 1
: Source: 1, 1, 1, 1
1, 1, 1, 1

Looking good.

## Challenge #075.2: Largest Rectangle Histogram

You are given an array of positive numbers @A.

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

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

Example 1
Input: @A = (2, 1, 4, 5, 3, 7)
7           #
6           #
5       #   #
4     # #   #
3     # # # #
2 #   # # # #
1 # # # # # #
_ _ _ _ _ _ _
2 1 4 5 3 7
Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns (4, 5, 3 and 7).
Output: 12

Example 2
Input: @A = (3, 2, 3, 5, 7, 5)
7         #
6         #
5       # # #
4       # # #
3 #   # # # #
2 # # # # # #
1 # # # # # #
_ _ _ _ _ _ _
3 2 3 5 7 5
Looking at the above histogram, the largest rectangle (3 x 5) is formed by columns (5, 7 and 5).
Output: 15

This is also easy-ish. We construct all the possible rectangles, calculate the size, and the answer is the largest value. We do this by iterating over the start value, then the stop value, calclulating the height (with max on the sublist). The size is the width multiplied with this height.

Here it is, without furter explanation.

File: lrh
#! /usr/bin/env raku

subset NonNegativeInt of Int where * >= 0;

unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ NonNegativeInt,
:v(:\$verbose));

my \$end = @A.end;

my @solutions;
my \$max = -1;

for 0 .. \$end -> \$from
{
for \$from .. \$end -> \$to
{
my \$height = min(@A[\$from .. \$to]);
my \$width  = \$to - \$from +1;
my \$size   = \$height * \$width;

say ": \@A[\$from .. \$to] -> ({ @A[\$from .. \$to] }) w:\$width h:\$height s:\$size"
if \$verbose;

if \$size >= \$max
{
if \$size > \$max
{
@solutions = ();
\$max = \$size;
say ": New max: \$max" if \$verbose;
}
@solutions.push: @A[\$from .. \$to].join(", ");
}
}
}

if \$verbose
{
say ": columns: \$_" for @solutions;
}

say \$max;

Running it with the examples given in the challenge:

./lrh 2 1 4 5 3 7
12

\$ ./lrh 3 2 3 5 7 5
15

Looking good, but an explanation would make it more convincing. Verbose mode to the rescue. The «@A[0 .. 0] -> (2) w:1 h:2 s:2» line means a sublist of @A, from the first index to the second one (both included) -> ( list of values this gives; the sublist ), w:width of sublist, h:height of sublist, and s:size of sublist.

\$ ./lrh -v 2 1 4 5 3 7
: @A[0 .. 0] -> (2) w:1 h:2 s:2
: New max: 2
: @A[0 .. 1] -> (2 1) w:2 h:1 s:2
: @A[0 .. 2] -> (2 1 4) w:3 h:1 s:3
: New max: 3
: @A[0 .. 3] -> (2 1 4 5) w:4 h:1 s:4
: New max: 4
: @A[0 .. 4] -> (2 1 4 5 3) w:5 h:1 s:5
: New max: 5
: @A[0 .. 5] -> (2 1 4 5 3 7) w:6 h:1 s:6
: New max: 6
: @A[1 .. 1] -> (1) w:1 h:1 s:1
: @A[1 .. 2] -> (1 4) w:2 h:1 s:2
: @A[1 .. 3] -> (1 4 5) w:3 h:1 s:3
: @A[1 .. 4] -> (1 4 5 3) w:4 h:1 s:4
: @A[1 .. 5] -> (1 4 5 3 7) w:5 h:1 s:5
: @A[2 .. 2] -> (4) w:1 h:4 s:4
: @A[2 .. 3] -> (4 5) w:2 h:4 s:8
: New max: 8
: @A[2 .. 4] -> (4 5 3) w:3 h:3 s:9
: New max: 9
: @A[2 .. 5] -> (4 5 3 7) w:4 h:3 s:12
: New max: 12
: @A[3 .. 3] -> (5) w:1 h:5 s:5
: @A[3 .. 4] -> (5 3) w:2 h:3 s:6
: @A[3 .. 5] -> (5 3 7) w:3 h:3 s:9
: @A[4 .. 4] -> (3) w:1 h:3 s:3
: @A[4 .. 5] -> (3 7) w:2 h:3 s:6
: @A[5 .. 5] -> (7) w:1 h:7 s:7
: columns: 4, 5, 3, 7
12

\$ ./lrh -v 3 2 3 5 7 5
: @A[0 .. 0] -> (3) w:1 h:3 s:3
: New max: 3
: @A[0 .. 1] -> (3 2) w:2 h:2 s:4
: New max: 4
: @A[0 .. 2] -> (3 2 3) w:3 h:2 s:6
: New max: 6
: @A[0 .. 3] -> (3 2 3 5) w:4 h:2 s:8
: New max: 8
: @A[0 .. 4] -> (3 2 3 5 7) w:5 h:2 s:10
: New max: 10
: @A[0 .. 5] -> (3 2 3 5 7 5) w:6 h:2 s:12
: New max: 12
: @A[1 .. 1] -> (2) w:1 h:2 s:2
: @A[1 .. 2] -> (2 3) w:2 h:2 s:4
: @A[1 .. 3] -> (2 3 5) w:3 h:2 s:6
: @A[1 .. 4] -> (2 3 5 7) w:4 h:2 s:8
: @A[1 .. 5] -> (2 3 5 7 5) w:5 h:2 s:10
: @A[2 .. 2] -> (3) w:1 h:3 s:3
: @A[2 .. 3] -> (3 5) w:2 h:3 s:6
: @A[2 .. 4] -> (3 5 7) w:3 h:3 s:9
: @A[2 .. 5] -> (3 5 7 5) w:4 h:3 s:12
: @A[3 .. 3] -> (5) w:1 h:5 s:5
: @A[3 .. 4] -> (5 7) w:2 h:5 s:10
: @A[3 .. 5] -> (5 7 5) w:3 h:5 s:15
: New max: 15
: @A[4 .. 4] -> (7) w:1 h:7 s:7
: @A[4 .. 5] -> (7 5) w:2 h:5 s:10
: @A[5 .. 5] -> (5) w:1 h:5 s:5
: columns: 5, 7, 5
: columns: 5, 7, 5
15

Another one, while we are at it:

\$ ./lrh 1 2 3 4 5
9

\$ ./lrh -v 1 2 3 4 5
: @A[0 .. 0] -> (1) w:1 h:1 s:1
: New max: 1
: @A[0 .. 1] -> (1 2) w:2 h:1 s:2
: New max: 2
: @A[0 .. 2] -> (1 2 3) w:3 h:1 s:3
: New max: 3
: @A[0 .. 3] -> (1 2 3 4) w:4 h:1 s:4
: New max: 4
: @A[0 .. 4] -> (1 2 3 4 5) w:5 h:1 s:5
: New max: 5
: @A[1 .. 1] -> (2) w:1 h:2 s:2
: @A[1 .. 2] -> (2 3) w:2 h:2 s:4
: @A[1 .. 3] -> (2 3 4) w:3 h:2 s:6
: New max: 6
: @A[1 .. 4] -> (2 3 4 5) w:4 h:2 s:8
: New max: 8
: @A[2 .. 2] -> (3) w:1 h:3 s:3
: @A[2 .. 3] -> (3 4) w:2 h:3 s:6
: @A[2 .. 4] -> (3 4 5) w:3 h:3 s:9
: New max: 9
: @A[3 .. 3] -> (4) w:1 h:4 s:4
: @A[3 .. 4] -> (4 5) w:2 h:4 s:8
: @A[4 .. 4] -> (5) w:1 h:5 s:5
: columns: 3, 4, 5
9

### The Bonus Histogram

File: lrh-histogram
#! /usr/bin/env raku

subset NonNegativeInt of Int where * >= 0;

unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ NonNegativeInt,
:v(:\$verbose), :h(:\$histogram));  # [1]

my \$end = @A.end;

my @solutions;
my \$max = -1;

for 0 .. \$end -> \$from
{
for \$from .. \$end -> \$to
{
my \$height = min(@A[\$from .. \$to]);
my \$width  = \$to - \$from +1;
my \$size   = \$height * \$width;

say ": \@A[\$from .. \$to] -> ({ @A[\$from .. \$to] }) w:\$width h:\$height s:\$size"
if \$verbose;

if \$size >= \$max
{
if \$size > \$max
{
@solutions = ();
\$max = \$size;
say ": New max: \$max" if \$verbose;
}
@solutions.push: @A[\$from .. \$to].join(", ");
}
}
}

if \$verbose
{
say ": columns: \$_" for @solutions;
}

say \$max;

if \$histogram  # [1]
{
say '';
my \$height = @A.max;
my \$width  = \$height.chars;

for \$height ... 1 -> \$row
{
print "{ \$row.fmt("%{\$width}d") } ";
for 0 .. \$end -> \$index
{
print @A[\$index] >= \$row
?? ('#' x \$width ~ " ")
!! ' ' x \$width +1;
}
say '';
}

say "-" x 6 + \$width * (\$end +2);

print ' ' x \$width +1;

for 0 .. \$end -> \$index
{
print @A[\$index].fmt("%{\$width}d") ~ " ";
}
say '';
}

[1] Enable histogram mode with the «-h» or «--histogram» command line argument(s).

The rest of the code is a pretty printer. Note the usage of the maximum length (number of digits) of the numbers (in fmt and with the string repetition operator x) to get nicely tabulated values.

Running it:

\$ ./lrh-histogram -h 2 1 4 5 3 7
12

7           #
6           #
5       #   #
4     # #   #
3     # # # #
2 #   # # # #
1 # # # # # #
-------------
2 1 4 5 3 7

\$ ./lrh-histogram -h 3 2 3 5 7 5
15

7         #
6         #
5       # # #
4       # # #
3 #   # # # #
2 # # # # # #
1 # # # # # #
-------------
3 2 3 5 7 5

It works with numbers with more than one digit:

\$ ./lrh-histogram -h 1 2 3 4 5 11
12

11                ##
10                ##
9                ##
8                ##
7                ##
6                ##
5             ## ##
4          ## ## ##
3       ## ## ## ##
2    ## ## ## ## ##
1 ## ## ## ## ## ##
--------------------
1  2  3  4  5 11

\$ ./lrh-histogram -h 1 2 3 4 11 111
111

111                     ###
110                     ###
109                     ###
108                     ###
....
14                     ###
13                     ###
12                     ###
11                 ### ###
10                 ### ###
9                 ### ###
8                 ### ###
7                 ### ###
6                 ### ###
5                 ### ###
4             ### ### ###
3         ### ### ### ###
2     ### ### ### ### ###
1 ### ### ### ### ### ###
---------------------------
1   2   3   4  11 111

And it will show all the answers, if there are more than one:

\$ ./lrh-histogram -h -v 3 4 4 4
: @A[0 .. 0] -> (3) w:1 h:3 s:3
: New max: 3
: @A[0 .. 1] -> (3 4) w:2 h:3 s:6
: New max: 6
: @A[0 .. 2] -> (3 4 4) w:3 h:3 s:9
: New max: 9
: @A[0 .. 3] -> (3 4 4 4) w:4 h:3 s:12
: New max: 12
: @A[1 .. 1] -> (4) w:1 h:4 s:4
: @A[1 .. 2] -> (4 4) w:2 h:4 s:8
: @A[1 .. 3] -> (4 4 4) w:3 h:4 s:12
: @A[2 .. 2] -> (4) w:1 h:4 s:4
: @A[2 .. 3] -> (4 4) w:2 h:4 s:8
: @A[3 .. 3] -> (4) w:1 h:4 s:4
: columns: 3, 4, 4, 4
: columns: 4, 4, 4
12

4   # # #
3 # # # #
2 # # # #
1 # # # #
-----------
3 4 4 4

\$ ./lrh-histogram -h -v 3 4 4 4 2 2
: @A[0 .. 0] -> (3) w:1 h:3 s:3
: New max: 3
: @A[0 .. 1] -> (3 4) w:2 h:3 s:6
: New max: 6
: @A[0 .. 2] -> (3 4 4) w:3 h:3 s:9
: New max: 9
: @A[0 .. 3] -> (3 4 4 4) w:4 h:3 s:12
: New max: 12
: @A[0 .. 4] -> (3 4 4 4 2) w:5 h:2 s:10
: @A[0 .. 5] -> (3 4 4 4 2 2) w:6 h:2 s:12
: @A[1 .. 1] -> (4) w:1 h:4 s:4
: @A[1 .. 2] -> (4 4) w:2 h:4 s:8
: @A[1 .. 3] -> (4 4 4) w:3 h:4 s:12
: @A[1 .. 4] -> (4 4 4 2) w:4 h:2 s:8
: @A[1 .. 5] -> (4 4 4 2 2) w:5 h:2 s:10
: @A[2 .. 2] -> (4) w:1 h:4 s:4
: @A[2 .. 3] -> (4 4) w:2 h:4 s:8
: @A[2 .. 4] -> (4 4 2) w:3 h:2 s:6
: @A[2 .. 5] -> (4 4 2 2) w:4 h:2 s:8
: @A[3 .. 3] -> (4) w:1 h:4 s:4
: @A[3 .. 4] -> (4 2) w:2 h:2 s:4
: @A[3 .. 5] -> (4 2 2) w:3 h:2 s:6
: @A[4 .. 4] -> (2) w:1 h:2 s:2
: @A[4 .. 5] -> (2 2) w:2 h:2 s:4
: @A[5 .. 5] -> (2) w:1 h:2 s:2
: columns: 3, 4, 4, 4
: columns: 3, 4, 4, 4, 2, 2
: columns: 4, 4, 4
12

4   # # #
3 # # # #
2 # # # # # #
1 # # # # # #
-------------
3 4 4 4 2 2

And that's it.