蹄它

代码来临 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中文网其他相关文章！