代碼來(lái)臨 2024 年第 7 天

第 1 部分

今年第一次遞歸

至少這就是我今天想要贏得一顆金星的方式：

• 從完整列表開(kāi)始
• 檢查加法和乘法
• 對(duì)于每個(gè)結(jié)果，繼續(xù)列表的其余部分
• 直到我超過(guò)或匹配總數(shù)

困難在于細(xì)節(jié)。

讓我們開(kāi)始吧！

制定我的算法

首先，我需要將每一行解析為數(shù)字列表：

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

第一個(gè)元素是所需的總數(shù)。

其余的是方程的有序操作數(shù)。

我需要在遞歸函數(shù)中考慮到這一點(diǎn)。

這是我的遞歸函數(shù)：

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)

正如我所希望但從未預(yù)料到的，它為示例輸入生成了正確的答案！

它會(huì)完成處理我的拼圖輸入嗎？

如果是這樣，它會(huì)生成正確的答案嗎？

老實(shí)說(shuō)我不確定......

確實(shí)如此！??！

哇?。?！

盡管我很興奮，但我擔(dān)心下一部分要么會(huì)添加更多運(yùn)算符，要么需要一些高級(jí) CS 來(lái)使遞歸不再是可行的解決方案。

第2部分

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

我該怎么做？

...

幾天后...

回顧一下我的思考過(guò)程：

• 就像在我的退貨條件中添加第三個(gè)條款一樣簡(jiǎn)單嗎？ 不
• 我的第 1 部分遞歸函數(shù)是否配置正確才能成功？ 不
• 哦，不，通過(guò)先前的操作累積金額是否可行？ 不
• 我真的需要用新策略來(lái)解決這個(gè)問(wèn)題嗎？ 是的

考慮所有新的變化

對(duì)于這個(gè)方程：

292: 11 6 16 20

給定三個(gè)運(yùn)算符，這些都是可能的方程：

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 

也許我可以構(gòu)建每個(gè)方程的字符串，并在遞歸函數(shù)中手動(dòng)對(duì)其求值。

例如：
我在最外層函數(shù)調(diào)用中以空字符串開(kāi)始：

""

從那里，我使用下一個(gè)數(shù)字創(chuàng)建三個(gè)變體：

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

嗯，但這對(duì)第一個(gè)數(shù)字不起作用。

我需要用第一個(gè)數(shù)字開(kāi)始我的第一個(gè)函數(shù)調(diào)用，而不是空字符串：

"N"

同樣的事情：

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

是的，應(yīng)該可以。

最后，我將獲得這些示例變體，所有這些都可以評(píng)估：

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

跳至：我對(duì)其進(jìn)行了編碼...并發(fā)現(xiàn)了一個(gè)更大的問(wèn)題

我編寫(xiě)的代碼成功生成了方程的所有變體。

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 用于沿著數(shù)字列表
• 僅當(dāng) i 位于倒數(shù)第二個(gè)索引之前或位于倒數(shù)第二個(gè)索引時(shí)，最后一個(gè)子句才會(huì)繼續(xù)

該函數(shù)獲取四個(gè)值：

1. 數(shù)字列表的副本，減去預(yù)期總數(shù)
2. 下一個(gè)索引
3. 由三個(gè)字符串之一連接而成的方程字符串
4. 相同的測(cè)試號(hào)碼

我使用與第 1 部分幾乎相同的簽名來(lái)調(diào)用該函數(shù)：

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

區(qū)別在于我作為參數(shù)傳遞的內(nèi)容：

1. 沒(méi)有預(yù)期總金額的清單
2. 從索引 0 開(kāi)始
3. 包含第一個(gè)數(shù)字的字符串
4. 預(yù)計(jì)總金額

好消息：

• 它生成所有方程變化

壞消息：

• 它使用 PEMDAS 計(jì)算所有方程，而不是從左到右

我應(yīng)該更清楚...內(nèi)置的 JavaScript 求值器會(huì)默認(rèn)使用正確的操作順序，而不是從左到右。

這確實(shí)給我的算法帶來(lái)了更大的麻煩：

• 我將不得不分解每個(gè)方程并逐個(gè)部分地評(píng)估它

嗚嗚嗚。

謝天謝地，我想我知道該怎么做。

手動(dòng)做數(shù)學(xué)

我需要 JavaScript 來(lái)計(jì)算這樣的方程：

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 

我想將該方程分成幾個(gè)部分：

""

我了解的唯一方法是使用這個(gè)三鏈表達(dá)式：

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

我用空格填充每個(gè)運(yùn)算符，只是將其用作分隔符。

關(guān)于這個(gè)方程部分列表的事實(shí)：

• 它將始終包含 3 個(gè)或更多的奇數(shù)項(xiàng)目

如何在迭代每個(gè)操作數(shù)-運(yùn)算符-操作數(shù)對(duì)的循環(huán)中利用這一事實(shí)？

這是我的想法：

• 刪除前三項(xiàng)
• 將它們作為字符串連接，并將其作為數(shù)學(xué)表達(dá)式進(jìn)行計(jì)算
• 將結(jié)果重新附加到方程列表的開(kāi)頭
• 重復(fù)直到方程式列表為空

希望它能起作用！

我在 JavaScript 中工作的數(shù)學(xué)模擬器：

"N"

好消息：

• 它向我顯示了預(yù)期的計(jì)算值

壞消息：

• 我仍然沒(méi)有得到示例輸入中一個(gè)方程的正確答案

示例答案不會(huì)錯(cuò)...可以嗎？

我不斷生成的答案比預(yù)期答案少了大約 7k。

這讓我認(rèn)為我的算法沒(méi)有識(shí)別出這個(gè)方程是正確的：

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)
  }
}

我的算法評(píng)估該方程并生成以下結(jié)果：

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

那是因?yàn)槲业乃惴ㄊ沁@樣運(yùn)行的：

292: 11 6 16 20

我不明白它怎么可能是其他數(shù)字。

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

我找到了我的答案，它一如既往地隱藏在簡(jiǎn)單的網(wǎng)站解釋中：

所有運(yùn)算符仍然從左到右計(jì)算。

我在每個(gè)遞歸函數(shù)調(diào)用中預(yù)先連接值。

相反，我的算法應(yīng)該這樣做：

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 

現(xiàn)在我明白了應(yīng)該發(fā)生什么，我可以調(diào)整我的算法以匹配該處理行為嗎？

從左到右......這次是真的

值得慶幸的是，調(diào)整我的算法相對(duì)容易。

我添加了一個(gè)replaceAll()子句來(lái)解釋||。

我處理每三個(gè)項(xiàng)目的新 while 循環(huán)如下所示：

""

我調(diào)整了退貨聲明的||子句包含這些字符，而不是立即連接兩個(gè)數(shù)字。

測(cè)試和重新測(cè)試

我在示例輸入上運(yùn)行了算法。

它終于生成了正確的答案??！

多么輕松?。?！

我想知道它是否會(huì)完成運(yùn)行并在我的拼圖輸入上生成正確的答案。

按運(yùn)行...

...

...

我得到答案了！

它很大，所以這可能是一個(gè)好兆頭。

這是正確答案嗎？

...

不。太高了。

真糟糕。

我錯(cuò)過(guò)了一個(gè)邊緣案例嗎？

我的獲勝方程的條件很簡(jiǎn)單，就是處理后的數(shù)學(xué)等于測(cè)試量。

但是，如果其中一個(gè)變體方程允許數(shù)字子集生成正確答案怎么辦？

為了捕獲并排除這種情況，我更新了 if 條件以包含另一個(gè)子句：

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

這樣，只有當(dāng)所有數(shù)字都處理完畢并且結(jié)果數(shù)量等于測(cè)試數(shù)時(shí)，方程才會(huì)被計(jì)算在內(nèi)。

大問(wèn)題：

• 這會(huì)改變我得到的答案嗎？

再次按下運(yùn)行...

...

嗯，看起來(lái)確實(shí)還是一樣的答案。

哦，等等，末尾附近有兩個(gè)數(shù)字不同！

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

是否有一個(gè)以 80 為預(yù)期數(shù)量的方程式？

是的！

"N"

有沒(méi)有一種方法可以在不使用所有數(shù)字的情況下得到 80？

是的！

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

這是我需要排除的唯一邊緣情況嗎？

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

正確?。?！

嗚呼?。?！

我做到了！?。?/p>

那個(gè)。曾是。筋疲力盡。令人興奮。并且真的跑了。并且具有挑戰(zhàn)性。

以及我喜歡做這些謎題的所有原因。

繼續(xù)下一篇！

以上是橋梁修復(fù)的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！