This is my response to The Weekly Challenge #354.
The challenge texts vary in length, but the second one this time is quite possibly the most verbose so far. I have chosen to include said texts in my articles so that they can stand on their own. I am not ending that, but starting with this article the challenge text will be hidden by default. Click on the arrow symbol to unhide it.
Input: @ints= (4, 2, 1, 3)
Output: [1, 2], [2, 3], [3, 4]
Input: @ints = (10, 100, 20, 30)
Output: [10, 20], [20, 30]
Input: @ints = (-5, -2, 0, 3)
Output: [-2, 0]
Input: @ints = (8, 1, 15, 3)
Output: [1, 3]
Input: @ints = (12, 5, 9, 1, 15)
Output: [9, 12], [12, 15]
File: min-abs-diff
#! /usr/bin/env raku
unit sub MAIN (*@ints where all(@ints) ~~ Int # [1]
&& @ints.repeated.elems == 0 # [1a]
&& @ints.elems > 0, # [1b]
:v(:$verbose));
my @sorted = @ints.sort; # [2]
my $mad = Inf; # [3]
my @res; # [4]
for 0 .. @ints.end -1 -> $i # [5]
{
my $left = @sorted[$i]; # [6]
my $right = @sorted[$i+1]; # [6a]
my $diff = @sorted[$i+1] - @sorted[$i]; # [6b]
if $diff < $mad # [7]
{
say ": [$left,$right] -> diff $diff (new,reset)" if $verbose;
$mad = $diff; # [7a]
@res = (($left,$right),); # [7b]
}
elsif $diff == $mad # [8]
{
say ": [$left,$right] -> diff $diff (equal,add)" if $verbose;
@res.push: ($left,$right); # [8a]
}
elsif $verbose
{
say ": [$left,$right] -> diff $diff (ignore)" if $verbose;
}
}
say @res.map({ "[$_[0], $_[1]]" }).join(", "); # [9]
[1] A slurpy array of integers, with no repetitions
(given with repeated [1a]) and at least 1 element [1b].
See docs.raku.org/routine/repeated for more information about repeated.
[2] We are looking for the shortest distance between pairs of values, and sorting them will make that possible.
[3] The shortest distance, initially larger than Life, the Universe and Everything.
[4] The resulting pairs will end up here.
[5] Iterate over the index of the first value in the pair. The second value is the one to the right of it (in the array), so we stop at the last but one.
[6] Get the left and right [6a] values, and the difference [6b]. The values are sorted, so we are guaranteed a positive value (and can skip the absolute merriment).
[7] Is the new MAD (i.e. Min Abs Diff) lower than the old one? If so, set it as the new MAD [7a] and reset the result to this pair [7b].
[8] Is the new MAD the same as the old one? If so, add the pair to the result [8a].
[9] Print the result. Each pair in brackets with a separating comma between the two values, and commas between the pairs.
Running it:
$ ./min-abs-diff 4 2 1 3
[1, 2], [2, 3], [3, 4]
$ ./min-abs-diff 10 100 20 30
[10, 20], [20, 30]
$ ./min-abs-diff -- -5 -2 0 3
[-2, 0]
$ ./min-abs-diff 0 1 15 3
[0, 1]
$ ./min-abs-diff 12 5 9 1 15
[9, 12], [12, 15]
Looking good.
With verbose mode:
$ ./min-abs-diff -v 4 2 1 3
: [1,2] -> diff 1 (new,reset)
: [2,3] -> diff 1 (equal,add)
: [3,4] -> diff 1 (equal,add)
[1, 2], [2, 3], [3, 4]
$ ./min-abs-diff -v 10 100 20 30
: [10,20] -> diff 10 (new,reset)
: [20,30] -> diff 10 (equal,add)
: [30,100] -> diff 70 (ignore)
[10, 20], [20, 30]
$ ./min-abs-diff -v -- -5 -2 0 3
: [-5,-2] -> diff 3 (new,reset)
: [-2,0] -> diff 2 (new,reset)
: [0,3] -> diff 3 (ignore)
[-2, 0]
$ ./min-abs-diff -v 0 1 15 3
: [0,1] -> diff 1 (new,reset)
: [1,3] -> diff 2 (ignore)
: [3,15] -> diff 12 (ignore)
[0, 1]
$ ./min-abs-diff -v 12 5 9 1 15
: [1,5] -> diff 4 (new,reset)
: [5,9] -> diff 4 (equal,add)
: [9,12] -> diff 3 (new,reset)
: [12,15] -> diff 3 (equal,add)
[9, 12], [12, 15]
m x n matrix and an integer, $k > 0.
$k times.
grid[i][j] moves to grid[i][j + 1]grid[i][n - 1] moves to grid[i + 1][0]grid[m - 1][n - 1] moves to grid[0][0]
Input: @matrix = ([1, 2, 3],
[4, 5, 6],
[7, 8, 9],)
$k = 1
Output: ([9, 1, 2],
[3, 4, 5],
[6, 7, 8],)
Rule 1: grid[i][j] -> grid[i][j+1] for j < n-1.
We take elements from the original grid at (i, j) and put them into
new_grid[i][j+1].
From original:
(0,0): 1 -> new_grid[0][1] = 1
(0,1): 2 -> new_grid[0][2] = 2
(1,0): 4 -> new_grid[1][1] = 4
(1,1): 5 -> new_grid[1][2] = 5
(2,0): 7 -> new_grid[2][1] = 7
(2,1): 8 -> new_grid[2][2] = 8
New grid looks after Rule 1:
([?, 1, 2],
[?, 4, 5],
[?, 7, 8],)
Rule 2: grid[i][n-1] -> grid[i+1][0] for i < m-1.
Elements from original last column (except last row) go to next row's
first column.
From original:
(0,2): 3 -> new_grid[1][0] = 3
(1,2): 6 -> new_grid[2][0] = 6
Now new grid after Rules 1 + 2:
([?, 1, 2],
[3, 4, 5],
[6, 7, 8],)
Rule 3: grid[m-1][n-1] -> grid[0][0].
Original (2,2): 9 -> new_grid[0][0] = 9.
Now new_grid is complete:
([9, 1, 2],
[3, 4, 5],
[6, 7, 8],)
Input: @matrix = ([10, 20],
[30, 40],)
$k = 1
Output: ([40, 10],
[20, 30],)
Rule 1 (move right in same row if not last column):
(0,0): 10 -> new[0][1] = 10
(1,0): 30 -> new[1][1] = 30
After Rule 1:
([?, 10],
[?, 30],)
Rule 2 (last col -> next row’s first col, except last row):
(0,1): 20 -> new[1][0] = 20
After Rule 2:
([?, 10],
[20, 30],)
Rule 3 (bottom-right to top-left):
(1,1): 40 -> new[0][0] = 40
After Rule 3:
([40, 10],
[20, 30],)
Input: @matrix = ([1, 2],
[3, 4],
[5, 6],)
$k = 1
Output: ([6, 1],
[2, 3],
[4, 5],)
Rule 1:
(0,0): 1 -> new[0][1] = 1
(1,0): 3 -> new[1][1] = 3
(2,0): 5 -> new[2][1] = 5
After Rule 1:
( [?, 1],
[?, 3],
[?, 5],)
Rule 2:
(0,1): 2 -> new[1][0] = 2
(1,1): 4 -> new[2][0] = 4
After Rule 2:
([?, 1],
[2, 3],
[4, 5],)
Rule 3:
(2,1): 6 -> new[0][0] = 6
After Rule 3:
([6, 1],
[2, 3],
[4, 5],)
Input: @matrix = ([1, 2, 3],
[4, 5, 6],)
$k = 5
Output: ([2, 3, 4],
[5, 6, 1],)
Shift 1
Rule 1
1 -> (0,1)
2 -> (0,2)
4 -> (1,1)
5 -> (1,2)
Rule 2
3 -> (1,0) (last column of row 0)
Rule 3
6 -> (0,0) (bottom-right corner)
Result
[6, 1, 2]
[3, 4, 5]
----------------------------
Shift 2
Starting from the previous matrix:
[6, 1, 2]
[3, 4, 5]
Rule 1
6 -> (0,1)
1 -> (0,2)
3 -> (1,1)
4 -> (1,2)
Rule 2
2 -> (1,0)
Rule 3
5 -> (0,0)
Result
[5, 6, 1]
[2, 3, 4]
----------------------------
Shift 3
[5, 6, 1]
[2, 3, 4]
Rule 2: 1 -> (1,0)
Rule 3: 4 -> (0,0)
Others follow Rule 1
Result
[4, 5, 6]
[1, 2, 3]
----------------------------
Shift 4
[4, 5, 6]
[1, 2, 3]
Result
[3, 4, 5]
[6, 1, 2]
----------------------------
Shift 5
[3, 4, 5]
[6, 1, 2]
Result
[2, 3, 4]
[5, 6, 1]
Final Output (after k = 5 shifts)
([2, 3, 4],
[5, 6, 1])
Input: @matrix = ([1, 2, 3, 4])
$k = 1
Output: ([4, 1, 2, 3])
Rule 1:
(0,0): 1 -> new[0][1] = 1
(0,1): 2 -> new[0][2] = 2
(0,2): 3 -> new[0][3] = 3
After Rule 1:
([?, 1, 2, 3])
Rule 2:
(0,3): 4 -> new[1][0] ??
Wait — but i=0, n-1=3, next row i+1=1 doesn’t exist (m=1).
So this is actually a special case where Rule 2 should not apply.
because m=1, so (0,3) goes by Rule 3 actually.
The rules say:
grid[i][j] -> grid[i][j+1] for j < n-1.
grid[i][n-1] -> grid[i+1][0] for i < m-1.
grid[m-1][n-1] -> grid[0][0].
For m = 1:
Elements (0,0),(0,1),(0,2) follow Rule 1 -> (0,1),(0,2),(0,3).
Element (0,3) is (m-1, n-1), so follows Rule 3 -> (0,0).
Actually, that means after Rule 1:
We put 1,2,3 in positions 1,2,3, leaving position 0 empty.
Then Rule 3 puts 4 in position 0.
So final directly:
[4, 1, 2, 3]
The lazy approach is to recognise that all we really have
to do here is to treat the matrix as a one dimentional array, and move
the last element to the front of the array (in a loop, $k times).
I have (re)used my «matrix as a string» format, used in e.g. Challenge #343.2: Champion Team. The examples translate to these strings:
"1 2 3 | 4 5 6 | 7 8 9"
"10 20 | 30 40"
"1 2 | 3 4 | 5 6"
"1 2 3 | 4 5 6"
"1 2 3 4"
#! /usr/bin/env raku
unit sub MAIN ($matrix, # [1]
UInt :$k where $k > 0, # [2]
:v(:$verbose));
class matrix # [3]
{
has @.values; # [3a]
has Int $.width; # [3b]
method new($string) # [4]
{
my @matrix = $matrix.split("|")>>.words>>.Numeric; # [5]
die "No data" unless @matrix[0].elems; # [6]
die "Uneven row lenghts" unless [==] @matrix>>.elems; # [7]
return self.bless(values => @matrix[*;*], # [8]
width => @matrix[0].elems);
}
method matrix # [9]
{
return @.values.batch($.width); # [9a]
}
method gist # [10]
{
return "(\n" ~ self.matrix.map({ " [" ~ @_.join(", ") \
~ "]\n" }).join ~ ")"; # [10a]
}
method shift(Int $shift) # [11]
{
@.values.unshift(@.values.pop) for ^$shift; # [11a]
}
}
my $m = matrix.new($matrix); # [12]
if $verbose {
say ": Pre-shift:";
print $m.gist.lines.map({ ": $_\n"}).join; # [15]
}
$m.shift($k); # [13]
say $m; # [14]
[1] The «matrix as a string» string, duh.
[2] The shift value, as a named argument. We start with an Unsigned Integer and remove the zero to get the positive integer constraint.
[3] A custom class for the matrix, with class members for the values (as an
array) [3a] and the width (as an integer) [3b]. These values are readable from
the outside (as I use . in the names. Using ! would have made them
unaccessible from outside). Note that they are not writeable from the outisde,
as I have not added explicit methods for that.
[4] A custom constructor, overriding the builtin one, taking the «matrix as a string» as argument.
[5] Split the string nicely into a two dimentional array. The Numeric
coercer is there to get rid of non-numeric values (if any), and to get rid of
the IntStr & co types that do not look very nice in output.
[6] Ensure that we get at least 1 element on the first row.
[7] Ensure that all the rows have
the same length (using the Reduction Metaoperator []
with == to compare all the values in one go).
See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator [].
[8] Set up a new object and return it. The [*;*] indexy thing flattens
the matrix into a one dimentional array.
This would have been a suitable location for a test that all the values are integers. Feel free to add it, if you want...
[9] Do you want the matrix as a matrix, i.e. aa a two dimentional
array? If so, use this method. It will split the (internal) array into chunks
of the correct length with batch, and return the lot.
See docs.raku.org/routine/batch for more information about batch.
[10] We are going to print the matrix after the shift. Printing
requires stringification, which the built-in gist method does for us. It
does not know how to handle our «matrix» class, so we supply a custom version.
We wrap the whole shebang in "(" and ")", and each matrix row (note
the use of the «matrix» method to get the matrix) is wrapped in brackets, with
the values separated by commas [10a].
[11]
The challenge used the word «shift» to describe the operation,
so let us use that name for the method. Shift as many times as required. We
do this by removing the last element (with pop), and adding
that value to the front (with unshift) [7a].
See docs.raku.org/routine/pop for more information about pop.
See docs.raku.org/routine/unshift for more information about unshift.
[12] Set up a new matrix, with the «matrix as a string» argument.
[13] Do the shift(s).
[14] Print the resulting (post shift) matrix.
[15] Explicit use of the gist method to get the stringified version,
and a map on the rows (in the output) with lines to add my
«:» verbose mode prefix.
Running it:
$ ./shift-grid -k=1 "1 2 3 | 4 5 6 | 7 8 9"
(
[9, 1, 2]
[3, 4, 5]
[6, 7, 8]
)
$ ./shift-grid -k=1 "10 20 | 30 40"
(
[40, 10]
[20, 30]
)
$ ./shift-grid -k=1 "1 2 | 3 4 | 5 6"
(
[6, 1]
[2, 3]
[4, 5]
)
$ ./shift-grid -k=5 "1 2 3 | 4 5 6"
(
[2, 3, 4]
[5, 6, 1]
)
$ ./shift-grid -k=1 "1 2 3 4"
(
[4, 1, 2, 3]
)
Looking good.
With verbose mode:
$ ./shift-grid -v -k=1 "1 2 3 | 4 5 6 | 7 8 9"
: Pre-shift:
: (
: [1, 2, 3]
: [4, 5, 6]
: [7, 8, 9]
: )
(
[9, 1, 2]
[3, 4, 5]
[6, 7, 8]
)
$ ./shift-grid -v -k=1 "10 20 | 30 40"
: Pre-shift:
: (
: [10, 20]
: [30, 40]
: )
(
[40, 10]
[20, 30]
)
$ ./shift-grid -v -k=1 "1 2 | 3 4 | 5 6"
: Pre-shift:
: (
: [1, 2]
: [3, 4]
: [5, 6]
: )
(
[6, 1]
[2, 3]
[4, 5]
)
$ ./shift-grid -v -k=5 "1 2 3 | 4 5 6"
: Pre-shift:
: (
: [1, 2, 3]
: [4, 5, 6]
: )
(
[2, 3, 4]
[5, 6, 1]
)
$ ./shift-grid -v -k=1 "1 2 3 4"
: Pre-shift:
: (
: [1, 2, 3, 4]
: )
(
[4, 1, 2, 3]
)
And that's it.