| 27 September 2024 | Challenge 288 |
Contiguous Palindromes
Task 1: Closest Palindrome
Submitted by: Mohammad Sajid Anwar
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.
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"
Solution
In the following we’ll consider the head of a number as the number’s first half if it has an even length and the first half including the middle digit if it has an odd length.
For every positive number \(n\) there are three palindromic candidates around it:
- The palindrome \(p_0\) build from the mirrored head of the number.
- The palindrome \(p_+\) build from the mirrored increment of the head.
- The palindrome \(p_-\) build from the mirrored decrement of the head.
As we have \(p_- \lt p_0 \lt p_+\) and \(p_- \lt n \lt p_+\), depending on the relation between \(n\) and \(p_0\), one of \(p_-\), \(p_0\) or \(p_+\) can be neglected. Let \(p^*\) be the solution. Then we have:
- \(p^* \in \{p_-, p_0\}\) if \(n < p_0\)
- \(p^* \in \{p_0, p_+\}\) if \(n > p_0\)
- \(p^* \in \{p_-, p_+\}\) if \(n = p_0\) (i.e. \(n\) is itself a palindrome)
Comparing the arithmetic mean of the two candidates against \(n\) reveals the solution.
Special cases are \(n \le 0\).
As there are no negative palindromes, here the solution is 0 or 1.
There remains the task to find \(p_+\) and \(p_-\).
In the general case, we just need to increment/decrement \(n\)’s head and build a new palindrome thereof.
The length of \(n\) determines the length of the palindrome, where odd and even lengths need to be treated differently, e.g. the head 123 results in 12321 for an odd and 123321 for an even length.
Here special cases arise when the head of \(p_-\) or \(p_+\) crosses a power of 10 compared to the head of \(p_0\):
- a
9has to be appended to the head after decrementing for even lengths - a
0has to be removed from the end of the head after incrementing for odd lengths - odd and even lengths are exchanged
Some special provisions are required for a zero head:
- it always “crosses a power of
10” - it must be used to produce an odd length
The sub near_palindrome is used to build \(p_-\), \(p_0\) and \(p_+\) depending on the second argument \(d \in \{-1, 0, 1\}\), while the sub closest_palindrome provides the solution to the task.
use strict;
use warnings;
use experimental 'signatures';
sub near_palindrome ($n, $d) {
my $odd = length($n) % 2;
my $head = substr $n, 0, (length($n) + $odd) / 2;
my $l0 = length $head;
$head += $d;
if (!$head || $l0 != length $head) {
$head = $head * 10 + 9 if $d < 0 && !$odd;
$head /= 10 if $d > 0 && $odd;
$odd ^= !!$head;
}
$head . reverse($odd ? substr $head, 0, -1 : $head);
}
sub closest_palindrome ($n) {
return 0 + !$n if ($n += 0) < 1;
my $p0 = near_palindrome($n, 0);
my $lo = $p0 < $n ? $p0 : near_palindrome($n, -1);
my $hi = $p0 > $n ? $p0 : near_palindrome($n, 1);
$lo + $hi >= 2 * $n ? $lo : $hi;
}
See the full solution to task 1.
Task 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.
Solution
For this task two of my favored CPAN modules may be combined: PDL and Graph.
We take the matrix’ elements as vertices of an undirected graph, where two vertices are connected with an edge if they are horizontally or vertically adjacent and contain the same value.
(This approach generalizes the task to matrices containing characters not limited to x and o.)
The task may be reformulated as finding the largest connected component in the resulting graph.
Using PDL to identify the graph’s edges:
Comparing the matrix with itself shifted by one row or column, where the first or last row or column is omitted.
Collecting the matching indices and use
the stringified coordinate ndarrays as vertices.
Here is a sample session in the pdl shell explaining the procedure for the matrix from example 1 on the “row edges”.
The matrix is created as a PDL::Char object that is capable of handling the task’s data format.
It gets converted into a numeric ndarray containing the ASCII codes of the first character of each cell on the fly.
pdl> require PDL::Char
pdl> $m = PDL::Char->new([
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o', 'o'],
])->((0))->long
pdl> $r = whichND $m(0:-2) == $m(1:-1)
pdl> p $r
[
[0 0]
[1 0]
[2 0]
[1 1]
[2 1]
[3 1]
[1 2]
[2 2]
[3 2]
[0 3]
[1 3]
[3 3]
]
Now duplicating the coordinate entries and adding a shift to the duplicates to convert these into the neighbor vertices:
pdl> $e = $r->dummy(1, 2) + indx([0, 0], [1, 0])
pdl> p $e
[
[
[0 0]
[1 0]
]
[
[1 0]
[2 0]
]
[
[2 0]
[3 0]
]
[
[1 1]
[2 1]
]
[
[2 1]
[3 1]
]
[
[3 1]
[4 1]
]
[
[1 2]
[2 2]
]
[
[2 2]
[3 2]
]
[
[3 2]
[4 2]
]
[
[0 3]
[1 3]
]
[
[1 3]
[2 3]
]
[
[3 3]
[4 3]
]
]
The “inner matrices” represent the horizontal edges that will be used to build the graph. Here is a visualization of the resulting edges. For the vertical edges the procedure is analogous with the role of rows and columns exchanged.
pdl> p join " <-> ", map "$_", $_->dog for $e->dog
[0 0] <-> [1 0]
[1 0] <-> [2 0]
[2 0] <-> [3 0]
[1 1] <-> [2 1]
[2 1] <-> [3 1]
[3 1] <-> [4 1]
[1 2] <-> [2 2]
[2 2] <-> [3 2]
[3 2] <-> [4 2]
[0 3] <-> [1 3]
[1 3] <-> [2 3]
[3 3] <-> [4 3]
Graph’s connected_components method returns an AoA of all connected components with their corresponding vertices.
Here we are interested in the sizes only, especially the maximum thereof.
Using PDL’s max to avoid requiring another module.
use v5.12;
use warnings;
use PDL;
use PDL::Char;
use PDL::NiceSlice;
use Graph::Undirected;
sub max_cont_block {
state $r = indx [0, 0], [1, 0];
state $c = indx [0, 0], [0, 1];
my $m = PDL::Char->new(@_)->((0))->long;
my $g = Graph::Undirected->new;
$g->add_edge(map "$_", $_->dog) for
(whichND($m(0:-2,) == $m(1:-1,))->dummy(1, 2) + $r)->dog,
(whichND($m(,0:-2) == $m(,1:-1))->dummy(1, 2) + $c)->dog;
max long map scalar @$_, $g->connected_components;
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.