加里凡特卫兵-js教程-PHP中文网

加里凡特卫兵

DDD

发布： 2024-12-12 13:42:22

转载

762人浏览过

加里凡特卫兵

代码来临 2024 年第 6 天

第 1 部分

一种非常熟悉的谜题

二维网格
到处都有障碍
追踪路径
计算访问过的独特图块

让我们开始吧！

一次一步

解析网格：

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

登录后复制

识别守卫的起始位置并将其替换为空图块：

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

登录后复制

创建一个对象来跟踪守卫当前的旋转：

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

登录后复制

守卫开始面向北，因此后续移动需要访问较小索引的行
遇到每个障碍物，警卫必须右转
这将使她面朝东方，因此后续移动需要访问更大指数的列
每次下一个单元格成为障碍物时，我的算法都会从列表中拉出第一项并将其移到后面

跟踪访问的单元格：

let visited = new set()

登录后复制

每次移动时，我都会尝试将字符串化坐标添加到此 set() 中。

移动守卫：

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let olddirection = facing.shift();
      facing.push(olddirection);
    }
  } else {
    break;
  }
}

登录后复制

解释：

keep going until manually broken out of
  add the current coordinate to the tracked list
  record the next location to visit
  if it is within the grid
    if it is empty cell
      move the guard
    else if it is an obstacle
      rotate the guard
  else
    break out of the loop

登录后复制

该算法成功为示例输入生成了 41 个已访问单元格列表！

它会为我的拼图输入生成正确的答案吗？

是的！！！

太棒了。

进入第二部分！

第2部分

我有点预见到了这一点，并且很害怕它

老兄，检查每个可能的选项以获得一个有效的谜题。

阅读时我最大的问题是：

如何识别守卫何时进入循环？

但我想我知道：

我会追踪朝向以及坐标
如果列表包含下一个添加的副本，则循环即将开始

是时候让事情变得更加复杂了！

循环遍历每个单元格以找到所有循环

首先，我想生成一个包含 . 的所有单元格的列表，不包括守卫的起始单元格：

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

登录后复制

然后，使用reduce 来迭代每个 .在网格中，复制网格和原始防护位置，在reduce内移动大量原始代码，扩展while循环以包含具有当前状态实例的跟踪坐标和旋转列表的条件：

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

登录后复制

很多。

但是它有效！至少在示例输入上。

它对我有用吗？？？

嗯...运行了 30 秒。

但是...它产生了答案！

这是...

正确答案!!!

呜呼！！！

第 1 部分很容易。第 2 部分是一个艰难但受欢迎的规模提升。

袋子里还有两颗金星！

进入第 7 天。