🎅

Advent of Code 2024 Day 18: RAM Run

2025/01/22に公開

このページは

2024 年の Advent of Code の Day18 の記事です。

https://adventofcode.com/2024/day/18

Day17 の内容はこちら。

https://zenn.dev/yasuharu519/articles/6bc95f52efc503

Day 18: RAM Run

今度の舞台はコンピュータ内部のメモリ空間です。このメモリ空間は二次元座標で表されており、座標は縦横共に 0 から 70 までの値をとるように広がっています。

バイト位置はそれぞれ X, Y で表現されており、 X は左端からの距離、Y は上端からの距離を表しています。

今はメモリ空間の上端 (0, 0) の座標におり、右下隅の (70, 70) に到達する必要があります。

落ちてくるバイトの座標の一覧が X, Y の座標リストとして与えられます。バイトが落ちてきた座標は破損しており、その位置に移動することはできません。

Part1

Part1 では、 1kb (1024 バイト) のメモリが座標に落ちてきたと考え、左上隅から右下隅まで移動するために必要なステップ数を求めるといった問題です。

これは二次元マップの上で、落ちてきたバイトを障害物と考えたときに、左上隅から右下隅までの最短路を求めれば良さそうです。

BFS などを使って最短路を求めるのが良いでしょう。
https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day18/part1.py#L33-L49

最短路の結果はこのような感じになります。

Part2

Part1 では 最初の 1024 バイト分のメモリしか利用しませんでした。Part2 では、すべてのバイトを利用すると、最終的にどこかで 左上隅 (0, 0) から右下隅 (70, 70) までの経路が塞がれてしまうようです。

今回の Part2 の問題は 左上隅から右下隅までの経路がどのタイミングで防がれてしまうか? を探す問題です。

まずは計算量について考えてみましょう。

BFS の場合、頂点数 V、エッジ数 E のグラフ G(V, E) に対して、計算量は O(V + E) のようです。

今回は 71x71 の二次元マップのため、

  • V = 71 \times 71 = 5041
  • E = 5041 \times 4 = 20164

となり、約 2 \times 10^4 ほどとなります。

インプットとなるバイトの座標リストは 3,450 件あり、すべて愚直に計算したとすると約 6 \times 10^7 程度の計算量になることがわかります。 10^7 程度の計算量であれば愚直に計算しても計算できそうです。 今回は愚直な方法をとりましたが、もっと効率的な方法はありそうな気がします。

Part1 で使用した関数を利用し、今回はコストではなく経路があるかを確認する関数にしました。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day18/part2.py#L7-L24

順にバイトを落としていき、その都度経路が塞がれているかを確認して行くようにしました。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day18/part2.py#L31-L40

Day19 に続きます。

https://zenn.dev/yasuharu519/articles/38ffc7cd98ccd3

Discussion