Advent of Code 2024 Day 16: Reindeer Maze
このページは
2024 年の Advent of Code の Day16 の記事です。
Day15 の内容はこちら。
Day 16: Reindeer Maze
さて今回はトナカイオリンピックの時間です! トナカイたちが一番少ないポイントで迷路を抜けるという競技を行っているようです。
#######
#....E#
#.#.#.#
#.#.#.#
#S....#
#######
のような迷路のマップが与えられます。 S がスタート地点、E がゴール地点です。トナカイは最初東を向いており、 # で表される壁へは移動できません。向いている方向に 1 マス進むと 1 ポイント増えます。時計回りもしくは反時計回りに 90 度回転することもできますが、その場合は 1000 ポイント増えることになります。
Part1
Part1 では、スタート地点からゴール地点まで到達する場合の最小ポイントについて求める問題です。ダイクストラ法 や A* などの最短路探索アルゴリズムを使うことで解くことが出来そうです。
今回は現在向いている向きも考慮する必要があるため、途中の最短スコアを保存する際には向いている方向の情報も併せて保存しておくことにしましょう。
のように、位置と共に向いている 4 方向も含めてスコアを保存するようにしました。
簡単にダイクストラで解く場合は、Python の場合は heapq を使って最小ヒープを作成してチェックして行くのが良いでしょう。
Part2
Part2 では、最短スコアを出す経路であるマスに椅子を置くことができ、いくつ椅子を置くことができるかを求める問題です。つまり、最短パスに含まれるマスがいくつあるかを求める問題です。
今回は最短路を求めるだけではなく、最短路となるすべての経路を求める必要があります。さてどうしましょうか。
Part 1 では、以下のようにゴール地点に到達した時点で結果を出力して終了していました。
Part2 では、最短路と同じポイントになる経路をすべて記録し、最短路に含まれるマスをすべて数え上げれば良さそうです。
Day 17 に続きます。
Discussion