Diving Deep: Recursive Solutions for Palindromes and Contiguous Blocks

In this article, we will tackle two tasks from the Perl Weekly Challenge #288: finding the closest palindrome and determining the size of the largest contiguous block in a matrix. Both solutions will be implemented recursively in Perl and Go.

Table of Contents

1. Closest Palindrome
2. Contiguous Block
3. Conclusion

Closest Palindrome

The first task is to find the closest palindrome that does not include itself.

The closest palindrome is defined as the one that minimizes the absolute difference between two integers.

If there are multiple candidates, the smallest one should be returned.

Task Description

Input: A string, $str, which represents an integer.

Output: The closest palindrome as a string.

Examples

• Input: "123"
  Output: "121"

• Input: "2"
  Output: "1"
  There are two closest palindromes: "1" and "3". Therefore, we return the smallest "1".

• Input: "1400"
  Output: "1441"

• Input: "1001"
  Output: "999"

Solution

Perl Implementation

In this implementation, we utilize a recursive approach to find the closest palindrome that is not equal to the original number. The recursive function explores both lower and upper bounds around the original number:

• It checks if the current candidates (lower and upper) are valid palindromes (and not equal to the original).
• If neither candidate is valid, the function recursively decrements the lower candidate and increments the upper candidate until it finds a valid palindrome.

This recursive strategy effectively narrows down the search space, ensuring that we identify the closest palindrome while adhering to the problem's constraints.

sub is_palindrome {
    my ($num) = @_;
    return $num eq reverse($num);
}

sub find_closest {
    my ($lower, $upper, $original) = @_;
    return $lower if is_palindrome($lower) && $lower != $original;
    return $upper if is_palindrome($upper) && $upper != $original;
    return find_closest($lower - 1, $upper + 1, $original) if $lower > 0;
    return $upper + 1;
}

sub closest_palindrome {
    my ($str) = @_;
    my $num = int($str);
    return find_closest($num - 1, $num + 1, $num);
}

Go Implementation

The Go implementation follows a similar recursive strategy. It also checks the candidates around the original number, using recursion to adjust the bounds until a valid palindrome is found.

package main

import (
    "strconv"
)

func isPalindrome(num int) bool {
    reversed := 0
    original := num

    for num > 0 {
        digit := num % 10
        reversed = reversed*10 + digit
        num /= 10
    }

    return original == reversed
}

func findClosest(lower, upper, original int) string {
    switch {
        case isPalindrome(lower) && lower != original:
            return strconv.Itoa(lower)
        case isPalindrome(upper) && upper != original:
            return strconv.Itoa(upper)
        case lower > 0:
            return findClosest(lower-1, upper+1, original)
        default:
            return strconv.Itoa(upper + 1)
    }
}

func closestPalindrome(str string) string {
    num, _ := strconv.Atoi(str)
    return findClosest(num-1, num+1, num)
}

Hier ist die erweiterte Definition für den Contiguous Block:

Contiguous Block

The second task is to determine the size of the largest contiguous block in a given matrix, where all cells contain either x or o.

A contiguous block consists of elements containing the same symbol that share an edge (not just a corner) with other elements in the block, creating a connected area.

Task Description

Input: A rectangular matrix containing x and o.

Output: The size of the largest contiguous block.

Examples

• Input:
  

  [
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'o', 'o'],
  ]
  

Output: 11
There is a block of 9 contiguous cells containing x and a block of 11 contiguous cells containing o.

• Input:
  

  [
      ['x', 'x', 'x', 'x', 'x'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
  ]
  

Output: 11
There is a block of 11 contiguous cells containing x and a block of 9 contiguous cells containing o.

• Input:
  

  [
      ['x', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
      ['o', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
  ]
  

Output: 7
There is a block of 7 contiguous cells containing o, two other 2-cell blocks of o, three 2-cell blocks of x and one 3-cell block of x.

Solution

Perl Implementation

In this implementation, we utilize a recursive depth-first search (DFS) approach to determine the size of the largest contiguous block in a matrix. The main function initializes a visited matrix to track which cells have been explored. It iterates through each cell, invoking the recursive DFS function whenever it encounters an unvisited cell.

The DFS function explores all four possible directions (up, down, left, right) from the current cell. It counts the size of the contiguous block by recursively calling itself on neighboring cells that share the same symbol and have not been visited. This recursive method effectively aggregates the size of the block while ensuring that each cell is only counted once.

sub largest_contiguous_block {
    my ($matrix) = @_;
    my $rows = @$matrix;
    my $cols = @{$matrix->[0]};
    my @visited = map { [(0) x $cols] } 1..$rows;

    my $max_size = 0;

    for my $r (0 .. $rows - 1) {
        for my $c (0 .. $cols - 1) {
            my $symbol = $matrix->[$r][$c];
            my $size = dfs($matrix, \@visited, $r, $c, $symbol);
            $max_size = $size if $size > $max_size;
        }
    }

    return $max_size;
}

sub dfs {
    my ($matrix, $visited, $row, $col, $symbol) = @_;

    return 0 if $row = @$matrix || $col = @{$matrix->[0]}
                || $visited->[$row][$col] || $matrix->[$row][$col] ne $symbol;

    $visited->[$row][$col] = 1;
    my $count = 1;

    $count += dfs($matrix, $visited, $row + 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row - 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row, $col + 1, $symbol);
    $count += dfs($matrix, $visited, $row, $col - 1, $symbol);

    return $count;
}

Go Implementation

The Go implementation mirrors this recursive DFS strategy. It similarly traverses the matrix and uses recursion to explore contiguous cells with the same symbol.

package main

func largestContiguousBlock(matrix [][]rune) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    maxSize := 0

    for r := 0; r  maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row = len(matrix) || col = len(matrix[0]) ||
        visited[row][col] || matrix[row][col] != symbol {
        return 0
    }

    visited[row][col] = true
    count := 1

    count += dfs(matrix, visited, row+1, col, symbol)
    count += dfs(matrix, visited, row-1, col, symbol)
    count += dfs(matrix, visited, row, col+1, symbol)
    count += dfs(matrix, visited, row, col-1, symbol)

    return count
}

Conclusion

In this article, we explored two intriguing challenges from the Perl Weekly Challenge #288: finding the closest palindrome and determining the size of the largest contiguous block in a matrix.

For the first task, both the Perl and Go implementations effectively utilized recursion to navigate around the original number, ensuring the closest palindrome was found efficiently.

In the second task, the recursive depth-first search approach in both languages allowed for a thorough exploration of the matrix, resulting in an accurate count of the largest contiguous block of identical symbols.

These challenges highlight the versatility of recursion as a powerful tool in solving algorithmic problems, showcasing its effectiveness in both Perl and Go. If you're interested in further exploration or have any questions, feel free to reach out!

You can find the complete code, including tests, on GitHub.

The above is the detailed content of Diving Deep: Recursive Solutions for Palindromes and Contiguous Blocks. For more information, please follow other related articles on the PHP Chinese website!