フーフ・イット

コード 2024 の出現 10 日目

パート 1

一時的な恐怖、その後の興奮

私は通常、すべてを詳しく読む前にページにざっと目を通します。

今日、私は次のものを見ました：

• グリッド
• そして道のように見えたもの

そして、これがまた最短距離での挑戦になるのではないかと心配していました。

それから読みました。

そして安堵のため息をつきました...少なくともパート 1 に関しては。

有効なパスをすべて見つける必要があります。

それは...私にはできます!

0から始める

すべての 0 を見つけなければなりません:

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0s: 見つかりました!

1 ずつ移動してみます

各 0 から、有効なパスは 9 ステップであり、各数値は最後の数値より 1 大きくなり、9 で終わります。

これは再帰の仕事のように思えます。

基本ケースが必要です:

1. 現在の数値は前の数値より正確に 1 大きいわけではありません
2. 現在の番号は 9 です

私のアルゴリズムは次のように機能するはずです:

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

今書きましたが、私が見逃していた部分は、有効な終了座標の台帳を追跡することでした。

私はしばらくこれに苦労しました。

何度もエラーが発生し、Set や配列さえも渡すことができないと誤解していました。

しかし、ありがたいことに、それを再帰関数のさらなる呼び出しに渡すのを忘れただけです。

これが私の作業中の再帰アルゴリズムです:

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

0 の座標から開始する必要があるため、最初の呼び出しでは -1 を使用します:

pathFinder(-1, zeroCoordinate, matches)

最後に、正しいスコアを取得するために、各ゼロを反復処理して宛先 9 の一意のセットを生成し、セットのサイズを保持して合計します。

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

迅速なテスト、迅速な結果

小さな入力例に対する正しい答えが生成されました。

さらに大きな入力例についても説明します。

そして...

...パズルの入力用です!!!

うおおお!!!

パート 2 では何に挑戦しますか?

パート 2

うーん、それは簡単すぎるようです

パート 1 でアルゴリズムを書いた方法では、正しい答えを得るためにいくつかの小さな変更だけが必要になるという可能性はありますか?

全部数えてください！

現在、有効な 9 をそれぞれセットに追加します。

パート 2 では、有効な 9 ごとにカウンターをインクリメントするだけでよいと思います。

試してみる価値があります!

Set を Array に変更すると出来上がりです。

例の正解です。

パズル入力に対する正しい答え。

うわー。おお。うわー。

翌日に続きます...もっと大変になる可能性があります。

以上がフーフ・イットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。