Scored Product with Raku
[238] Published 28. May 2023.This is my response to The Weekly Challenge #218.
Challenge #218.1: Maximum Product
Write a script to find the 3 integers whose product is the maximum and return it.
Example 1:
Input: @list = (3, 1, 2)
Output: 6
1 x 2 x 3 => 6
Input: @list = (4, 1, 3, 2)
Output: 24
2 x 3 x 4 => 24
Input: @list = (-1, 0, 1, 3, 1)
Output: 3
1 x 1 x 3 => 3
Input: @list = (-8, 2, -9, 0, -4, 3)
Output: 216
-9 × -8 × 3 => 216
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 3 && all(@list) ~~ Int, # [1]
:v(:$verbose));
my $highest = - Inf; # [2]
my @highest; # [3]
for @list.combinations(3) -> @candidate # [4]
{
my $product = [*] @candidate; # [5]
print ":Candidate { @candidate.join(",") } with product: $product"
if $verbose;
if $product > $highest # [6]
{
$highest = $product; # [6a]
@highest = @candidate; # [6b]
print " - highest" if $verbose;
}
say "";
}
say ":Highest triple { @highest.join(",") }" if $verbose;
say $highest; # [7]
[1] At least three integers.
[2] We are looking for the currently highest value. Start with the absolutely lowest one.
[3] The combination that gave us the highest value will end up here, for verbose mode usage.
[4] Iterate over all three value combinations.
[5] Multiply the three values with the
Reduction Metaoperator [] using multiplication (e.g. *).
See
docs.raku.org/language/operators#Reduction_metaoperators for more
information about the Reduction Metaoperator [].
[6] Have we found a new highest value? If so, use it [6a] and note the combination [6b].
[7] Print the result.
Running it:
$ ./maximum-product 3 1 2
6
$ ./maximum-product 4 1 3 2
24
$ ./maximum-product -v -1 0 1 3 1
Usage:
./maximum-product [-v|--verbose[=Any]] [<list> ...]
The «-1» value is taken as a command line option, and one that the program does not recognise. We can either move it after e.g. «0», or mark the end of command line parsing with with the magical «--»:
$ ./maximum-product 0 -1 1 3 1
3
$ ./maximum-product -- -1 0 1 3 1
3
Then the final one.
$ ./maximum-product 2 -8 -9 0 -4 3
216
Looking good.
With verbose mode:
$ ./maximum-product -v 3 1 2
:Candidate 3,1,2 with product: 6 - highest
:Highest triple 3,1,2
6
$ ./maximum-product -v 4 1 3 2
:Candidate 4,1,3 with product: 12 - highest
:Candidate 4,1,2 with product: 8
:Candidate 4,3,2 with product: 24 - highest
:Candidate 1,3,2 with product: 6
:Highest triple 4,3,2
24
$ ./maximum-product -v -- -1 0 1 3 1
:Candidate -1,0,1 with product: 0 - highest
:Candidate -1,0,3 with product: 0
:Candidate -1,0,1 with product: 0
:Candidate -1,1,3 with product: -3
:Candidate -1,1,1 with product: -1
:Candidate -1,3,1 with product: -3
:Candidate 0,1,3 with product: 0
:Candidate 0,1,1 with product: 0
:Candidate 0,3,1 with product: 0
:Candidate 1,3,1 with product: 3 - highest
:Highest triple 1,3,1
3
$ ./maximum-product -v -- -8 2 -9 0 -4 3
:Candidate -8,2,-9 with product: 144 - highest
:Candidate -8,2,0 with product: 0
:Candidate -8,2,-4 with product: 64
:Candidate -8,2,3 with product: -48
:Candidate -8,-9,0 with product: 0
:Candidate -8,-9,-4 with product: -288
:Candidate -8,-9,3 with product: 216 - highest
:Candidate -8,0,-4 with product: 0
:Candidate -8,0,3 with product: 0
:Candidate -8,-4,3 with product: 96
:Candidate 2,-9,0 with product: 0
:Candidate 2,-9,-4 with product: 72
:Candidate 2,-9,3 with product: -54
:Candidate 2,0,-4 with product: 0
:Candidate 2,0,3 with product: 0
:Candidate 2,-4,3 with product: -24
:Candidate -9,0,-4 with product: 0
:Candidate -9,0,3 with product: 0
:Candidate -9,-4,3 with product: 108
:Candidate 0,-4,3 with product: 0
:Highest triple -8,-9,3
216
It is possible to wrap it up as a one liner, here with the error handling in place giving a «three liner» (if that is a thing):
File: maximum-product-map
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 3 && all(@list) ~~ Int);
say @list.combinations(3).map({ [*] @_ }).max; # [1]
[1] Using map to reduce the combinations to a single value each.
See
docs.raku.org/routine/map
for more information about map.
Running it gives the expected result:
$ ./maximum-product-map 3 1 2
6
$ ./maximum-product-map 4 1 3 2
24
$ ./maximum-product-map -- -1 0 1 3 1
3
$ ./maximum-product-map -- -8 2 -9 0 -4 3
216
Reduce you say? Does not Raku have a reduce
method?
Here is a version using reduce instead of map:
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 3 && all(@list) ~~ Int);
say @list.combinations(3)>>.reduce(&infix:<*>).max; # [1]
[1] We must apply reduce on all the combinations, thus the
>>. invocation. Note the way to specify inbuilt operators,
here multiplication.
See
docs.raku.org/routine/reduce for
more information about reduce.
Running this version gives the same result as before:
$ ./maximum-product-reduce 3 1 2
6
$ ./maximum-product-reduce 4 1 3 2
24
$ ./maximum-product-reduce -- -1 0 1 3 1
3
$ ./maximum-product-reduce -- -8 2 -9 0 -4 3
216
Challenge #218.2: Matrix Score
1 and 0.
You are allowed to make as many moves as you want to get the highest score.
A move can be either toggling each value in a row or column.
To get the score, convert the each row binary to dec and return the sum.
Example 1:
Input: @matrix = [ [0,0,1,1],
[1,0,1,0],
[1,1,0,0], ]
Output: 39
Move #1: convert row #1 => 1100
[ [1,1,0,0],
[1,0,1,0],
[1,1,0,0], ]
Move #2: convert col #3 => 101
[ [1,1,1,0],
[1,0,0,0],
[1,1,1,0], ]
Move #3: convert col #4 => 111
[ [1,1,1,1],
[1,0,0,1],
[1,1,1,1], ]
Score: 0b1111 + 0b1001 + 0b1111 => 15 + 9 + 15 => 39
Input: @matrix = [ [0] ]
Output: 1
We can distill two rules from this:
- All the rows must start with "1" (to give the highest possible value)
- All the columns should have the same or more number of "1"s than "0"s
Explaining the rules
The first rule follows by the fact that the (decimal) value of the first column is higher than the sum op all the following columns. A row with eg «0111» has a decimal value of 7, whereas «1000» has a decimal value of 8.
It does not matter on which row we have the «1», as they have the same decimal value regardlessly. But the number of them does matter, so we should flip the column if that increases the number of «1»s.
Let us apply them, in that order.
File: matrix-score
#! /usr/bin/env raku
unit sub MAIN (Str $matrix = "0 0 0 1 | 1 0 1 0 | 1 1 0 0", # [1]
:v(:$verbose));
my @matrix = $matrix.split("|")>>.words>>.Array; # [2]
my @rows = @matrix>>.elems; # [3]
die "Must have at least 1 row" unless @rows.elems >= 1; # [4]
die "The rows must have the same size" unless [==] @rows; # [4a]
die "Must contain 0 and 1 only" unless all(@matrix[*;*]) eq any(0,1); # [4b]
my $cols = @matrix[0].elems; # [5]
say ": Matrix: { @matrix.raku } " if $verbose;
say ": - Size: rows:$rows cols:$cols" if $verbose;
for ^$rows -> $row-id # [6]
{
print ": - row $row-id " if $verbose;
if @matrix[$row-id][0] == 0 # [6a]
{
say " - swapping" if $verbose;
@matrix.&flip-row($row-id); # [6b]
say ": Matrix: { @matrix.raku } " if $verbose;
}
else
{
say " - ok" if $verbose;
}
}
for ^$cols -> $col-id # [7]
{
my @cols = (^@matrix.elems).map({ @matrix[$_][$col-id] }); # [7a]
print ": - col $col-id -> @cols[]" if $verbose;
if @cols.sum < $cols / 2 # [7b]
{
say " - swapping" if $verbose;
@matrix.&flip-col($col-id); # [7c]
say ": Matrix: { @matrix.raku } " if $verbose;
}
else
{
say " - ok" if $verbose;
}
}
say ": Final matrix: { @matrix.raku }" if $verbose;
say @matrix.map({ @$_.join.parse-base(2) }).sum; # [8]
sub flip-row(@matrix, UInt $row) # [9]
{
@(@matrix[$row]).=map({ $_ == 1 ?? 0 !! 1 } ); # [9a]
return @matrix; # [9b]
}
sub flip-col(@matrix, UInt $col) # [10]
{
(^@matrix.elems).map({ @matrix[$_][$col] = + ! + @matrix[$_][$col] }); # [10a]
return @matrix; # [10b]
}
[1] A default matrix.
[2] Unpack the matrix.
[3] The number of elements on each row.
[4] Error handling.
[5] The number of columns, taken from the first row. The rows have the same number of columns, thanks to [4a].
[6] Iterate over the row indices. If the first column on the row has a '0'
[6a], flip the row. (Note the &flip-row syntax used to call a
procedure like a method.)
[7] Iterate over the column indices. Get the values for the column, with a
fancy map instead of a traditional loop [7a]. Are the number
of "1"s in the lead (ewual to or grater than the number of '0's [7b]? If so,
swap the column [7c]
[8] Join each row (with map) into a single binary number
(join), converted to decimal (or whatever Raku uses internally)
(.parse-base(2)) and added together (sum). Print
the result.
[9] Flipping a row is easy. We use map on the row to flip
each value.
[10] Flipping a column is harder. We start with the row indices, and applies
map to flip each value. Note the + ! + sequence, that
(from the right) coerces the value to a number, then negate the boolean version
of the alue, and finally coerces it back to numeric form (as we expect "0" and
"1", and not "False" and "True").
The initial cersion to a number is critical, as non flipped values are of the string type (as shown by verbose mode, later on) - and that does not play nice with Boolification:
> say so 0 # -> False
> say so "0" # -> True
See
docs.raku.org/routine/!
for more information about the Negated Boolean context operator !.
Running it:
$ ./matrix-score
39
$ ./matrix-score "0"
1
Looking good.
With verbose mode:
$ ./matrix-score -v
: Matrix: [["0", "0", "0", "1"], ["1", "0", "1", "0"], ["1", "1", "0", "0"]]
: - Size: rows:3 cols:4
: - row 0 - swapping
: Matrix: [[1, 1, 1, 0], ["1", "0", "1", "0"], ["1", "1", "0", "0"]]
: - row 1 - ok
: - row 2 - ok
: - col 0 -> 1 1 1 - ok
: - col 1 -> 1 0 1 - ok
: - col 2 -> 1 1 0 - ok
: - col 3 -> 0 0 0 - swapping
: Matrix: [[1, 1, 1, 1], ["1", "0", "1", 1], ["1", "1", "0", 1]]
: Final matrix: [[1, 1, 1, 1], ["1", "0", "1", 1], ["1", "1", "0", 1]]
39
$ ./matrix-score -v "0"
: Matrix: [["0"],]
: - Size: rows:1 cols:1
: - row 0 - swapping
: Matrix: [[1],]
: - col 0 -> 1 - ok
: Final matrix: [[1],]
1
And that's it.