This is my response to the Perl Weekly Challenge #075.
@C, assuming you have infinite amount of each
coin in the set.
$SC using the coins from
the set @C.
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.)
See
docs.raku.org/routine/div for
more information about div.
See
docs.raku.org/routine/combinations for
more information about combinations.
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.
#! /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.
See
docs.raku.org/routine/xx for
more information about the list repetition operator xx.
See
docs.raku.org/routine/push for
more information about push.
See
docs.raku.org/routine/append for
more information about append.
$ ./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.
@A.
7 #
6 #
5 # #
4 # # #
3 # # # #
2 # # # # #
1 # # # # # #
_ _ _ _ _ _ _
2 1 4 5 3 7
7 #
6 #
5 # # #
4 # # #
3 # # # # #
2 # # # # # #
1 # # # # # #
_ _ _ _ _ _ _
3 2 3 5 7 5
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
#! /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.
See
docs.raku.org/routine/x for
more information about the string repetition operator x.
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.