深く掘り下げる: 回文と連続ブロックの再帰的ソリューション

この記事では、Perl Weekly Challenge #288 の 2 つのタスク、つまり最も近い回文の検索と、行列内の最大の連続ブロックのサイズの決定に取り組みます。どちらのソリューションも Perl と Go で再帰的に実装されます。

目次

1. 最も近い回文
2. 連続ブロック
3. 結論

最も近い回文

最初のタスクは、それ自体を含まない最も近い回文を見つけることです。

最も近い回文は、2 つの整数間の絶対差を最小化する回文として定義されます。

複数の候補がある場合は、最小のものを返す必要があります。

タスクの説明

入力: 整数を表す文字列 $str。

出力: 文字列として最も近い回文。

例

• 入力: "123"
  出力: "121"

• 入力: "2"
  出力: "1"
  最も近い回文は「1」と「3」の 2 つです。したがって、最小の「1」を返します。

• 入力: "1400"
  出力: "1441"

• 入力: "1001"
  出力: "999"

解決

Perlの実装

この実装では、再帰的アプローチを利用して、元の数値と等しくない最も近い回文を見つけます。再帰関数は、元の数値の下限と上限の両方を調べます:

• 現在の候補 (下位と上位) が有効な回文である (元の回文と等しくない) かどうかをチェックします。
• どちらの候補も有効でない場合、関数は有効な回文が見つかるまで、再帰的に下位の候補を減算し、上位の候補を増分します。

この再帰的戦略は、探索空間を効果的に絞り込み、問題の制約を守りながら最も近い回文を確実に特定します。

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の実装

Go の実装は、同様の再帰戦略に従っています。また、有効な回文が見つかるまで再帰を使用して範囲を調整し、元の数値の周囲の候補をチェックします。

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)
}

連続ブロック:

の定義

連続ブロック

2 番目のタスクは、すべてのセルに x または o が含まれる、指定された行列内の最大の連続ブロックのサイズを決定することです。

連続ブロックは、ブロック内の他の要素とエッジ (角だけではなく) を共有する同じシンボルを含む要素で構成され、接続された領域を作成します。

タスクの説明

入力: x と o を含む長方形行列

出力: 最大の連続ブロックのサイズ。

例

• 入力:
  

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

出力: 11
x を含む 9 個の連続するセルのブロックと、o を含む 11 個の連続するセルのブロックがあります。

• 入力:
  

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

出力: 11
x を含む 11 個の連続するセルのブロックと、o を含む 9 個の連続するセルのブロックがあります。

• 入力:
  

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

出力: 7
o を含む 7 つの連続したセルのブロック、o の他の 2 セル ブロックが 2 つ、x の 2 セル ブロックが 3 つ、x の 3 セル ブロックが 1 つあります。

解決

Perlの実装

この実装では、再帰的深さ優先検索 (DFS) アプローチを利用して、行列内の最大の連続ブロックのサイズを決定します。 main 関数は、どのセルが探索されたかを追跡するために、訪問済み行列を初期化します。各セルを反復処理し、未訪問のセルに遭遇するたびに再帰的 DFS 関数を呼び出します。

DFS 関数は、現在のセルから考えられる 4 つの方向 (上、下、左、右) をすべて探索します。同じシンボルを共有し、まだ訪問されていない隣接セル上で自分自身を再帰的に呼び出すことにより、連続ブロックのサイズをカウントします。この再帰的方法は、各セルが 1 回だけカウントされるようにしながら、ブロックのサイズを効果的に集計します。

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 < 0 || $row >= @$matrix || $col < 0 || $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の実装

Go の実装は、この再帰的 DFS 戦略を反映しています。同様に行列を走査し、再帰を使用して同じシンボルを持つ連続したセルを探索します。

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 < rows; r++ {
        for c := 0; c < cols; c++ {
            symbol := matrix[r][c]
            size := dfs(matrix, visited, r, c, symbol)
            if size > maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row < 0 || row >= len(matrix) || col < 0 || 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.

以上が深く掘り下げる: 回文と連続ブロックの再帰的ソリューションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。