桥梁修复

代码来临 2024 年第 7 天

第 1 部分

今年第一次递归

至少这就是我今天想要赢得一颗金星的方式：

• 从完整列表开始
• 检查加法和乘法
• 对于每个结果，继续列表的其余部分
• 直到我超过或匹配总数

困难在于细节。

让我们开始吧！

制定我的算法

首先，我需要将每一行解析为数字列表：

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

第一个元素是所需的总数。

其余的是方程的有序操作数。

我需要在递归函数中考虑到这一点。

这是我的递归函数：

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

这是使用它的reduce：

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

正如我所希望但从未预料到的，它为示例输入生成了正确的答案！

它会完成处理我的拼图输入吗？

如果是这样，它会生成正确的答案吗？

老实说我不确定......

确实如此！！！

哇！！！

尽管我很兴奋，但我担心下一部分要么会添加更多运算符，要么需要一些高级 CS 来使递归不再是可行的解决方案。

第2部分

完全出乎意料！而且难度更大

我该怎么做？

...

几天后...

回顾一下我的思考过程：

• 就像在我的退货条件中添加第三个条款一样简单吗？ 不
• 我的第 1 部分递归函数是否配置正确才能成功？ 不
• 哦，不，通过先前的操作累积金额是否可行？ 不
• 我真的需要用新策略来解决这个问题吗？ 是的

考虑所有新的变化

对于这个方程：

292: 11 6 16 20

给定三个运算符，这些都是可能的方程：

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

也许我可以构建每个方程的字符串，并在递归函数中手动对其求值。

例如：
我在最外层函数调用中以空字符串开始：

""

从那里，我使用下一个数字创建三个变体：

"" + "+N"
"" + "*N"
"" + "N"

嗯，但这对第一个数字不起作用。

我需要用第一个数字开始我的第一个函数调用，而不是空字符串：

"N"

同样的事情：

"N" + "+N"
"N" + "*N"
"N" + "N"

是的，应该可以。

最后，我将获得这些示例变体，所有这些都可以评估：

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

跳至：我对其进行了编码...并发现了一个更大的问题

我编写的代码成功生成了方程的所有变体。

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

• i 用于沿着数字列表
• 仅当 i 位于倒数第二个索引之前或位于倒数第二个索引时，最后一个子句才会继续

该函数获取四个值：

1. 数字列表的副本，减去预期总数
2. 下一个索引
3. 由三个字符串之一连接而成的方程字符串
4. 相同的测试号码

我使用与第 1 部分几乎相同的签名来调用该函数：

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

区别在于我作为参数传递的内容：

1. 没有预期总金额的清单
2. 从索引 0 开始
3. 包含第一个数字的字符串
4. 预计总金额

好消息：

• 它生成所有方程变化

坏消息：

• 它使用 PEMDAS 计算所有方程，而不是从左到右

我应该更清楚...内置的 JavaScript 求值器会默认使用正确的操作顺序，而不是从左到右。

这确实给我的算法带来了更大的麻烦：

• 我将不得不分解每个方程并逐个部分地评估它

呜呜呜。

谢天谢地，我想我知道该怎么做。

手动做数学

我需要 JavaScript 来计算这样的方程：

292: 11 6 16 20

按此顺序：

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

我想将该方程分成几个部分：

""

我了解的唯一方法是使用这个三链表达式：

"" + "+N"
"" + "*N"
"" + "N"

我用空格填充每个运算符，只是将其用作分隔符。

关于这个方程部分列表的事实：

• 它将始终包含 3 个或更多的奇数项目

如何在迭代每个操作数-运算符-操作数对的循环中利用这一事实？

这是我的想法：

• 删除前三项
• 将它们作为字符串连接，并将其作为数学表达式进行计算
• 将结果重新附加到方程列表的开头
• 重复直到方程式列表为空

希望它能起作用！

我在 JavaScript 中工作的数学模拟器：

"N"

好消息：

• 它向我显示了预期的计算值

坏消息：

• 我仍然没有得到示例输入中一个方程的正确答案

示例答案不会错...可以吗？

我不断生成的答案比预期答案少了大约 7k。

这让我认为我的算法没有识别出这个方程是正确的：

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

在示例输入的解释中，这是获胜方程式：

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

我的算法评估该方程并生成以下结果：

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

那是因为我的算法是这样运行的：

292: 11 6 16 20

我不明白它怎么可能是其他数字。

所以...我用谷歌搜索了。

我找到了我的答案，它一如既往地隐藏在简单的网站解释中：

所有运算符仍然从左到右计算。

我在每个递归函数调用中预先连接值。

相反，我的算法应该这样做：

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

现在我明白了应该发生什么，我可以调整我的算法以匹配该处理行为吗？

从左到右......这次是真的

值得庆幸的是，调整我的算法相对容易。

我添加了一个replaceAll()子句来解释||。

我处理每三个项目的新 while 循环如下所示：

""

我调整了退货声明的||子句包含这些字符，而不是立即连接两个数字。

测试和重新测试

我在示例输入上运行了算法。

它终于生成了正确的答案！！

多么轻松啊！！

我想知道它是否会完成运行并在我的拼图输入上生成正确的答案。

按运行...

...

...

我得到答案了！

它很大，所以这可能是一个好兆头。

这是正确答案吗？

...

不。太高了。

真糟糕。

我错过了一个边缘案例吗？

我的获胜方程的条件很简单，就是处理后的数学等于测试量。

但是，如果其中一个变体方程允许数字子集生成正确答案怎么办？

为了捕获并排除这种情况，我更新了 if 条件以包含另一个子句：

"" + "+N"
"" + "*N"
"" + "N"

这样，只有当所有数字都处理完毕并且结果数量等于测试数时，方程才会被计算在内。

大问题：

• 这会改变我得到的答案吗？

再次按下运行...

...

嗯，看起来确实还是一样的答案。

哦，等等，末尾附近有两个数字不同！

我的新答案比以前少了 80。

是否有一个以 80 为预期数量的方程式？

是的！

"N"

有没有一种方法可以在不使用所有数字的情况下得到 80？

是的！

"N" + "+N"
"N" + "*N"
"N" + "N"

这是我需要排除的唯一边缘情况吗？

正在提交我的新答案...

正确！！！

呜呼！！！

我做到了！！！

那个。曾是。筋疲力尽。令人兴奋。并且真的跑了。并且具有挑战性。

以及我喜欢做这些谜题的所有原因。

继续下一篇！

以上是桥梁修复的详细内容。更多信息请关注PHP中文网其他相关文章！