Advent of Code 2022 Day 20

第1部分

1. 从来没有那么乐于进入圈子
2. 困难的部分：跟踪原始位置
3. 逐步：使用示例输入
4. 回到硬部分

从来没有那么乐于绕圈

在2D网格之后，在数万亿个区域，搜索和图形算法和四氨基模拟器中...

...我很高兴有这个看似简单的任务，即在数组中移动项目！

困难的部分：跟踪原始位置

示例是欺骗性的：

• 数字都是不同的

我的难题输入不是很好：

• 许多数字重复两次或多次

这意味着我不能使用跟踪方法以其原始顺序和indexOf()阵列方法的数字队列的方法：

• 一个后来可能已经移动的数字，导致indexOf()标记了数字的错误实例

嗯。我将如何解释这一点？

逐步：使用示例输入

我知道我需要一个跟踪相同数字的多个实例的策略。

但是，首先，我想确保我可以构建一个在所有不同数字列表中工作的算法，例如在示例输入列表中。

再次列表是：

1
2
-3
3
-2
0
4

splice()ing和shift()ing

原始顺序的数字为：

let order = [1, 2, -3, 3, -2, 0, 4]

我需要移动第一个项目。

indexOf()第一个数字1是0：

numbers.indexOf(order.shift()) // 0

我需要向前移动1。

let amount = order.shift()
let start = numbers.indexOf(amount)
numbers.splice(start, 1)
numbers.splice((start + amount) % numbers.length, 0, amount)

第一步工作！

它将为每个后续步骤工作吗？

输入：for循环

我认为我可以在输入中的每个数字上执行上面的四行：

for (let i = 0; i < numbers.length; i++) {
  let amount = order.shift()
  let start = numbers.indexOf(amount)
  numbers.splice(start, 1)
  numbers.splice((start + amount) % numbers.length, 0, amount)
}

与所示的顺序不同，还是它？

移动-2：
之后，该示例显示了这样的列表

-2 moves between 4 and 1:
1, 2, -3, 0, 3, 4, -2

我的列表在头部而不是尾巴上有-2。

起初我很担心。

然后我记得这是一个圆圈。

只要-2在4和1之间，我很好！

最后一部分是检查0的数千个索引。

我的JavaScript中的算法

let numbers = input.split('\n').map(Number)
let order = numbers.slice()
for (let i = 0; i < numbers.length; i++) {
  let amount = order.shift()
  let start = numbers.indexOf(amount)
  numbers.splice(start, 1)
  numbers.splice((start + amount) % numbers.length, 0, amount)
}
return numbers[(numbers.indexOf(0) + 1000) % numbers.length] +
  numbers[(numbers.indexOf(0) + 2000) % numbers.length] +
  numbers[(numbers.indexOf(0) + 3000) % numbers.length]

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

我想交换拼图输入并运行它，但是我知道这是错误的答案，因为我的输入重复了数字。

所以，现在又回到了制定处理该策略的策略。

回到艰难的部分

回顾：

• 我的难题输入有5000个数字，但其中许多人出现不止一次
• 因此，我不能依靠indexOf()来找到下一个数字的正确实例
• 那么，我可以依靠什么？

好吧，我可以存储数字，而不是仅存储数字，而是当前索引：

let order = [1, 2, -3, 3, -2, 0, 4].map((n, i) => [n, i])

但是现在怎么了？

• 每个步骤，我需要在移动的数字的原点和目标索引之间更新每个数字索引
• 在我的难题输入中，大多数数字将接近10k索引
• 加起来 ton 数组访问和更新
• 另外，我必须考虑运动方向，并以+1或-1
更新索引
• 哦，我必须考虑一个从我的数组中移动到尾部的物品，这不是本质上的圆形

我可能会想利用一个循环链接列表，但是有了我必须进行的所有查找和编辑，它似乎也不是很有性能。

再次，我很难过。

另一个零星日

真是个bummer！

阅读了这个难题的描述后，我感到有信心。

可悲的是，实际的难题输入在我的计划中以重复的数字扔了一个扳手。

将此添加到我想有一天要再试一次的难题列表中。