Advent of Code 2024 Day 18: RAM Run
このページは
2024 年の Advent of Code の Day18 の記事です。
Day17 の内容はこちら。
Day 18: RAM Run
今度の舞台はコンピュータ内部のメモリ空間です。このメモリ空間は二次元座標で表されており、座標は縦横共に 0 から 70 までの値をとるように広がっています。
バイト位置はそれぞれ X, Y で表現されており、 X は左端からの距離、Y は上端からの距離を表しています。
今はメモリ空間の上端 (0, 0) の座標におり、右下隅の (70, 70) に到達する必要があります。
落ちてくるバイトの座標の一覧が X, Y の座標リストとして与えられます。バイトが落ちてきた座標は破損しており、その位置に移動することはできません。
Part1
Part1 では、 1kb (1024 バイト) のメモリが座標に落ちてきたと考え、左上隅から右下隅まで移動するために必要なステップ数を求めるといった問題です。
これは二次元マップの上で、落ちてきたバイトを障害物と考えたときに、左上隅から右下隅までの最短路を求めれば良さそうです。
BFS などを使って最短路を求めるのが良いでしょう。
最短路の結果はこのような感じになります。
Part2
Part1 では 最初の 1024 バイト分のメモリしか利用しませんでした。Part2 では、すべてのバイトを利用すると、最終的にどこかで 左上隅 (0, 0) から右下隅 (70, 70) までの経路が塞がれてしまうようです。
今回の Part2 の問題は 左上隅から右下隅までの経路がどのタイミングで防がれてしまうか? を探す問題です。
まずは計算量について考えてみましょう。
BFS の場合、頂点数
今回は 71x71 の二次元マップのため、
V = 71 \times 71 = 5041 E = 5041 \times 4 = 20164
となり、約
インプットとなるバイトの座標リストは 3,450 件あり、すべて愚直に計算したとすると約
Part1 で使用した関数を利用し、今回はコストではなく経路があるかを確認する関数にしました。
順にバイトを落としていき、その都度経路が塞がれているかを確認して行くようにしました。
Day19 に続きます。
Discussion