橋樑修復-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

登入後複製

我不明白它怎麼可能是其他數字。

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

我找到了我的答案，它一如既往地隱藏在簡單的網站解釋中：

所有運算子仍然從左到右計算。

我在每個遞歸函數呼叫中預先連接值。

相反，我的演算法應該要這樣做：

登入後複製

現在我明白了應該發生什麼，我可以調整我的演算法以匹配該處理行為嗎？