深成子の小石

コード 2024 の到来、11 日目: 小石の増殖

パート 1: Pebble サイクルのマッピング

この問題には、一連の変換を通じて小石の進化を追跡することが含まれます。 25 回の反復をシミュレートする最初のアプローチは、パート 1 で実行可能であることが証明されました。しかし、小石の指数関数的な増加は、はるかに多くの反復が必要となるパート 2 では別の戦略が必要であることを示唆しています。 重要なのは、小石の変換ルールと、それが小石全体の数にどのような影響を与えるかを理解することです。

Pebble 変換ルール:

ルール 1: 値 0 の小石は、値 1 の小石に変わります。

ルール 2: 偶数の長さの番号が付けられた小石は、元の番号の長さの半分の 2 つの新しい小石に分割されます。

ルール 3: 奇数の長さの番号が付けられた小石の価値は 2024 倍になります。

実装とテスト:

blink() 関数は、次の変換ルールを実装します。

function blink(num) {
    let str = String(num);
    if (num === 0) {
        return 1;
    } else if (str.length % 2 === 0) {
        return [+(str.slice(0, str.length / 2)), +(str.slice(str.length / 2))];
    } else {
        return num * 2024;
    }
}

文字列スライスを数値に変換するための の使用に注意してください。 入力例を使用した初期テストにより、関数の精度が確認されました。 flatMap を使用した反復処理は、小石の分割を効率的に処理します。 このソリューションは、パズル入力に対して 25 回の反復を正常に処理し、正しい答えを生成しました。

パート 2: 指数関数的成長の克服

パート 2 では、小石の数が急速に増加しているため、計算上の大きな課題が生じます。 直接シミュレーションという私の最初のアプローチは、計算的に実行不可能であることが判明しました。わずか数十回の反復で、小石の数が爆発的に管理可能な限界を超えてしまいます。

最適化戦略の検討:

これに対処するために、私はいくつかの戦略を調査しました。

1. サイクル検出: 冗長な計算を回避するために、pebble 値の繰り返しパターンを検出する可能性を検討しました。 一部の数値では、生成された値のセットが限定的で有限であることが示されましたが、このパターンは普遍的に適用できるものではなく、このアプローチは不十分でした。

2. Pebble カタログ: Pebble の値とその後の変換のカタログを作成しようとしました。 目標は、事前に計算された結果を再利用してプロセスを高速化することでした。 カタログでは一部の小石の計算量が削減されましたが、全体的な改善はパート 2 の規模に対処できるほど大幅ではありませんでした。

ロードブロッキングとリフレクション:

これらの最適化手法を検討したにもかかわらず、パート 2 では小石の指数関数的な増加を効率的に処理する解決策を見つけることができませんでした。この問題の計算の複雑さと、簡単に識別できるパターンの欠如が相まって、次の制約内では克服できないことが判明しました。私の現在のアプローチ。 この課題は、潜在的に爆発的に増加する問題のアルゴリズムを設計する際に、計算の複雑さを考慮することの重要性を強調しました。 パート 1 は無事解決しましたが、パート 2 は未解決のままです。

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