蹄它

代码来临 2024 年第 10 天

第 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]);
    }
  }
}

0：找到！

尝试递增移动

从每个 0 开始，有效的路径包含九个步骤，每个数字都比前一个大 1，最终以 9 结束。

这听起来像是递归的应用场景。

我需要一个基本情况：

1. 当前数字不比前一个数字大 1
2. 当前数字是 9

我的算法工作流程如下：

1. 起始数字
2. 当前坐标

获取当前数字

如果它不比起始数字恰好大 1 返回 false 否则 如果它是 9 返回当前坐标 如果它不是 9 继续检查正交方向上的坐标

现在写完了，我意识到漏掉的部分是跟踪有效结束坐标的记录。

我为此纠结了一段时间。

我不断收到错误，错误地让我认为我无法传入 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 => {
            let newCoord = [coord[0] + dir[0], coord[1] + dir[1]];
            if (
                newCoord[0] >= 0 &&
                newCoord[0] < input.length &&
                newCoord[1] >= 0 &&
                newCoord[1] < input[0].length &&
                !memo.has(newCoord.join(','))
            ) {
                pathfinder(current, newCoord, 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 部分

嗯，这似乎太简单了

我在第一部分编写算法的方式是否意味着只需要进行一些小的修改就能得到正确的答案？

数一数吧！

现在，我将每个有效的 9 添加到一个集合中。

对于第二部分，我想我只需要为每个有效的 9 增加一个计数器。

值得一试！

将 Set 更改为数组，瞧！

示例的正确答案。

我的谜题输入的正确答案。

哇。哇。哇。

第二天……这可能会更难。