Ma[tri]x with Raku
[237] Published 20. May 2023.This is my response to The Weekly Challenge #217.
Challenge #217.1: Sorted Matrix
n x n matrix where n >= 2.
Write a script to find
3rd smallest element in the sorted matrix.
Example 1:
Input: @matrix = ([3, 1, 2], [5, 2, 4], [0, 1, 3])
Output: 1
The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5.
The 3rd smallest of the sorted list is 1.
Input: @matrix = ([2, 1], [4, 5])
Output: 4
The sorted list of the given matrix: 1, 2, 4, 5.
The 3rd smallest of the sorted list is 4.
Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1])
Output: 0
The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3.
The 3rd smallest of the sorted list is 0.
We need a way of specifying
a matrix on the command line, and can reuse the syntax I last used in
The Same Toeplitz with Raku. E.g.
"1 2 3 | 4 5 6 | 7 8 9" which will give three rows (separated
by |) with tree values each (separated by space(s)).
#! /usr/bin/env raku
unit sub MAIN (Str $matrix = "3 1 2 | 5 2 4 | 0 1 3", :v(:$verbose)); # [1]
my @matrix = $matrix.split("|")>>.words; # [2]
my @size = @matrix>>.elems; # [3]
die "Must have at least 2 rows" unless @size.elems >= 2; # [4]
die "The rows must have the same size" unless [==] @size; # [5]
die "The number of columns and rows must be the same"
unless @size[0] == @size.elems; # [6]
my @sorted = @matrix[*;*].sort; # [7]
say ":Sorted: { @sorted.join(",") }" if $verbose;
say @sorted[2]; # [8]
[1] Note the default matrix.
[2] Split the matrix into rows (with split), and then each row
into a list of values (with words). This leaves us with an array
of sequence rows (the Seq type), which is ok in our case as we
consume them only once (in [7]). We could have added >>.Array at
the end (before the ;) to avoid that.
[3] Get the number of elements in each row.
[4] We require at least two rows.
[5] All the rows must have the same number of elements.
[6] The number of rows must be the same as the number of elements in the rows.
[7] Flatten the matrix (a two dimensional array) with the [*;*]
indexer, telling Raku that we want everything from the first and second
dimension, and then sort the values.
[8] The third lowest value resides at index 2 (as the indices start at zero).
Running it:
$ ./sorted-matrix
1
$ ./sorted-matrix "2 1 | 4 5"
4
$ ./sorted-matrix "1 0 3 | 0 0 0 | 1 2 1"
0
Looking good.
With verbose mode:
$ ./sorted-matrix -v
:Sorted: 0,1,1,2,2,3,3,4,5
1
$ ./sorted-matrix -v "2 1 | 4 5"
:Sorted: 1,2,4,5
4
$ ./sorted-matrix -v "1 0 3 | 0 0 0 | 1 2 1"
:Sorted: 0,0,0,0,1,1,1,2,3
0
Constructing a matrix just so that we can deconstruct it right away may seem a little silly, and we can make the program shorter if we skip that phase - and even shorter if we drop all the pesky error checking:
File: sorted-matrix-cheat
#! /usr/bin/env raku
unit sub MAIN (Str $matrix = "3 1 2 | 5 2 4 | 0 1 3");
say $matrix.words.grep( * !~~ /\|/ )>>.Int.sort[2]; # [1]
[1] Turn the string into an array (with words). Then use
grep to get rid of the vertical bars. Then we coerce the
values to integers (from the strings returned by words),
so that sort will sort them numerically. And finally we
print the value at index 2.
Running it gives the same result, as long as we do not try to invoke verbose mode or use junk values:
$ ./sorted-matrix-cheat
1
$ ./sorted-matrix-cheat "2 1 | 4 5"
4
$ ./sorted-matrix-cheat "1 0 3 | 0 0 0 | 1 2 1"
0
Turning this one into a one liner is easy:
say @*ARGS[0].words.grep( * !~~ /\|/ )>>.Int.sort[2];
Note that this requires the usage of my matrix command line specification format.
Challenge #217.2: Max Number
Write a script to concatenate the integers to form the highest possible value.
Example 1:
Input: @list = (1, 23)
Output: 231
Input: @list = (10, 3, 2)
Output: 3210
Input: @list = (31, 2, 4, 10)
Output: 431210
Input: @list = (5, 11, 4, 1, 2)
Output: 542111
Input: @list = (1, 10)
Output: 110
Sorting the values as strings (and not as numbers, as we did above), and then gluing them together in reverse order should get us there. Perhaps...
File: max-number-leg
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0
&& all(@list) ~~ /^<[1..9]><[0..9]>*$/); # [1]
say @list.sort({ $^b leg $^a }).join; # [2]
[1] A slurpy array with the values, all of which must be non-negative integers (starting with 1..9 and followed by zero or more of 0..9).
[2]
Sort the values with this explicit code block; $^b
is mapped to the second argument in each comparison, and $^a
to the first, thus reversing the sort order. The leg (less
equal greater) operator sorts the values as texts, just as we need.
(The <=> operator works on numbers, and cmp
(compare) is a smart version that tries to do the right thing. But the
IntStr type we get courtesy of the command line will confuse
cmp into sorting them as strings.)
See
docs.raku.org/routine/leg
for more information about the string thre-way comparator leg.
See
docs.raku.org/routine/<=>
for more information about the Numeric three-way comparator <=>.
See
docs.raku.org/routine/cmp
for more information about the Generic "smart" three-way comparator
cmp.
Running it:
$ ./max-number-leg 1 23
231
$ ./max-number-leg 10 3 2
3210
$ ./max-number-leg 31 2 4 10
431210
$ ./max-number-leg 5 11 4 1 2
542111
$ ./max-number-leg 1 10
101
The last one did not come out as expected (i.e. we should have gotten 110).
The problem is that numeric comparison is correct for all the values, except where we have two value that start out the same - but one of them has one or more zeroes added to the end.
Here is another one that fails to give the correct answer:
$ ./max-number-leg 10 100
10010
We can write a custom sorting function to sort it out (pun intended):
File: max-number-arm
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0 && all(@list) ~~ /^<[1..9]><[0..9]>*$/);
say @list.sort(&arm).join; # [1]
sub arm ($a, $b)
{
return False if $b.substr(0, $a.chars) eq $a && $b.substr($a.end +1,1) eq '0';
return True if $a.substr(0, $b.chars) eq $b && $a.substr($b.end +1,1) eq '0';
return $b leg $a;
}
[1] This is how to specify a function as an argument. Without the &
sigil, it would have been executed right away. (The «arm» name is a pun on the
original «leg».)
Running it with the troublesome values:
$ ./max-number-arm 1 10
110
Swapping the values works as well, as does adding zeroes:
$ ./max-number-arm 10 1
110
$ ./max-number-arm 10 1
110
$ ./max-number-arm 10 100
10100
$ ./max-number-arm 100 10
10100
But this does not work:
$ ./max-number-arm 3 31 2
3132
We should have gotten 3312...
On the other hand, this works out:
$ ./max-number-arm 3 34 2
3432
An illustration may help:
3 comes before 31, but 34 comes before 3...
This is too complicated. Let us do it in another way entirely, leaving the heavy lifting to Raku:
File: max-number
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems > 0
&& all(@list) ~~ /^<[1..9]><[0..9]>*$/,
:v(:$verbose));
my @permutations = @list.permutations; # [1]
my @values = @permutations>>.join;
say ":Permutations: ", @permutations if $verbose;
say ":Values: ", @values if $verbose;
say @values.max; # [2]
[1] We have a list of values, and permutations
gives us all the ways we can sort those values. (See the verbose mode ouput for
examples.)
See
docs.raku.org/routine/permutations for more information about permutations.
[2] Use max to get the highest numeric value. We passed
them along as strings courtesy of the join, but max coerces
them to numbers.
See
docs.raku.org/routine/max
for more information about max.
Running it, with verbose mode:
$ ./max-number -v 1 23
:Permutations: [(1 23) (23 1)]
:Values: [123 231]
231
$ ./max-number -v 10 3 2
:Permutations: [(10 3 2) (10 2 3) (3 10 2) (3 2 10) (2 10 3) (2 3 10)]
:Values: [1032 1023 3102 3210 2103 2310]
3210
$ ./max-number -v 31 2 4 10
:Permutations: [(31 2 4 10) (31 2 10 4) (31 4 2 10) (31 4 10 2) (31 10 2 4) \
(31 10 4 2) (2 31 4 10) (2 31 10 4) (2 4 31 10) (2 4 10 31) (2 10 31 4) \
(2 10 4 31) (4 31 2 10) (4 31 10 2) (4 2 31 10) (4 2 10 31) (4 10 31 2) \
(4 10 2 31) (10 31 2 4) (10 31 4 2) (10 2 31 4) (10 2 4 31) (10 4 31 2) \
(10 4 2 31)]
:Values: [312410 312104 314210 314102 311024 311042 231410 231104 243110 \
241031 210314 210431 431210 431102 423110 421031 410312 410231 103124 \
103142 102314 102431 104312 104231]
431210
$ ./max-number -v 5 11 4 1 2
:Permutations: [(5 11 4 1 2) (5 11 4 2 1) (5 11 1 4 2) (5 11 1 2 4) \
(5 11 2 4 1) (5 11 2 1 4) (5 4 11 1 2) (5 4 11 2 1) (5 4 1 11 2) \
(5 4 1 2 11) (5 4 2 11 1) (5 4 2 1 11) (5 1 11 4 2) (5 1 11 2 4) \
(5 1 4 11 2) (5 1 4 2 11) (5 1 2 11 4) (5 1 2 4 11) (5 2 11 4 1) \
(5 2 11 1 4) (5 2 4 11 1) (5 2 4 1 11) (5 2 1 11 4) (5 2 1 4 11) \
(11 5 4 1 2) (11 5 4 2 1) (11 5 1 4 2) (11 5 1 2 4) (11 5 2 4 1) \
(11 5 2 1 4) (11 4 5 1 2) (11 4 5 2 1) (11 4 1 5 2) (11 4 1 2 5) \
(11 4 2 5 1) (11 4 2 1 5) (11 1 5 4 2) (11 1 5 2 4) (11 1 4 5 2) \
(11 1 4 2 5) (11 1 2 5 4) (11 1 2 4 5) (11 2 5 4 1) (11 2 5 1 4) \
(11 2 4 5 1) (11 2 4 1 5) (11 2 1 5 4) (11 2 1 4 5) (4 5 11 1 2) \
(4 5 11 2 1) (4 5 1 11 2) (4 5 1 2 11) (4 5 2 11 1) (4 5 2 1 11) \
(4 11 5 1 2) (4 11 5 2 1) (4 11 1 5 2) (4 11 1 2 5) (4 11 2 5 1) \
(4 11 2 1 5) (4 1 5 11 2) (4 1 5 2 11) (4 1 11 5 2) (4 1 11 2 5) \
(4 1 2 5 11) (4 1 2 11 5) (4 2 5 11 1) (4 2 5 1 11) (4 2 11 5 1) \
(4 2 11 1 5) (4 2 1 5 11) (4 2 1 11 5) (1 5 11 4 2) (1 5 11 2 4) \
(1 5 4 11 2) (1 5 4 2 11) (1 5 2 11 4) (1 5 2 4 11) (1 11 5 4 2) \
(1 11 5 2 4) (1 11 4 5 2) (1 11 4 2 5) (1 11 2 5 4) (1 11 2 4 5) \
(1 4 5 11 2) (1 4 5 2 11) (1 4 11 5 2) (1 4 11 2 5) (1 4 2 5 11) \
(1 4 2 11 5) (1 2 5 11 4) (1 2 5 4 11) (1 2 11 5 4) (1 2 11 4 5) \
(1 2 4 5 11) (1 2 4 11 5) (2 5 11 4 1) (2 5 11 1 4) (2 5 4 11 1) \
(2 5 4 1 11) ...]
:Values: [511412 511421 511142 511124 511241 511214 541112 541121 541112 \
541211 542111 542111 511142 511124 514112 514211 512114 512411 521141 \
521114 524111 524111 521114 521411 115412 115421 115142 115124 115241 \
115214 114512 114521 114152 114125 114251 114215 111542 111524 111452 \
111425 111254 111245 112541 112514 112451 112415 112154 112145 451112 \
451121 451112 451211 452111 452111 411512 411521 411152 411125 411251 \
411215 415112 415211 411152 411125 412511 412115 425111 425111 421151 \
421115 421511 421115 151142 151124 154112 154211 152114 152411 111542 \
111524 111452 111425 111254 111245 145112 145211 141152 141125 142511 \
142115 125114 125411 121154 121145 124511 124115 251141 251114 254111 \
254111 ...]
542111
$ ./max-number -v 1 10
:Permutations: [(1 10) (10 1)]
:Values: [110 101]
110
$ ./max-number -v 3 31 2
:Permutations: [(3 31 2) (3 2 31) (31 3 2) (31 2 3) (2 3 31) (2 31 3)]
:Values: [3312 3231 3132 3123 2331 2313]
3312
$ ./max-number -v 3 34 2
:Permutations: [(3 34 2) (3 2 34) (34 3 2) (34 2 3) (2 3 34) (2 34 3)]
:Values: [3342 3234 3432 3423 2334 2343]
3432
Looking good.
We can turn this program into a one liner as well, if we leave out the error handling:
say @*ARGS[0].permutations>>.join.max;
And that's it.