Code Day の到来 キーパッドの難題

21日目: キーパッドの難題

GitHub リポジトリ - ソリューション

今日の課題は難しく、ロジックを完全に理解するだけでなく、解決するのに 2 日かかりました。今年気づいたことは、指示の意図を理解するのに苦労したということです。

私と同じように、あなたもこの課題と解決策から何かを学んでいただければ幸いです。 Advent of Code に毎年参加すると、たくさんのことを学べます。そのため、さまざまな言語を試したり、自分自身を快適ゾーンから押し出したりするのが好きなのです。私は Advent of Code を単なる競争として扱うのではなく、開発者が知識やアイデアを共有する学習/開発の機会として考えています。

今日も Python を試してみましたが、その解決策には満足しています。今日私が学んだことは次のとおりです。クラス宣言で @dataclass(frozen=True) アノテーションを使用する不変クラス。

私は、座標をナビゲートして更新するためのヘルパー クラスとして Location クラスを作成しました (これは、一部の C# ソリューションで Point クラスを使用して以前に行ったのと少し似ています。

C# / .Net の厳密に型指定されたバックグラウンドを持っている私は、この複雑な問題の際に何を扱っていたのかを視覚化できるように、コードに型を追加してみました。私も TypeScript を書いているときにこれを行うことに慣れているので、ほとんど習慣になっています。

今日の問題

**パート 1 **では、複数のロボットをナビゲートおよび制御して、次のロボットに指示を渡し、テンキーでコードを入力するという問題を紹介します。

パート 2 では、一連のロボットと方向キーパッドによって複雑さを増すことで問題を解決し、マルチレベルの依存関係の指数関数的な性質を示します。

ウォークスルー

道順とキーパッドのレイアウトはすでにわかっているので、すべての位置マッピングとそれらが移動できる方向の辞書を構築できます。

キャッシュ (cache および move_cache)

cache: 以前に計算された最短シーケンスを保存して、冗長な計算を回避し、パフォーマンスを向上させます。

moves_cache: キーパッド上の任意の 2 つのボタン間の有効な移動シーケンスをすべて保存し、素早い検索のために事前に計算されます。

最短長の計算 (shortest_length)

指定されたコードを入力するためにボタンを押す最短のシーケンスを再帰的に計算します。

レベル (cur_ Depth) を限界 ( Depth_limit ) まで反復処理することにより、キーパッドのマルチレベル チェーンを処理します。

*ポジション間の移動 (moves_between_positions)
*

キーパッド上の 2 つのボタン間のすべての有効な一連の動きを計算し、ロボットが無効な位置 (ギャップ) を指して パニックにならないようにします。

キャッシュの初期化 (create_cache_moves)

テンキーと方向キーパッドの両方のすべてのボタン ペアに対して有効な移動シーケンスを事前計算し、実行時の計算を節約します。

解決関数は、シーケンスの長さにコードの数値部分を乗算して複雑さを計算する入力をループし、パズルの要件に従ってすべてのコードの複雑さを単純に合計します。

順列

順列は何をしますか?

Python の順列関数 (itertools モジュールから) は、項目のコレクションの考えられるすべての順序付けされた配置を生成します。

例:

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

これにより次のものが生成されます:

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

各順列は、元のコレクション内のすべてのアイテムを含む一意のシーケンスですが、順序は異なります。

なぜ組み合わせではなく順列を使用するのでしょうか?

順列:

アイテムのコレクションの可能な順序付けされた配置をすべて生成します。
項目の順序は重要です。

一方、
組み合わせ:

項目のコレクションの可能な順序なしの選択をすべて生成します。

項目の順序は関係ありません。

このシナリオではなぜ順序が重要なのでしょうか?

キーパッド ナビゲーション: 各動作の後にキーパッド上のロボットの位置が変化するため、動作が実行される順序が結果に直接影響します。

Valid Moves Check: この関数は、ナビゲーション中の中間位置の有効性をチェックします。移動の順序を変更すると、無効なパスが発生する可能性があります。

代わりに組み合わせが役立つのはどのような場合ですか?

組み合わせは、動きの順序が重要ではない場合、または順序を気にせずに動きやボタンのサブセットを選択しているシナリオで役立つ可能性があります。

キーパッドのナビゲーションでは移動の順序が重要であるため、現在の順列の使用が必要です。これを組み合わせに置き換えると、プログラムのロジックが壊れてしまいます。順序に関係なく、動きやキーの一意のグループをすべて見つける必要があるタスクの場合は、組み合わせの方が適切です。

パズルの最も困難な部分は、ロボット命令の深さ (開始) レベルを追跡するための適切でクリーンな方法を考えることでした。これに完全に注意を向けられるまでに少し時間がかかりました。

以上がCode Day の到来 キーパッドの難題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。