Zenn
🎅

Advent of Code 2024 Day 15: Warehouse Woes

2025/01/02に公開
Python
adventofcode
tech

このページは

2024 年の Advent of Code の Day15 の記事です。 Day14 はこちら。

https://zenn.dev/yasuharu519/articles/e3f21bd7a556e9

Day 15: Warehouse Woes

今回は チョウチンアンコウ(lanternfish)が管理する倉庫が舞台です。チョウチンアンコウは食料を保存する倉庫を持ち、その管理をロボットに任せていたのですが、ロボットが制御不能になってしまったようです。ロボットは倉庫内を移動し、倉庫内の食料の入った箱を乱暴に押し回しています。

チョウチンアンコウから、倉庫内の地図とロボットの位置、ロボットが上下左右に移動する動作リストが与えられます。

Part1

#########
#..O...O#
#..O@.#.#
#O#.....#
#########
  • @ がロボットの位置
  • O が箱の位置
  • # が壁

同時にロボットの移動リストが与えられます。

  • ^ は上に移動
  • v は下に移動
  • < は左に移動
  • > は右に移動

を表します。

ロボットが移動する際、移動先が . の空きマスであればそのまま移動しますが、 O の箱があった場合は箱と共に移動します。

#######
#..O@.#
#.O...#
#######

のときに < が与えられた場合ロボットは左方向に移動し

#######
#.O@..#
#.O...#
#######

となります。

複数の箱も同時に移動させることができますが、移動するときに箱の移動先がなければロボットは移動できません。

これはロボットの移動の際に、移動先のマスをチェックすれば良さそうです。

  • 移動先が空きマスの場合: ロボットを移動
  • 移動先が壁の場合: ロボットは移動できないため、今の位置のまま
  • 移動先が箱の場合: 箱の移動先をチェック
    • 箱の移動先が箱の場合: さらにその先の箱の移動先をチェック
    • 箱の移動先が空きマスの場合: ロボットと箱を移動
    • 箱の移動先が壁の場合: 移動できないため今の位置のまま

のように確認して、箱やロボットの位置のアップデートを行いました。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day15/part1.py#L30-L49

Part2

Part1 をクリアし、無事誤作動していたロボットの電源を切ることが出来ましたが、別の倉庫のロボットも故障していることがわかりました！

Part2 の倉庫では、ロボットの動作リストは同じなのですが、倉庫のレイアウトが少し異なります。Part1 のレイアウトと似ているのですが、各アイテムの幅が二倍になっています。

  • # は ## に
  • . は .. に
  • O は [] に
  • @ は @. に

なります。そのため、

#########
#..O...O#
#..O@.#.#
#O#.....#
#########

というレイアウトは

##################
##....[]......[]##
##....[]@...##..##
##[]##..........##
##################

というように幅が二倍のレイアウトになります。ただし、移動する際の移動距離は 1 マスずつ移動するため

##############
##....[]@...##
##..[]......##
##############

のときに < が与えられた場合ロボットは左方向に移動し

##############
##...[]@....##
##..[]......##
##############

となります。

左右移動の場合は Part1 と同じ考え方で問題なさそうですが、上下移動の場合、箱のサイズが 2 倍になったことで

[].
.[]

のように、上下で箱が半分ずつ重なるケースが発生します。そのため、主に上下移動の場合を考えます

  • 上下移動で箱の移動も伴う場合、箱が移動可能かのチェック
  • 箱の移動が伴う場合の、箱とロボットのレイアウトのアップデート

と分けて考え、処理するようにしました。

箱が移動可能かどうかのチェック

ロボットが上下に移動する際、移動先に箱がある場合はその箱が移動できるかをチェックします。その先も箱の場合は、その先の箱もチェックします。最終的に移動対象となる箱をすべて移動することができるかどうか、を確認することで、連鎖的に移動する箱のすべてを移動させられるかチェックするようにしました。

実装上は再帰的にチェックしていき、該当するすべての箱が移動できるかどうかチェックをしました。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day15/part2.py#L27-L57

箱を移動させる場合のレイアウトアップデート

箱がすべて移動可能かチェックした後は、移動後のレイアウトにアップデートする必要があります。これについては、移動対象となる箱を抽出した後、奥から順にレイアウトのアップデートを行うことで対応が可能です。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day15/part2.py#L146-L158

倉庫番のロボットと箱の動きを可視化すると以下のようになります。ルール通り箱の移動は出来てそうで、ロボットが箱を押して回っている動きもかわいいですね。

実装を試すときには、与えられた入力ではなく、自分でロボットに指示を出して動かせるようにして、箱をルール通り動かせているか見ることで実装のチェックを行いました。

asciicast

Day 16 に続きます。

Discussion