RogerBW's Blog

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.