This is my response to The Weekly Challenge #288.
$str, which is an integer.
Input: $str = "123"
Output: "121"
Input: $str = "2"
Output: "1"
There are two closest palindrome "1" and "3". Therefore we return the
smallest "1".
Input: $str = "1400"
Output: "1441"
Input: $str = "1001"
Output: "999"
File: closest-palindrome
#! /usr/bin/env raku
unit sub MAIN ($str where $str ~~ UInt, :v(:$verbose)); # [1]
my $lower = $str; # [2]
my $higher = $str; # [2a]
loop # [3]
{
$lower -= 1; # [4]
if $lower >= 0 # [5]
{
say ": Down: $lower (distance { $str - $lower })" if $verbose;
if $lower.flip eq $lower # [6]
{
say $lower; # [6a]
last; # [6b]
}
}
$higher += 1; # [7]
say ": Up: $higher (distance { $higher - $str })" if $verbose;
if $higher.flip eq $higher
{
say $higher;
last;
}
}
[1] Negative integers are not palindromes, so we use the Unsigned Int type
UInt on the input to prevent any such number from beeing entered.
See docs.raku.org/type/UInt for more information about the UInt type.
[2] We are going to count down, and up [2b]. One integer at a time.
[3] An eternal loop, until we have found the nearest palindrome.
[4] Decrease the lower (downwards) counter.
[5] Skip the block if we have reached a negative value, as it is not a palindrome.
[6] Do we have a palindrome? Flipping (reversing, but that keyword works
on lists) the string with flip will tell us. If so, print the original number [6a]
and exit the loop (and the program) [6b].
See docs.raku.org/routine/flip for more information about flip.
[7] The same for the upwards counter, except that we cannot reach nagative value in this direction. Note that we did the downwards count first, as the challenge wanted the lowest number if we got matches in both directions.
Running it:
$ ./closest-palindrome 123
121
$ ./closest-palindrome 2
1
$ ./closest-palindrome 1400
1441
$ ./closest-palindrome 1001
999
Looking good.
With verbose mode:
$ ./closest-palindrome -v 123
: Down: 122 (distance 1)
: Up: 124 (distance 1)
: Down: 121 (distance 2)
121
$ ./closest-palindrome -v 2
: Down: 1 (distance 1)
1
$ ./closest-palindrome -v 1400
: Down: 1399 (distance 1)
: Up: 1401 (distance 1)
: Down: 1398 (distance 2)
: Up: 1402 (distance 2)
: Down: 1397 (distance 3)
: Up: 1403 (distance 3)
: Down: 1396 (distance 4)
: Up: 1404 (distance 4)
: Down: 1395 (distance 5)
: Up: 1405 (distance 5)
: Down: 1394 (distance 6)
: Up: 1406 (distance 6)
: Down: 1393 (distance 7)
: Up: 1407 (distance 7)
: Down: 1392 (distance 8)
: Up: 1408 (distance 8)
: Down: 1391 (distance 9)
: Up: 1409 (distance 9)
: Down: 1390 (distance 10)
: Up: 1410 (distance 10)
: Down: 1389 (distance 11)
: Up: 1411 (distance 11)
: Down: 1388 (distance 12)
: Up: 1412 (distance 12)
: Down: 1387 (distance 13)
: Up: 1413 (distance 13)
: Down: 1386 (distance 14)
: Up: 1414 (distance 14)
: Down: 1385 (distance 15)
: Up: 1415 (distance 15)
: Down: 1384 (distance 16)
: Up: 1416 (distance 16)
: Down: 1383 (distance 17)
: Up: 1417 (distance 17)
: Down: 1382 (distance 18)
: Up: 1418 (distance 18)
: Down: 1381 (distance 19)
: Up: 1419 (distance 19)
: Down: 1380 (distance 20)
: Up: 1420 (distance 20)
: Down: 1379 (distance 21)
: Up: 1421 (distance 21)
: Down: 1378 (distance 22)
: Up: 1422 (distance 22)
: Down: 1377 (distance 23)
: Up: 1423 (distance 23)
: Down: 1376 (distance 24)
: Up: 1424 (distance 24)
: Down: 1375 (distance 25)
: Up: 1425 (distance 25)
: Down: 1374 (distance 26)
: Up: 1426 (distance 26)
: Down: 1373 (distance 27)
: Up: 1427 (distance 27)
: Down: 1372 (distance 28)
: Up: 1428 (distance 28)
: Down: 1371 (distance 29)
: Up: 1429 (distance 29)
: Down: 1370 (distance 30)
: Up: 1430 (distance 30)
: Down: 1369 (distance 31)
: Up: 1431 (distance 31)
: Down: 1368 (distance 32)
: Up: 1432 (distance 32)
: Down: 1367 (distance 33)
: Up: 1433 (distance 33)
: Down: 1366 (distance 34)
: Up: 1434 (distance 34)
: Down: 1365 (distance 35)
: Up: 1435 (distance 35)
: Down: 1364 (distance 36)
: Up: 1436 (distance 36)
: Down: 1363 (distance 37)
: Up: 1437 (distance 37)
: Down: 1362 (distance 38)
: Up: 1438 (distance 38)
: Down: 1361 (distance 39)
: Up: 1439 (distance 39)
: Down: 1360 (distance 40)
: Up: 1440 (distance 40)
: Down: 1359 (distance 41)
: Up: 1441 (distance 41)
1441
$ ./closest-palindrome -v 1001
: Down: 1000 (distance 1)
: Up: 1002 (distance 1)
: Down: 999 (distance 2)
999
x or o.
Input: $matrix = [
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o', 'o'],
]
Ouput: 11
There is a block of 9 contiguous cells containing 'x'.
There is a block of 11 contiguous cells containing 'o'.
Input: $matrix = [
['x', 'x', 'x', 'x', 'x'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
]
Ouput: 11
There is a block of 11 contiguous cells containing 'x'.
There is a block of 9 contiguous cells containing 'o'.
Input: $matrix = [
['x', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
['o', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
]
Ouput: 7
There is a block of 7 contiguous cells containing 'o'.
There are two other 2-cell blocks of 'o'.
There are three 2-cell blocks of 'x' and one 3-cell.
My «Matrix as a string» syntax would work just fine here:
unit sub MAIN (Str $matrix = "x x x x o | x o o o o | x o o o o | x x x o o", :v(:$verbose));
my @m = $matrix.split("|")>>.words>>.Array;
But why bother with those extra spaces? We can use a more compact «Array of Strings» syntax, as the values are exactly one character each.
File: contiguous-block
#! /usr/bin/env raku
unit sub MAIN (*@matrix where @matrix.elems > 0 # [1]
&& ( [==] @matrix>>.elems ) # [1a]
&& all(@matrix) ~~ /^<[ox]>+$/, # [1b]
:v(:$verbose));
my @m = @matrix>>.comb>>.Array; # [2]
print-matrix(@m) if $verbose;
my $current = 1; # [3]
my %replace; # [4]
for ^@m.elems -> $row # [5]
{
for ^@m[0].elems -> $col # [6]
{
my $curr = @m[$row][$col]; # [7]
my $todo = $curr eq any('o', 'x'); # [8]
say ": Loop iteration at r:$row c:$col val:$curr - \
{ $todo ?? "Enter, todo" !! "Skip, already done" }" if $verbose;
next unless $todo; # [9]
%replace{$current} = $curr; # [10]
$current++ if set-value(@m, $row, $col, $curr, $current); # [11]
}
}
sub set-value(@m, $row, $col, $swap, $replace) # [12]
{
return unless 0 <= $row < @m.elems; # [13]
return unless 0 <= $col < @m[0].elems; # [14]
return unless @m[$row][$col] eq $swap; # [15]
say ": - r:$row c:$col | Replace @m[$row][$col] with $replace" if $verbose;
@m[$row][$col] = $replace; # [16]
set-value(@m, $row -1, $col, $swap, $replace); # [17-up
set-value(@m, $row, $col -1, $swap, $replace); # [17-left]
set-value(@m, $row, $col +1, $swap, $replace); # [17-right]
set-value(@m, $row +1, $col, $swap, $replace); # [17-down]
return True; # [18]
}
print-matrix(@m) if $verbose;
my $bag = @m[*;*].Bag; # [19]
my @sorted = $bag.sort({ $^b.value <=> $^a.value }); # [20]
say ": Bag { $bag.raku }" if $verbose;
say ": Bag Sort: { $bag.sort({ $^b.value <=> $^a.value }).raku }" if $verbose;
print-matrix(@m, @sorted.first.key) if $verbose;
say @sorted.first.value; # [21]
multi sub print-matrix (@m)
{
@m.map({ say ": " ~ $_.join(" ") });
}
multi sub print-matrix (@m, $match)
{
my $col-blue = "\e[44m";
my $col-green = "\e[42m";
my $col-red = "\e[101m";
my $col-stop = "\e[0m";
for @m -> @row
{
say ": " ~ @row.map({ $_ == $match ?? "$col-green%replace{$_}$col-stop"
!! %replace{$_} }).join(" ");
}
}
[1] Specify the matrix as an array (a slurpy array, courtesy of the * prefix)
of row characters. There must be at least one
row, all the rows must have the same length [1a], and the rows must contain
the legal characters «o» and «x» only [1b].
[2] Split up the input into a two dimentional array (a matrix). Note the
.Array coercer, as the list we have at that time is read only - and we want to
change the content later on.
[3] We are going to replace all contiguous blocks (the values in the cells belongng to that block) with an individual number, starting with 1.
[4] Used by verbose mode to print the original values instead of the numbers we replaced them with.
[5] Iterate over each row,
[6] and column.
[7] Get the current value.
[8] Does the cell still have the original value?
[9] Skip this cell if we have already replaced the value.
[10] Save the original value («o» or «x») associated with the number.
[11] Set the value for the curent cell. This is a recursive call, so it will
detect all the adjacent cells with the same value and fix them as well. A
return value of true means that it swapped the value. This is not really
needed, but makes it possible to specify a position off the grid without messing
up the counter.
[12] The procedure setting the cell value.
[13] Return if the row is outside of the matrix.
[14] Return if the column is outside of the matrix. Here we use the size of the first row, as they all have the same length. It would be possible to allow rows with different lengths, but then this check would have to use the actual row number instaed of zero.
[15] Return if we have already changed the value for this cell.
[16] Change the value.
[17] Search for adjacents cells.
Surely right and down should be sufficient?
No.
The following matrix shows why we have to allow for left and up movements as well...
: x x x x x
: o o o o x
: x o o o x
: x x x x x
13
[18] We have finished with one contiguous block.
[19] Flatten the matrix, and turn it into a Bag, a hash like structure
that counts the different values.
See docs.raku.org/routine/Bag for more information about Bag.
[20] Get a list of key/value pairs from the Bag, sorted by their frequency - largest first.
[21] Get the first pair (the largest block, or one of them (arbitrarily chosen) if there are more with the same size). Print the value; i.e. the frequency.
See docs.raku.org/routine/first for more information about first.
Running it:
$ ./contiguous-block xxxxo xoooo xoooo xxxoo
11
$ ./contiguous-block xxxxx xoooo xxxxo xoooo
11
$ ./contiguous-block xxxoo oooxx oxxoo oooxx
7
Looking good.
With verbose mode:
$ ./contiguous-block -v xxxxo xoooo xoooo xxxoo
: x x x x o
: x o o o o
: x o o o o
: x x x o o
: Loop iteration at r:0 c:0 val:x - Enter, todo
: - r:0 c:0 | Replace x with 1
: - r:0 c:1 | Replace x with 1
: - r:0 c:2 | Replace x with 1
: - r:0 c:3 | Replace x with 1
: - r:1 c:0 | Replace x with 1
: - r:2 c:0 | Replace x with 1
: - r:3 c:0 | Replace x with 1
: - r:3 c:1 | Replace x with 1
: - r:3 c:2 | Replace x with 1
: Loop iteration at r:0 c:1 val:1 - Skip, already done
: Loop iteration at r:0 c:2 val:1 - Skip, already done
: Loop iteration at r:0 c:3 val:1 - Skip, already done
: Loop iteration at r:0 c:4 val:o - Enter, todo
: - r:0 c:4 | Replace o with 2
: - r:1 c:4 | Replace o with 2
: - r:1 c:3 | Replace o with 2
: - r:1 c:2 | Replace o with 2
: - r:1 c:1 | Replace o with 2
: - r:2 c:1 | Replace o with 2
: - r:2 c:2 | Replace o with 2
: - r:2 c:3 | Replace o with 2
: - r:2 c:4 | Replace o with 2
: - r:3 c:4 | Replace o with 2
: - r:3 c:3 | Replace o with 2
: Loop iteration at r:1 c:0 val:1 - Skip, already done
: Loop iteration at r:1 c:1 val:2 - Skip, already done
: Loop iteration at r:1 c:2 val:2 - Skip, already done
: Loop iteration at r:1 c:3 val:2 - Skip, already done
: Loop iteration at r:1 c:4 val:2 - Skip, already done
: Loop iteration at r:2 c:0 val:1 - Skip, already done
: Loop iteration at r:2 c:1 val:2 - Skip, already done
: Loop iteration at r:2 c:2 val:2 - Skip, already done
: Loop iteration at r:2 c:3 val:2 - Skip, already done
: Loop iteration at r:2 c:4 val:2 - Skip, already done
: Loop iteration at r:3 c:0 val:1 - Skip, already done
: Loop iteration at r:3 c:1 val:1 - Skip, already done
: Loop iteration at r:3 c:2 val:1 - Skip, already done
: Loop iteration at r:3 c:3 val:2 - Skip, already done
: Loop iteration at r:3 c:4 val:2 - Skip, already done
: 1 1 1 1 2
: 1 2 2 2 2
: 1 2 2 2 2
: 1 1 1 2 2
: Bag (1=>9,2=>11).Bag
: Bag Sort: (2 => 11, 1 => 9).Seq
: x x x x o
: x o o o o
: x o o o o
: x x x o o
11
$ ./contiguous-block -v xxxxx xoooo xxxxo xoooo
: x x x x x
: x o o o o
: x x x x o
: x o o o o
: Loop iteration at r:0 c:0 val:x - Enter, todo
: - r:0 c:0 | Replace x with 1
: - r:0 c:1 | Replace x with 1
: - r:0 c:2 | Replace x with 1
: - r:0 c:3 | Replace x with 1
: - r:0 c:4 | Replace x with 1
: - r:1 c:0 | Replace x with 1
: - r:2 c:0 | Replace x with 1
: - r:2 c:1 | Replace x with 1
: - r:2 c:2 | Replace x with 1
: - r:2 c:3 | Replace x with 1
: - r:3 c:0 | Replace x with 1
: Loop iteration at r:0 c:1 val:1 - Skip, already done
: Loop iteration at r:0 c:2 val:1 - Skip, already done
: Loop iteration at r:0 c:3 val:1 - Skip, already done
: Loop iteration at r:0 c:4 val:1 - Skip, already done
: Loop iteration at r:1 c:0 val:1 - Skip, already done
: Loop iteration at r:1 c:1 val:o - Enter, todo
: - r:1 c:1 | Replace o with 2
: - r:1 c:2 | Replace o with 2
: - r:1 c:3 | Replace o with 2
: - r:1 c:4 | Replace o with 2
: - r:2 c:4 | Replace o with 2
: - r:3 c:4 | Replace o with 2
: - r:3 c:3 | Replace o with 2
: - r:3 c:2 | Replace o with 2
: - r:3 c:1 | Replace o with 2
: Loop iteration at r:1 c:2 val:2 - Skip, already done
: Loop iteration at r:1 c:3 val:2 - Skip, already done
: Loop iteration at r:1 c:4 val:2 - Skip, already done
: Loop iteration at r:2 c:0 val:1 - Skip, already done
: Loop iteration at r:2 c:1 val:1 - Skip, already done
: Loop iteration at r:2 c:2 val:1 - Skip, already done
: Loop iteration at r:2 c:3 val:1 - Skip, already done
: Loop iteration at r:2 c:4 val:2 - Skip, already done
: Loop iteration at r:3 c:0 val:1 - Skip, already done
: Loop iteration at r:3 c:1 val:2 - Skip, already done
: Loop iteration at r:3 c:2 val:2 - Skip, already done
: Loop iteration at r:3 c:3 val:2 - Skip, already done
: Loop iteration at r:3 c:4 val:2 - Skip, already done
: 1 1 1 1 1
: 1 2 2 2 2
: 1 1 1 1 2
: 1 2 2 2 2
: Bag (2=>9,1=>11).Bag
: Bag Sort: (1 => 11, 2 => 9).Seq
: x x x x x
: x o o o o
: x x x x o
: x o o o o
11
$ ./contiguous-block -v xxxoo oooxx oxxoo oooxx
: x x x o o
: o o o x x
: o x x o o
: o o o x x
: Loop iteration at r:0 c:0 val:x - Enter, todo
: - r:0 c:0 | Replace x with 1
: - r:0 c:1 | Replace x with 1
: - r:0 c:2 | Replace x with 1
: Loop iteration at r:0 c:1 val:1 - Skip, already done
: Loop iteration at r:0 c:2 val:1 - Skip, already done
: Loop iteration at r:0 c:3 val:o - Enter, todo
: - r:0 c:3 | Replace o with 2
: - r:0 c:4 | Replace o with 2
: Loop iteration at r:0 c:4 val:2 - Skip, already done
: Loop iteration at r:1 c:0 val:o - Enter, todo
: - r:1 c:0 | Replace o with 3
: - r:1 c:1 | Replace o with 3
: - r:1 c:2 | Replace o with 3
: - r:2 c:0 | Replace o with 3
: - r:3 c:0 | Replace o with 3
: - r:3 c:1 | Replace o with 3
: - r:3 c:2 | Replace o with 3
: Loop iteration at r:1 c:1 val:3 - Skip, already done
: Loop iteration at r:1 c:2 val:3 - Skip, already done
: Loop iteration at r:1 c:3 val:x - Enter, todo
: - r:1 c:3 | Replace x with 4
: - r:1 c:4 | Replace x with 4
: Loop iteration at r:1 c:4 val:4 - Skip, already done
: Loop iteration at r:2 c:0 val:3 - Skip, already done
: Loop iteration at r:2 c:1 val:x - Enter, todo
: - r:2 c:1 | Replace x with 5
: - r:2 c:2 | Replace x with 5
: Loop iteration at r:2 c:2 val:5 - Skip, already done
: Loop iteration at r:2 c:3 val:o - Enter, todo
: - r:2 c:3 | Replace o with 6
: - r:2 c:4 | Replace o with 6
: Loop iteration at r:2 c:4 val:6 - Skip, already done
: Loop iteration at r:3 c:0 val:3 - Skip, already done
: Loop iteration at r:3 c:1 val:3 - Skip, already done
: Loop iteration at r:3 c:2 val:3 - Skip, already done
: Loop iteration at r:3 c:3 val:x - Enter, todo
: - r:3 c:3 | Replace x with 7
: - r:3 c:4 | Replace x with 7
: Loop iteration at r:3 c:4 val:7 - Skip, already done
: 1 1 1 2 2
: 3 3 3 4 4
: 3 5 5 6 6
: 3 3 3 7 7
: Bag (5=>2,4=>2,3=>7,7=>2,1=>3,2=>2,6=>2).Bag
: Bag Sort: (3 => 7, 1 => 3, 5 => 2, 4 => 2, 7 => 2, 2 => 2, 6 => 2).Seq
: x x x o o
: o o o x x
: o x x o o
: o o o x x
7
Note that the ,trix is printed three times by verbose mode. The first is the original one, as given on the command line. The second one has all the contiguous blocks with a block identifier for each block. And the third and last has the original values, and the largest block (or one of them, if there are several) is highlighted with green.
The randomness is eaily shown by running the program several times:
$ ./contiguous-block -v "xo"
: x o
: Loop iteration at r:0 c:0 val:x - Enter, todo
: - r:0 c:0 | Replace x with 1
: Loop iteration at r:0 c:1 val:o - Enter, todo
: - r:0 c:1 | Replace o with 2
: 1 2
: Bag (2=>1,1=>1).Bag
: Bag Sort: (2 => 1, 1 => 1).Seq
: x o
1
$ ./contiguous-block -v "xo"
: x o
: Loop iteration at r:0 c:0 val:x - Enter, todo
: - r:0 c:0 | Replace x with 1
: Loop iteration at r:0 c:1 val:o - Enter, todo
: - r:0 c:1 | Replace o with 2
: 1 2
: Bag (1=>1,2=>1).Bag
: Bag Sort: (1 => 1, 2 => 1).Seq
: x o
1
But this does not really matter, as the challenge only wanted the size.
And that's it.