by Arne Sommer

# Scored Product with Raku

[238] Published 28. May 2023.

This is my response to The Weekly Challenge #218.

## Challenge #218.1: Maximum Product

You are given a list of 3 or more integers.

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 ``` Example 2: ```Input: @list = (4, 1, 3, 2) Output: 24 2 x 3 x 4 => 24 ``` Example 3: ```Input: @list = (-1, 0, 1, 3, 1) Output: 3 1 x 1 x 3 => 3 ``` Example 4: ```Input: @list = (-8, 2, -9, 0, -4, 3) Output: 216 -9 × -8 × 3 => 216 ```
File: maximum-product ```#! /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`:

File: maximum-product-reduce ```#! /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

You are given a m x n binary matrix i.e. having only `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 ``` Example 2: ```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.