I’ve been doing the Weekly
Challenges. The
latest
involved palindromic numbers and block searches. (Note that this ends
today.)
Task 1: Closest Palindrome
You are given a string, $str
, which is an integer.
Write a script to find out the closest palindrome, not including
itself. If there are more than one then return the smallest.
The closest is defined as the absolute difference minimized between
two integers.
One could probably solve many cases of this by reversing the first
half of the string onto the second half, e.g. 456 → 454, but there are
exceptions—such as the test case of 1000, for which 1001 is a
palindrome but not the correct answer.
So instead I perform a search with deltas -1, +1, -2, +2, etc. Kotlin:
fun closestpalindrome(a: String): String {
Get the int value of the string.
val n = a.toInt()
Initialise the delta and start an infinite loop.
var delta = -1
while (true) {
Work out the next candidate value, and stringify it.
val q = (n + delta).toString()
If it's a palindrome, return it.
if (q == q.reversed()) {
return q
}
Otherwise, flip the sign on the delta, and if it's now negative
subtract one.
delta = -delta;
if (delta < 0) {
delta -= 1
}
}
}
It would be equally valid to have nested loops, an outer for (1, 2, 3, …)
and an inner for (-1, +1)
and multiply them together, but
this felt cleaner.
Task 2: Contiguous Block
You are given a rectangular matrix where all the cells contain
either x
or o
.
Write a script to determine the size of the largest contiguous
block.
A contiguous block consists of elements containing the same symbol
which share an edge (not just a corner) with other elements in the
block, and where there is a path between any two of these elements
that crosses only those shared edges.
The main concern here is: can an array be a hash key? Because I want
to keep track of whether coordinates have been visited. Generally a
mutable array can't be used as a key (what happens if it changes?) but
a fixed one can. In languages where that wasn't available or I didn't
sufficiently understand how it was done, I wrote an encoder.
Thus in Raku, where I assume an arbitrary value greater than grid
size:
sub cencode($x, $y) {
return Int($x * 1000000 + $y);
}
This was a lot of work to get right. They're integers going in,
they're being subjected to integer-only operations, why wouldn't they
be integers coming out?
sub cdecode($c) {
return [Int(($c+0) div 1000000), Int($c % 1000000)];
}
sub contiguousblock(@a) {
Establish the grid sizes.
my $y = @a.elems;
my $x = @a[0].elems;
Initialise the set of possible start points to all grid points.
my %starts = SetHash.new;
for (0 .. $x - 1) -> $cx {
for (0 .. $y - 1) -> $cy {
%starts{cencode($cx, $cy)}++;
}
}
Store the largest block we've seen.
my $maxblock = 0;
If there are any start points left,
while (%starts.elems > 0) {
Pick one at random. (It doesn't matter which one it is, so if your
language's hash preserves insertion order that'll work too.)
my $start = %starts.keys[0];
my @cstart = cdecode($start);
Set up a FIFO queue. (Yes, I can do recursion. I just don't like it
when the task is more than trivial.)
my @queue;
Also we'll have a set of points visited on this search.
my %visited = SetHash.new;
Initialise both.
%visited{$start}++;
@queue.push($start);
Do a standard breadth-first search (depth-first would also work).
while (@queue.elems > 0) {
my $here = @queue.shift;
my @chere = cdecode($here);
For each possible neigbour location,
for ([-1, 0], [1, 0], [0, -1], [0, 1]) -> @delta {
make sure it lies within the grid
if ((@delta[0] >= 0 || @chere[0] > 0)
&& (@delta[0] <= 0 || @chere[0] < $x - 1)
&& (@delta[1] >= 0 || @chere[1] > 0)
&& (@delta[1] <= 0 || @chere[1] < $y - 1)) {
and calculate its coordinates.
my @cthere = [@chere[0] + @delta[0], @chere[1] + @delta[1]];
my $there = cencode(@cthere[0], @cthere[1]);
If we havent yet visited it, and it contains the same symbol as at the
start point,add it to the queue and mark it as visited.
if (%visited{$there}:!exists &&
@a[@cthere[1]][@cthere[0]]
eq @a[@cstart[1]][@cstart[0]]) {
%visited{$there}++;
@queue.push($there);
}
}
}
}
At this point we've visited every location that's reachable from the
start. The number of locations we visited is the size of the block.
my $size = %visited.elems;
if ($size > $maxblock) {
$maxblock = $size;
}
No location we've visited needs to be a start point for future
testing, because it would just give the same result. So remove them
all from the starts list.
%starts = %starts (-) %visited;
}
And return the maximum block size found.
return $maxblock;
}
In some languages (Rust, Python, Kotlin, Scala, Crystal, and possibly
others I don't know well enough) I can use a tuple as the key and
avoid the c
variables and the encode/decode stepx.
Full code on
github.