暴雪盆地-DEV365 开发者社区

Advent of Code 2022 Day 24

Try the simulator using your puzzle input!

第1部分

这一切都已经导致了这个
我希望完成的工作
模拟器：重新创建输入为2D数组
确定启动和结束坐标
移动暴风雪
对暴风雪进行分类
包裹暴风雪
重新供应网格
代表与数字重叠的暴风雪
考虑球员运动和等待
使用我的模拟器，直到我得到[在此处插入形容词]
告诉我我可以去哪里
最后机会：递归算法

这一切都一直在这样做

2D网格
shortest path问题
graph search算法挑战
多个rounds
根据规则移动的作品
移动包裹在网格周围
第一部分决定一块是否可以移动，第二部分移动所有零件

我希望完成的

构建模拟器
我可以在哪里使用箭头键来表达每个定向移动和表达don't move的特定键
防止无效的移动
接受有效的动作并更新网格以适应更改
显示执行的总动作

如果我可以为这些规格构建模拟器，那么我认为我可以从头到尾至少识别一条路径...

我希望构建模拟器可以帮助我实现一种递归算法，我可以用来通过迷宫来探索几条可行的道路，其中一个是最短的。

最终，我不希望解决第1部分，可悲的是。

让我们看看如何进行！

模拟器：将输入重新创建为2D数组

我遵循我通常的步骤来构建新的模拟器：

复制式代码中的新沙盒
更新标题，ID，默认输入值
调整字体尺寸
在我的初始化函数中写下前几行

此时，我的模拟器解析了textarea的输入，创建一个2D数组并在页面上显示：

确定开始和结束坐标

您的探险开始于顶行中唯一的非墙位置，需要达到底行中唯一的非墙位置。

我在javascript中的算法：

let start = [
  0, 
  grid[0].indexOf('.')
]
let end = [
  grid.length - 1, 
  grid[grid.length - 1].indexOf('.')
]

我使用E和X暂时将标记放在生成的地图上，以验证我的算法正确工作：

移动暴风雪

四种暴风雪，每种都表示运动方向：

let moves = {
  '>': [0,1],
  'v': [1,0],
  '<': [0,-1],
  '^': [-1,0]
}

然后是包装。

所有四个边缘都有墙
如果下一步将暴风雪推入墙壁...
...相反，它应该从同一行或列中的另一个网格边缘移动到两个单元格

绘制时：

< moves to A
v moves to B
> moves to C
^ moves to D

######
#.B^.#
#<..A#
#C..>#
#.vD.#
######

i预见了一个精心设计的switch语句和/或系列if...else if条款。

但是首先，我需要知道所有暴风雪在哪里！

分类暴风雪

我需要存储每个暴风雪的位置和面向。

使用更简单的示例输入：

#.#####
#.....#
#>....#
#.....#
#...v.#
#.....#
#####.#

我想要类似于此的数据结构：

{
  '>': [
    [2, 1]
  ],
  'v': [
    [4, 4]
  ]
}

我认为这将使他们的面对面更容易分组。这样，我可以参考早期的数据结构来移动它们。

我在JavaScript中生成以上数据结构的算法：

for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (['>','v','<','^'].includes(grid[row][col])) {
      blizzards[grid[row][col]].push([row, col])
    }
  }
}

我现在知道每个暴风雪在哪里，并有一张有关如何移动它们的地图。

是时候编写处理包装的逻辑了。

包裹暴风雪

再次有用的图：

######
#.B^.#
#<..A#
#C..>#
#.vD.#
######

我的伪代码中的算法：

Wrap when the blizzard is:
  Facing left and in column 1
    To same row, column (row length - 2)
  Facing right and in column (row length - 2)
    To same row, column 1
  Facing up and in row 1
    To same column, (grid length - 2)
  Facing down and in row (grid length - 2)
    To same column, row 1

我在JavaScript中的运动和包装功能：

function calculateNewBlizzardPositions() {
  let positions = {'>': [], 'v': [], '<': [], '^': []}
  for (let blizzard in blizzards) {
    switch (blizzard) {
      case '<':
        blizzards[blizzard].forEach(([row, col]) => {
          if (col == 1) {
            positions[blizzard].push([row, grid[row].length - 2])
          } else {
            positions[blizzard].push([row, col - 1])
          }
        })
        break;
      case '>':
        blizzards[blizzard].forEach(([row, col]) => {
          if (col == grid[row].length - 2) {
            positions[blizzard].push([row, 1])
          } else {
            positions[blizzard].push([row, col + 1])
          }
        })
        break;
      case '^':
        blizzards[blizzard].forEach(([row, col]) => {
          if (row == 1) {
            positions[blizzard].push([grid.length - 2, col])
          } else {
            positions[blizzard].push([row - 1, col])
          }
        })
        break;
      case 'v':
        blizzards[blizzard].forEach(([row, col]) => {
          if (row == grid.length - 2) {
            positions[blizzard].push([1, col])
          } else {
            positions[blizzard].push([row + 1, col])
          }
        })
        break;
    }
  }
  return positions
}

重新呈现网格

我可以根据初始难题输入渲染网格。

现在，我需要根据暴风雪的新位置重新渲染网格 - 最终是玩家的位置。

我走了很长的路线：

将数组转换为字符串
用.s替换所有<>^v
将字符串转换为数组
根据其新坐标更新适当的数组值

我在javascript中的算法：

blizzards = calculateNewBlizzardPositions(blizzards)
grid = grid
  .map(row => row.join(''))
  .join('\n')
  .replaceAll(/[<>v^]/g, '.')
  .split('\n')
  .map(line => line.split(''))
for (let blizzard in blizzards) {
  blizzards[blizzard].forEach(([row, col]) => {
    grid[row][col] = blizzard
  })
}
gridEl.textContent = grid.map(row => row.join('')).join('\n')

a，我现在可以坐下来观看暴风雨，如果我这样选择：

要真正从说明中重新创建图表，我需要表示任何带有数字的重叠的暴风雪（2-4）。

代表与一个数字重叠的暴风雪

Build a dictionary with coordinates as keys and counts as values
For each coordinate pair in each of the four symbol lists
  Create a key if it doesn't exist and set it's value to 0
  Increment the value of the key by 1

For each coordinate pair in each of the four symbol lists
  Place in the cell of the grid either:
    The symbol if the count in the dictionary is 1
    The count if the count in the dictionary is greater than 1

我在javascript中更新的算法：

let counts = {}
for (let blizzard in blizzards) {
  blizzards[blizzard].forEach(b => {
    let position = b.join('|')
    if (!(position in counts)) {
      counts[position] = 0
    }
    counts[position]++
  })
}
for (let blizzard in blizzards) {
  blizzards[blizzard].forEach(([row, col]) => {
    grid[row][col] = counts[[row, col].join('|')] > 1 
      ? counts[[row, col].join('|')] 
      : blizzard
  })
}

我的模拟器现在与示例图：

考虑球员运动和等待

现在要面对真正的挑战：

处理下一步的键盘输入
检查所需的移动是否有效
仅在搬家有效时更新董事会

我最终没有使用我的四键值对相对坐标词典moves。

太好了，因为我可以重新标记键以匹配用户可以按下的键的四个代码：

let moves = {
  'ArrowRight': [0,1],
  'ArrowDown': [1,0],
  'ArrowLeft': [0,-1],
  'ArrowUp': [-1,0]
}

我将收听keyup事件，并根据event.code的字符串值执行不同的操作，只有按下Start按钮：

document.addEventListener('keyup', function(event) {
  if (playEl.getAttribute('disabled') == 'disabled') {
    switch (event.code) {
      case 'Slash':
        break;
      case 'ArrowUp':
        break;
      case 'ArrowDown':
        break;
      case 'ArrowLeft':
        break;
      case 'ArrowRight':
        break;
    }
  }
})

我决定让左箭头键映射上方的前向斜线键进入等待的动作。

幸运的是，正如我的算法目前所写的那样，这意味着我只能调用移动暴风雪并重新呈现网格的功能：

      case 'Slash':
        nextMinute()
        break;

我需要知道最近通过的是什么，所以我添加了一个适当增加的跟踪器。

处理Slash盒很容易。

但是每个其他人都需要分解我当前的nextMinute()功能，以便我可以在下一分钟播放以确定该动作是否有效，并且只有当它实际上是在更新板上...否则否则就可以t移动任何暴风雪。

我走了！

...

我使事情变得比必要的更复杂。

我忽略了几件事。

这是我学到的，固定和重构的：

我的replaceAll()的regex仅占四个符号。我忘了用E,2,3,4重置单元！
检查提出的玩家移动是否有效时，我忘了检查它是否进入墙壁！这需要我嵌套的for环中的一条额外的线，以构建一个新的阵列，以跟踪所有墙壁的坐标。然后是我的有效移动检查的附加条件。
我忽略了等待如何无效的举动，因为暴风雪可能会进入我的位置。这促使我将Slash键添加到我的moves对象，并使用相对坐标0,0添加。更奇妙的是，它让我删除一个巨大的if子句，该子句刚刚检查了被按下的斜杠键。现在，我的算法在单个条件下对五个键中的任何一个说明！

在所有令人愉快的调试之后，我的模拟器现在正确地播放了样本演练：

使用我的模拟器，直到我得到[在此处插入形容词]

现在它起作用 - 至少在样本输入上 - 我可能应该尝试探索一些路径，看看我是否曾经到达出口。

我想我会尝试直到感到沮丧，无聊或不耐烦。

无论如何，我为我制作了这个模拟器而感到自豪。

...

我尝试了几次。

我无法在不移动或等待的情况下超越第10行和第六列。

知道 - 在任何给定的一分钟 - 我可以采取哪些动作可能会有所帮助。

告诉我我可以去哪里

我想在我的模拟器中添加五个按钮，如果在下一分钟可以进行相应的动作，请点亮。

它需要更多的DOM操作。

，但更重要的是，它需要一些冗余代码才能在按键下和之后的下一分钟播放：一旦点亮按钮，然后再次处理操作。

这是一个很好的练习。

，我的模拟器很酷，因此很酷：

可悲的是，我没有找到通往终点线的单一路径。

最后机会：递归算法

我真的想要一颗金星。

我仍然怀疑我会得到它。

，但我相信我可以从模拟器中的代码中构建递归功能，该功能可能能够通过迷宫找到路径。

我再次走了！

...

我构建了递归功能：

一段时间以来，它没有超越第一次下降
经过大量的刮擦和代码分析后，我发现了错误：我没有更新暴雪位置的字典
我将其设置为显示分钟数，如果它将播放器移至目标端坐标
我按跑步并等待，希望我不会碰到任何与堆栈相关的错误
我最终看到了一个数字！
那么更多相同的数字
比这个数字还要少。
那么什么都没有
一段时间

在非智能中，这是正确的答案，我决定提交它。

错误的答案。太高。

我花了很多时间试图优化我的递归功能，这样它将：

如果路径有大量的Waits
如果路径试图重新审视起始坐标
如果会议记录越过最小的数字，我知道它可以到达
以不同的顺序探索每个方向

什么都没有用。

实际上，我再也没有看到这两个数字。

是时候扔毛巾了。

我完成的

我构建了一个交互式模拟器，该模拟器应适用于任何有效的拼图输入！
我练习了在JavaScript中使用多种数据类型时使用的大量技术！
我构建了一种递归算法，该算法发现了一些看似有效的路径！
我又证明了我没有技能来解决涉及图形的拼图，这些路径是在某些节点上双重折叠的路径（例如'a'' - >'b' - >'b' - >'a' - >'b'）

我很沮丧，我没有获得金星。

，但我对我编写的所有代码以及试图解决今天的难题的建造印象深刻。

我很想明天再赚一颗金星，并系好我最低的明星数量。

但是，如果我不这样做，至少我将不再有最低恒星计数的领带（目前是2021和2019的34）。