蹄它

代碼來臨 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 開始，有效路徑有九步，其中每個數字都比最後一個大 1，以 9 結束。

這聽起來像是遞歸的工作。

我需要一個基本案例：

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 改為數組，瞧！

範例的正確答案。

我輸入的謎題的正確答案。

哇。哇。哇。

第二天......這可能會更加困難。

以上是蹄它的詳細內容。更多資訊請關注PHP中文網其他相關文章！