Advent of Code 2024 Day 6: Guard Gallivant
このページは
2024 年の Advent of Code の Day6 の記事です。 Day5 はこちら。
Part1
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
このような . と # で出来た Map が与えられる。 ^ が警備員の場所と向きを表しているとしたときに、警備員がどのような動きをするかシミュレーションするという問題です。
# は障害物を表し、障害物にぶつかると、右に 90 度回転して進む向きを変えます。
どこかでこの Map の画面外にでることになるのですが、それまでに何マス通ることになるかを求める問題です。
これは、素直に警備員の動きを画面外にでるまでシミュレーションすれば良さそうです。
求めるのは歩数ではなく通ったマスの種類なので、通ったマスを set で管理するようにしました。
Part2
Part1 では、警備員が通る経路のシミュレーションを行いましたが、障害物を一つ追加して、画面外にでないように経路をループさせることを考えましょう。
同じ経路をループしているか? をどうやって判定するかがポイントになりそうですが、 通ったマス に加えて 通ったときの向き を記録しておき、既に同じマス・同じ向きで通ったことがある場合は、ループしていると判断して良さそうです。
通ったマスを二次元配列で管理し、向きをビットマスクで保存するようにしました。
当初は警備員の動きをシミュレーションしながら、 もし今右に回転するとループするかどうか を判定するようにしていましたが、うまくいかなかったため、結果的に候補をすべて出して候補ごとにループしているか判定するようにして答えを出しました。
警備員の動きをシミュレーションしながら、今右に回転するとループになるかどうか を判定すると同時に、障害物を置くマスを既に通っていいないかを確認すれば正しい答えが出そうな気がします。こちらはまだ未確認ですがまた試してみようと思います。
(追記)
一度障害物を置いてみて、結果的にループになるかどうかをチェックするコードに書き換えました。
Day 7 に続きます。
Discussion