桥梁修复-js教程-PHP中文网

Bridge Repair

代码来临 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

登录后复制

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

登录后复制

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

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

""

登录后复制

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

"" + "+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 部分几乎相同的签名来调用该函数：

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

登录后复制

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

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

好消息：

它生成所有方程变化

坏消息：

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

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

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

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

呜呜呜。

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

手动做数学

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

292: 11 6 16 20

登录后复制

按此顺序：

登录后复制

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

""

登录后复制

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

"" + "+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

登录后复制

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

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

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

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

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

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

登录后复制

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