コード 2024 の出現(xiàn) 7 日目

パート 1

今年最初の再帰

今日は少なくともそうしてゴールドスターを 1 つ獲得するつもりです:

• 完全なリストから始めます
• 足し算と掛け算の両方をチェックしてください
• 各結(jié)果について、リストの殘りの部分に進(jìn)みます
• 合計(jì)を超えるか一致するまで

難しいのは細(xì)部にあります。

これをやってみよう!

アルゴリズムを作成する

まず、各行を數(shù)値のリストに解析する必要があります。

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

最初の要素は必要な合計(jì)です。

殘りは方程式の順序付けされたオペランドです。

再帰関數(shù)でこれを考慮する必要があります。

これが私の再帰関數(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)

期待していましたが、予想外でした。入力例に対する正しい答えが生成されます。

パズル入力の処理は完了しますか?

もしそうなら、正しい答えが生成されますか?

正直、よくわかりません...

本當(dāng)にできました!!!

うわー!!!

私はとても興奮していますが、次の部分ではさらに演算子が追加されるか、再帰が実行可能な解決策ではなくなるために高度な CS が必要になるのではないかと心配しています。

パート 2

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

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

...

數(shù)日後...

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

• 返品條件に 3 番目の條項(xiàng)を追加するのと同じくらい簡(jiǎn)単ですか? いいえ
• パート 1 の再帰関數(shù)は成功するように正しく構(gòu)成されていますか? いいえ
• ああ、いや、以前の操作の結(jié)果として金額を蓄積することは可能でしょうか? いいえ
• 本當(dāng)に新しい戦略でこれに取り組む必要があるのでしょうか? そうだね

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

この方程式の場(chǎng)合:

292: 11 6 16 20

これらは、3 つの演算子が與えられた場(chǎ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 

おそらく、各方程式の文字列を構(gòu)築し、それを再帰関數(shù)內(nèi)で手動(dòng)で評(píng)価できます。

例:
一番外側(cè)の関數(shù)呼び出しでは空の文字列から始めます:

""

そこから、次の番號(hào)を使用して 3 つのバリエーションを作成します。

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

うーん、でもこれは最初の番號(hào)では機(jī)能しません。

最初の関數(shù)呼び出しを空の文字列ではなく、最初の數(shù)値で開始する必要があります:

"N"

そこから同じこと:

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

ああ、それはうまくいくはずです。

最後までに、これらのサンプル バリエーションが完成し、すべて評(píng)価可能になります:

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

• 私は數(shù)字のリストをたどるのに慣れています
• 最後の節(jié)は、i が最後から 2 番目のインデックスの前またはインデックスにある場(chǎng)合にのみ続行されます

関數(shù)は 4 つの値を取得します:

1. 數(shù)値リストのコピーから、予想される合計(jì)を差し引いたもの
2. 次のインデックス
3. 3 つの文字列のいずれかを連結(jié)した方程式文字列
4. 同じテスト番號(hào)

パート 1 とほぼ同じシグネチャを使用して関數(shù)を呼び出します。

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

違いは、引數(shù)として渡すものです:

1. 合計(jì)予定額を除いたリスト
2. インデックス 0 から開始
3. 最初の數(shù)字を含む文字列
4. 予定総額

素晴らしいニュース:

• すべての方程式のバリエーションを生成します

悪いニュース:

• 左から右ではなく、PEMDAS を使用してすべての方程式を評(píng)価します

組み込みの JavaScript エバリュエーターはデフォルトで左から右ではなく正しい操作順序を使用することをもっとよく知っておくべきでした。

これは実際に私のアルゴリズムにさらに大きな問題を投げかけます:

• 各方程式を分解して部分ごとに評(píng)価する必要があります

うわー。

ありがたいことに、その方法を知っているようです。

手動(dòng)で計(jì)算する

次のような方程式を評(píng)価するには 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"

區(qū)切り文字として使用するためだけに、各演算子に空白を埋め込みます。

この方程式部分のリストに関する事実:

• 常に 3 つ以上の奇數(shù)のアイテムが含まれます

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

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

• 最初の 3 つの項(xiàng)目を削除
• それらを文字列として結(jié)合し、それを數(shù)式として評(píng)価します
• 結(jié)果を方程式リストの先頭に再添付します
• 方程式リストが空になるまで繰り返します

うまくいくことを願(yuàn)っています!

JavaScript で作成した數(shù)學(xué)シミュレータ:

"N"

素晴らしいニュース:

• 期待される計(jì)算値が表示されます

悪いニュース:

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

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

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

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

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)

それは、私のアルゴリズムが次のように実行されるためです:

292: 11 6 16 20

これが他の數(shù)字になる可能性がわかりません。

それで...Google で調(diào)べてみました。

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

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

各再帰関數(shù)呼び出しで値を事前に連結(jié)していました。

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

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 

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

左から右へ…今度は本當(dāng)に

ありがたいことに、アルゴリズムの調(diào)整は比較的簡(jiǎn)単でした。

|| を考慮して replaceAll() 句を追加しました。

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

""

そして、return ステートメントの || を調(diào)整しました。 2 つの數(shù)値を即座に連結(jié)する代わりに、これらの文字を含める句。

テストと再テスト

入力例でアルゴリズムを?qū)g行しました。

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

本當(dāng)に安心しました!!

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

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

...

...

答えが出ました!

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

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

...

いいえ。高すぎます。

殘念です。

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

私が勝利の方程式を得る條件は、単純に、処理された數(shù)學(xué)がテスト量と等しいということです。

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

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

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

この方法では、すべての數(shù)値が処理され、結(jié)果の量がテスト數(shù)値と等しい場(chǎng)合にのみ、方程式がカウントされます。

大きな質(zhì)問:

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

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

...

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

ああ、ちょっと待って、最後の近くに 2 つの數(shù)字が違います!

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

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

はい!

"N"

すべての數(shù)字を使わずに 80 を作る方法はありますか?

はい!

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

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

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

正解です!!!

うおおお!!!

やったよ!!!

あれ。だった。疲れる。そして爽快です。そして本當(dāng)に走ります。そして挑戦的です。

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

次へ!

以上が橋の修理の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。