コードの出現、12～15日目

今週開始されるパズルは期待を裏切りません! 2 つの異なる経路探索演習と興味深い文字列挿入問題が含まれていました.

最初の経路探索パズルはかなりトリッキーでした.大きな「洞窟」と小さな「洞窟」の間の一連の関係が与えられた場合、目標は、最初から最後まで、小さな洞窟に 1 回だけ入る道の数を数え、小さな洞窟の 1 つに 2 回入ることが許可されたときの道も数えることでした. .

Sample set of relationships:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

私の戦略は、各キーが洞窟の名前 ('A'、'c'、'end' など) であり、関連付けられた値がその洞窟からの可能な出口のリストである辞書を作成することでした.私はたどられている経路を追跡し、洞窟に入った後、有効な出口を見つけるために出口のリストを再帰的に繰り返しました.有効な出口が見つかった場合、その洞窟は「入り」、出口のリストが評価されます.これは、特に有効な出口を構成するものに関して、把握するのが難しいパターンでした.

My day 12 code on GitHub

もう 1 つの経路探索演習 (15 日目) では、最短経路探索のためのダイクストラのアルゴリズムを紹介しました.整数値のグリッドが与えられた場合、目標は、左上隅 (開始) と右下隅 (終了) の間で上下左右に移動する値の最小合計を見つけることでした.

最初はどうやってパズルを解けばいいのか分からなかった.ブレーンストーミングの後、私は Google を利用することに決め、すぐに多くの可能性のあるアルゴリズムの候補を発見しました.いくつか読んだ後、ダイクストラのアルゴリズムが私の最善の策である可能性が高いことが明らかになりました.

次に検索したのは、このアルゴリズムの手順を明確に説明することでした.疑似コードを見たくありませんでした.むしろ、アルゴリズムがどのように機能するかを説明したかったので、自分でコーディングしてみることができました.各ステップを説明するいくつかの画像を含む素晴らしい記事を見つけました.これに基づいて実装を行いました: Implementing Dijkstra's Algorith in Python .この記事はアルゴリズムのコーディングに続きますが、私は途中で読むのをやめ、コーディングを行うために PyCharm に向かいました.

ノード (グリッド上の位置) ごとに追跡したいアトリビュートの数が多かったため、小さなクラスを作成し、ノードごとにオブジェクトを作成しました.その後、ノードが訪問されたかどうか、その値と座標、およびそのノードと開始点の間の最短 (最低) パスの合計を簡単に追跡できました.

アルゴリズムの各ステップの開始時に、まだ訪れていない最小の距離値を持つノードを検索する必要があります. 100 x 100 グリッドの場合、これは些細なことでしたが、パズルの 2 番目の部分でグリッドが 500 x 500 に拡張されました.各ステップで全体を検索するにはノードが多すぎるため、すべてのアクティブ ノード (任意のノード) を追加することにしました.距離が評価されたがまだ訪問されていない) をリストに追加し、各ステップでそのリストのみを検索します.このリストは、処理中に 600 ～ 700 ノードに増加しましたが、250,000 ステップごとに 250,000 回の検索よりもはるかに優れています.

My day 15 code on GitHub