橋の修理

コード 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 つの演算子が与えられた場合に考えられるすべての方程式です。

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 

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

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

""

そこから、次の番号を使用して 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 つの値を取得します:

1. 数値リストのコピーから、予想される合計を差し引いたもの
2. 次のインデックス
3. 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 つ以上の奇数のアイテムが含まれます

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

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

• 最初の 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 で調べてみました。

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

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

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

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

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() 句を追加しました。

3 つの項目ごとに処理する新しい while ループは次のようになります。

""

そして、return ステートメントの || を調整しました。 2 つの数値を即座に連結する代わりに、これらの文字を含める句。

テストと再テスト

入力例でアルゴリズムを実行しました。

それは ついに正しい答えを生成しました!!

本当に安心しました!!

実行が完了して、パズルの入力に対して正しい答えが生成されるかどうか疑問です。

実行を押しています...

...

...

答えが出ました!

それは大きいので、おそらく良い兆候です。

それは正しい答えですか?

...

いいえ。高すぎます。

残念です。

エッジケースを見逃しているのでしょうか?

私が勝利の方程式を得る条件は、単純に、処理された数学がテスト量と等しいということです。

しかし、変形方程式の 1 つで数値のサブセットが正しい答えを生成できる場合はどうなるでしょうか?

このシナリオを捕らえて除外するために、if 条件を更新してもう 1 つの句を含めました。

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

この方法では、すべての数値が処理され、結果の量がテスト数値と等しい場合にのみ、方程式がカウントされます。

大きな質問:

• これによって得られる答えは変わりますか?

もう一度実行を押します...

...

うーん、確かにまだ同じ答えのようですね。

ああ、ちょっと待って、最後の近くに 2 つの数字が違います!

私の新しい答えは、以前よりちょうど 80 少ないものです。

期待値が 80 になる方程式はありますか?

はい!

"N"

すべての数字を使わずに 80 を作る方法はありますか?

はい!

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

これは除外する必要がある唯一のエッジケースでしたか?

新しい回答を送信中...

正解です!!!

うおおお!!!

やったよ!!!

あれ。だった。疲れる。そして爽快です。そして本当に走ります。そして挑戦的です。

私がこれらのパズルをするのが好きな理由はすべてです。

次へ!

以上が橋の修理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。