Robbie Hatley's Solutions To The Weekly Challenge #288

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

The Weekly Challenge for the week of 2024-09-22 through 2024-09-28 is #288. Its tasks are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 288-1: "Closest Palindrome"
Submitted by: Mohammad Sajid Anwar
You are given a string, $str, which is a non-negative 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.

Example 1:  Input: $str = "123"   Output: "121"

Example 2:  Input: $str = "2"     Output: "1"
(There are two closest palindrome "1" and "3".
Therefore we return the smallest "1".)

Example 3:  Input: $str = "1400"  Output: "1441"

Example 4:  Input: $str = "1001"  Output: "999"

This is just a matter of counting down and up to find the nearest lower and upper palindromes, then returning the lower palindrome unless the upper is closer. (Of course, one needs to implement an "is_palindrome" sub.)

Robbie Hatley's Perl Solution to The Weekly Challenge 288-1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 288-2: "Contiguous Block"
Submitted by: Peter Campbell Smith

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.

Example 1:
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'.)

Example 2:
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'.)

Example 3:
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.)

This one is complicated! The approach I came up with goes like this:

1. Assign a unique integer id to every cell in matrix.
2. Make a hash "%ids" to keep track of the block number assigned to each id.
3. For keys (0..MatrixSize-1), initialize all values of %ids to "-1", meaning "no block assigned yet".
4. Make a single pass through each cell of matrix, comparing each "current" cell to all neighbors.
5. If current cell matches a neighbor, and both have no block, assign a new block number to both.
6. If current cell matches a neighbor, and one has a block, assign block to cell that doesn't have one.
7. If current cell matches a neighbor, and both have a block, and they're the same, do nothing.
8. If current cell matches a neighbor, and both have a block, and they're different, then reassign lesser block number to all cells with greater block number, thus merging the two blocks.
9. Make array "@blocks" to serve as list of how many cells are in each block.
10. For each key $id of %ids, increment $blocks[$ids{$id}]. @blocks will now be a list of how many cells are in each block.
11. Reverse-sort the list of block sizes.
12. Return 0th element of reverse-sorted list of block sizes.

Robbie Hatley's Perl Solution to The Weekly Challenge 288-2

That's it for challenge 288; see you on challenge 289!