谷神星搜索

代码来临 2024 年第 4 天

第 1 部分

X 标记（数百个？）点

令我惊讶的是，到目前为止还没有像这样的文字搜索谜题。

这似乎令人畏惧，但我的策略是：

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

在示例中检查此策略使我相信这是一种成功的方法。

现在是令人兴奋的部分：从头开始编码整个事情！

找到网格中每个 X 的索引...最终

首先，我必须将输入解析为二维字符数组：

let grid = input.split('\n').map(line => line.split(''))

我在网格谜题中经常遇到的一个障碍是考虑越界索引。

如果我从边界单元格 - 或靠近边界的单元格开始 - 并朝边缘方向走这么远，我最终会遇到越界的行或列。

我有两种策略来处理这个问题：

1. 向我的条件添加检查以查找不存在的行或列
2. 用足够的行和列填充网格，这样就不会出现越界的风险

对于这个挑战，我选择#2。

用 3 单元格厚边框填充网格，如下所示：

grid = grid.map(line => ['.','.','.',...line,'.','.','.'])
grid = [
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  ...grid,
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.')
]

示例网格现在如下所示：

................
................
................
...MMMSXXMASM...
...MSAMXMSMSA...
...AMXSXMAAMM...
...MSAMASMSMX...
...XMASAMXAMM...
...XXAMMXXAMA...
...SMSMSASXSS...
...SAXAMASAAA...
...MAMMMXMMMM...
...MXMXAXMASX...
................
................
................

现在我准备好对填充网格中每个 X 的坐标进行编目：

let Xs = []
for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == "X") {
      Xs.push([row, col])
    }
  }
}

成功：在示例网格中找到了所有 19 个 X！

从每个X向八个方向走三步

所有八个相对坐标都编码为 8 元素数组：

let dirs = [
  [-1,-1],
  [-1,0],
  [-1,1],
  [0,-1],
  [0,1],
  [1,-1],
  [1,0],
  [1,1]
]

现在主要算法：

For each X
  For each direction
    Create an array that starts with X
    Do 3 times
      Move one cell in this direction
      Add the value of that cell to the array
    Check whether the concatenation of all four values is "XMAS"
      If it is, increment a tally

在 JavaScript 中：

Xs.reduce((total, coord) => {
  dirs.forEach((dir) => {
    let [row, col] = coord;
    let [y, x] = dir;
    let word = ["X"];
    for (let i = 0; i < 3; i++) {
      row += y;
      col += x;
      word.push(grid[row][col]);
    }
    if (word.join("") == "XMAS") {
      total++;
    }
  });
  return total;
}, 0);

它为示例输入生成正确的答案！

当我在拼图输入上运行它时会发生什么？！！

我得到一个数字：几千个“XMAS”

这是正确答案吗？

就是这样！！！

呜呼！！！

迫不及待地想看看第二部分有什么精彩内容......

第2部分

哦天哪。这变得有点复杂了。但可行！

在第 1 部分中，我一直在寻找 X。

现在，我正在寻找

女士

在第 1 部分中，我将字母写成一条直线来组成单词。

现在，我正在寻找 5 单元短语的四种配置：

M S   M M   S M   S S
 A     A     A     A
M S   S S   S M   M M

一个 M 可以是多个 X-MAS 的一部分。

通过检查每一个M，我很可能会遇到好几次。

我需要为每场比赛构建一个字符串化坐标的 Set()。这样，我只占一个 X-MAS 实例一次。

突然——辉煌！ - 主意

我不会检查每一个M。

我会检查每一个A。

我将按顺时针顺序检查对角相邻的四个单元格。

X-MAS 比赛将符合以下四种模式之一：

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

`

唷！这比我最初的想法要简单得多。

而且我应该能够重新利用我的大部分第 1 部分代码！

复制粘贴调整

在网格中找到所有 As：
js
让 As = [];
for (let row = 0; row for (let col = 0; col if (网格[行][列] == "A") {
As.push([行, 列]);
}
}
}

建立要检查的相对坐标顺序：
js
让阿迪尔斯 = [
[-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

将比赛的得分相加：
js
让part2 = As.reduce((总计, 坐标) => {
让顺时针 = Adirs.map((dir) => {
让 [行，列] = 坐标；
让 [y, x] = dir;
返回网格[行y][列x];
});
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(顺时针.join(""))) {
总计;
}
返回总计；
}, 0);

它为示例输入生成正确的答案！

现在检查我的拼图输入...

确实！！！正确答案！！！

我很高兴我突然想到使用 As 而不是 Ms.

我确信，为我节省了数小时的时间来解决头痛问题。

这是另一个有趣且容易上手的谜题！

我想知道第五天会发生什么。

以上是谷神星搜索的详细内容。更多信息请关注PHP中文网其他相关文章！