The Weekly Challenge 288

Closest Palindrome & Contiguous Block: String Reflection and Grid DFS

Lubos Kolouch September 23, 2024 Challenge Details GitHub Solutions

Task 1: Closest Palindrome

You are given a string, $str, representing an integer.

Write a script to find the closest palindrome integer to the given integer string, excluding the integer itself. If there are multiple palindromes with the same minimal absolute difference, return the smallest one.

Method Explanation

Finding the closest palindrome to a number string $S$ without scanning all numbers sequentially requires analyzing how palindromes are formed around their center. A palindrome is completely determined by its first half (including the middle element if the length is odd).

To generate candidate palindromes that could be closest to $S$:

  1. Extract the prefix consisting of the first $\lceil \text{length} / 2 \rceil$ digits.
  2. Consider three primary variations: prefix $- 1$, prefix $+ 0$, and prefix $+ 1$. Reflect each variation to form a full palindrome of the same length.
  3. Handle boundary/edge cases where the number of digits changes:
    • Underflow edge case: A sequence of nines with length $\text{length} - 1$ (e.g., $1000 \to 999$).
    • Overflow edge case: A number of the form $10\dots01$ with length $\text{length} + 1$ (e.g., $999 \to 1001$).
  4. Filter out the original number itself (as required by the task).
  5. Select the candidate with the minimum absolute difference from the target number. In the event of a tie in difference, choose the numerically smaller palindrome.

Perl Solution

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
use Test::More;

signature_for closest_palindrome => (
    method     => 0,
    positional => [ Str ],
);

sub closest_palindrome ($n_str) {
    my $n       = int($n_str);
    my $len     = length($n_str);
    my $is_even = $len % 2 == 0;
    my $mid     = int($len / 2);

    # Obtain the left part of the number
    my $left_len = $is_even ? $mid : $mid + 1;
    my $left     = substr($n_str, 0, $left_len);
    my @candidates;

    for my $i (-1, 0, 1) {
        my $new_left = int($left) + $i;
        next if $new_left < 0;
        my $new_left_str = "$new_left";

        my $palindrome;
        if ($is_even) {
            $palindrome = $new_left_str . reverse($new_left_str);
        } else {
            $palindrome = $new_left_str . reverse(substr($new_left_str, 0, -1));
        }
        push @candidates, $palindrome;
    }

    # Edge cases (e.g. 99 -> 101, 100 -> 99)
    push @candidates, ('9' x ($len - 1)) if $len > 1;
    push @candidates, '1' . ('0' x ($len - 1)) . '1';

    # Remove the original number from candidates
    @candidates = grep { $_ ne $n_str } @candidates;

    # Find the closest palindrome
    my $min_diff           = undef;
    my $closest_palindrome = undef;
    for my $candidate (@candidates) {
        my $diff = abs(int($candidate) - $n);
        if (!defined $min_diff || $diff < $min_diff || ($diff == $min_diff && int($candidate) < int($closest_palindrome))) {
            $min_diff           = $diff;
            $closest_palindrome = $candidate;
        }
    }
    return $closest_palindrome;
}

Python Solution

from __future__ import annotations
from collections.abc import Sequence

def closest_palindrome(n_str: str) -> str:
    """Find the closest palindrome integer string to n_str, excluding itself."""
    n = int(n_str)
    length = len(n_str)
    is_even = length % 2 == 0
    mid = length // 2
    left_len = mid if is_even else mid + 1
    left = n_str[:left_len]
    candidates: set[str] = set()

    for diff in (-1, 0, 1):
        new_left = str(int(left) + diff)
        if len(new_left) != left_len and diff != 0:
            continue
        if is_even:
            pal = new_left + new_left[::-1]
        else:
            pal = new_left + new_left[:-1][::-1]
        candidates.add(pal)

    # Edge cases (e.g. 100 -> 99, 99 -> 101)
    if length > 1:
        candidates.add("9" * (length - 1))
    candidates.add("1" + ("0" * (length - 1)) + "1")

    candidates.discard(n_str)

    min_diff: int | None = None
    closest_pal = ""
    for cand in sorted(candidates, key=lambda x: (abs(int(x) - n), int(x))):
        if not cand:
            continue
        diff = abs(int(cand) - n)
        if diff == 0:
            continue
        if min_diff is None or diff < min_diff:
            min_diff = diff
            closest_pal = cand

    return closest_pal

Task 2: Contiguous Block

You are given a rectangular matrix of 'x' and 'o'.

Write a script to find 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.

Method Explanation

This problem is a classic connected-component size calculation on a 2D grid, commonly known as the Flood Fill or Island Area problem.

Key steps:

  1. Maintain a 2D visited matrix or table initialized to false.
  2. Iterate through every cell (i, j) of the matrix.
  3. If cell (i, j) has not yet been visited, initiate a Depth-First Search (DFS) or Breadth-First Search (BFS) starting at that cell.
  4. During the search, traverse the 4-directional adjacent neighbors (up, down, left, right) that match the symbol of the starting cell and have not been visited.
  5. Accumulate the count of cells belonging to this connected component and update the global maximum block size.
  6. Return the maximum block size found across the entire matrix.

Perl Solution

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Str);
use List::Util qw(max);
use Test::More;

signature_for largest_contiguous_block => (
    method     => 0,
    positional => [ ArrayRef[ArrayRef[Str]] ],
);

sub dfs ($matrix_ref, $visited_ref, $i, $j, $symbol) {
    my $rows = scalar @$matrix_ref;
    my $cols = scalar @{ $matrix_ref->[0] };

    return 0 if $i < 0 || $i >= $rows || $j < 0 || $j >= $cols;
    return 0 if $visited_ref->[$i][$j];
    return 0 if $matrix_ref->[$i][$j] ne $symbol;

    $visited_ref->[$i][$j] = 1;
    my $size = 1;

    # Explore neighbors (up, down, left, right)
    $size += dfs($matrix_ref, $visited_ref, $i - 1, $j, $symbol);
    $size += dfs($matrix_ref, $visited_ref, $i + 1, $j, $symbol);
    $size += dfs($matrix_ref, $visited_ref, $i, $j - 1, $symbol);
    $size += dfs($matrix_ref, $visited_ref, $i, $j + 1, $symbol);

    return $size;
}

sub largest_contiguous_block ($matrix_ref) {
    return 0 if !@$matrix_ref || !@{ $matrix_ref->[0] };

    my $rows = scalar @$matrix_ref;
    my $cols = scalar @{ $matrix_ref->[0] };
    my @visited = map { [(0) x $cols] } (0 .. $rows - 1);
    my $max_block_size = 0;

    for my $i (0 .. $rows - 1) {
        for my $j (0 .. $cols - 1) {
            if (!$visited[$i][$j]) {
                my $block_size = dfs($matrix_ref, \@visited, $i, $j, $matrix_ref->[$i][$j]);
                $max_block_size = $block_size if $block_size > $max_block_size;
            }
        }
    }

    return $max_block_size;
}

Python Solution

from __future__ import annotations

def largest_contiguous_block(matrix: list[list[str]]) -> int:
    """Find the size of the largest contiguous block in a matrix of 'x' and 'o'."""
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    visited = [[False] * cols for _ in range(rows)]
    max_block_size = 0

    def dfs(i: int, j: int, symbol: str) -> int:
        if i < 0 or i >= rows or j < 0 or j >= cols:
            return 0
        if visited[i][j]:
            return 0
        if matrix[i][j] != symbol:
            return 0

        visited[i][j] = True
        size = 1
        size += dfs(i - 1, j, symbol)
        size += dfs(i + 1, j, symbol)
        size += dfs(i, j - 1, symbol)
        size += dfs(i, j + 1, symbol)
        return size

    for i in range(rows):
        for j in range(cols):
            if not visited[i][j]:
                block_size = dfs(i, j, matrix[i][j])
                max_block_size = max(max_block_size, block_size)

    return max_block_size