爪装置-js教程-PHP中文网

爪装置

霞舞

发布： 2025-02-04 13:16:01

原创

655人浏览过

爪装置

代码日历2024年第13天

第1部分

big gulp：每个置换？

又一个令人头疼的最短路径挑战。

所幸，给定的约束条件使问题看起来可解：最多100次按键 - 这意味着如果存在解，它就存在于10,000个排列中的一个：100 * 100 = 10,000；输入中每台机器用3行（加1行空行）表示，共4行。

我的输入有1280行。

因此，我的算法最多执行的计算次数为：

    100
  * 100
 ------
  10000
*
   1280
  /   4
 ------
    320
 ======
3200000

登录后复制

320万次计算，不算太坏。蛮力法可能是第一部分的一种选择。

值得一试！尝试破解解决方案。将字符串转换为整数。首先，我需要从每台机器的输入中提取六个重要数字：

```javascript

input .split('\n') .map(block => { let [ax, ay, bx, by, px, py] = [ ...block.matchall(/\d+/g).map(el => +el[0]) ] })

我在这里写下了代码。然后在代码编辑器中运行它。

然后我进行调试和修复，直到看到我期望的结果。我的工作算法如下所示：

```javascript
input
  .split('\n\n')
  .map(block => [
      ...block.matchall(/\d+/g)
    ].map(el => +el[0])
  )

登录后复制

我犯了一些愚蠢的错误，但我现在在我的控制台中看到了以下内容：

[
  [ 94, 34, 22, 67, 8400, 5400 ],
  [ 26, 66, 67, 21, 12748, 12176 ],
  [ 17, 86, 84, 37, 7870, 6450 ],
  [ 69, 23, 27, 71, 18641, 10279 ]
]

登录后复制

完美！准备进行10k次排列。

一些带有初始值的跟踪变量，嵌套循环计数为100，所有这些都减少了处理每台机器的过程：

let part1 = input.reduce( (total, machine) => {
  let [ax, ay, bx, by, px, py] = machine
  let min = Infinity
  let mina = Infinity
  let minb = Infinity
  for (let a = 0; a < 100; a++) {
    for (let b = 0; b < 100; b++) {
      // ...
    }
  }
  // ...
})

登录后复制

接下来，一些条件、加法和乘法：

// 在嵌套循环内 if ((a ax + b bx == px) && (a ay + b by == py)) { if (3 a + b a + b; } }

再次，我首先在这里写下了代码。

然后我将其复制到我的代码编辑器中并运行。

我看到了预期的获胜代币数量！

我兴奋地写下了其余的算法。

清理和调试后，这是最终的工作代码：

let part1 = input.reduce( (total, machine) => {
    let [AX, AY, BX, BY, PX, PY] = machine
    let min = Infinity
    for (let A = 0; A < 100; A++) {
        for (let B = 0; B < 100; B++) {
            if ((A * AX + B * BX === PX) && (A * AY + B * BY === PY)) {
                min = Math.min(min, 3 * A + B);
            }
        }
    }
    return total + min;
}, 0);

登录后复制

在示例输入上运行它会产生正确的答案。

在我的难题输入上呢？

...

好吧，它在一秒钟内就完成了，并在数千个答案中生成了一个答案。

正确吗？

...

是的！

太棒了！

我不需要计算机科学知识就能将我的蛮力算法重构为可以解决第二部分的东西。

不过，我还是很高兴看到这个结果！

第2部分