橋の修理-jsチュートリアル-php.cn

Bridge Repair

コード 2024 の出現 7 日目

パート 1

今年最初の再帰

今日は少なくともそうしてゴールドスターを 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

全く予想外でした！そしてはるかに難しい

どうやってこれを行うのでしょうか?

...

数日後...

私の思考プロセスの要約:

返品条件に 3 番目の条項を追加するのと同じくらい簡単ですか? いいえ
パート 1 の再帰関数は成功するように正しく構成されていますか? いいえ
ああ、いや、以前の操作の結果として金額を蓄積することは可能でしょうか? いいえ
本当に新しい戦略でこれに取り組む必要があるのでしょうか? そうだね

すべての新しいバリエーションを考慮して

この方程式の場合:

292: 11 6 16 20

ログイン後にコピー

これらは、3 つの演算子が与えられた場合に考えられるすべての方程式です。

ログイン後にコピー

おそらく、各方程式の文字列を構築し、それを再帰関数内で手動で評価できます。

例:
一番外側の関数呼び出しでは空の文字列から始めます:

""

ログイン後にコピー

そこから、次の番号を使用して 3 つのバリエーションを作成します。

"" + "+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 が最後から 2 番目のインデックスの前またはインデックスにある場合にのみ続行されます

関数は 4 つの値を取得します:

数値リストのコピーから、予想される合計を差し引いたもの
次のインデックス
3 つの文字列のいずれかを連結した方程式文字列
同じテスト番号

パート 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 つ以上の奇数のアイテムが含まれます

各オペランド、演算子、オペランドのペアを反復するループでこの事実を利用するにはどうすればよいですか?

これが私のアイデアです:

最初の 3 つの項目を削除
それらを文字列として結合し、それを数式として評価します
結果を方程式リストの先頭に再添付します
方程式リストが空になるまで繰り返します

うまくいくことを願っています!

JavaScript で作成した数学シミュレータ:

"N"

ログイン後にコピー

素晴らしいニュース:

期待される計算値が表示されます

悪いニュース:

入力例の 1 つの方程式について、まだ正しい答えが得られません

回答例は間違っているはずがありません...そうですよね??

私が生成し続けている答えは、予想される答えより約 7,000 足りません。

そのため、私のアルゴリズムがこの方程式を正しいものとして識別していないと思われます:

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

ログイン後にコピー

これが他の数字になる可能性がわかりません。

それで...Google で調べてみました。

そして、いつものように、説明内のわかりやすいサイトに隠れていた自分の答えを見つけました。

すべての演算子は依然として左から右に評価されます。

各再帰関数呼び出しで値を事前に連結していました。

代わりに、私のアルゴリズムは次のようにする必要があります:

ログイン後にコピー

何が起こるかを理解したので、その処理動作に合わせてアルゴリズムを調整できますか?