Advent of Code 2024 Day 21: Keypad Conundrum
このページは
2024 年の Advent of Code の Day21 の記事です。 Day20 はこちら。
Day 21: Keypad Conundrum
目の前にはドアがあり、そのドアを開けるには数字でできたキーパッドを操作する必要があります。しかしながら、そのキーパッドを直接操作することはできず、ロボットで操作するしかありません。ロボットの操作には <^v> などの方向キーをもつキーパッドでロボットアームを動かし、ボタンを押す指示をする必要があります。
このロボット操作のためのキーパッドが配置されている場所は高い放射線量が観測される場所のため人間が近づくことはできず、ロボットを送り込む必要があります。
さらにこのロボットを操作するためのキーパッドがおかれている場所は -40 度の極寒となっており、別のロボットを送り込む必要があります。
このようにロボットが別のロボットを操作し、最終的な数字のキーパッドの操作を行うといった設定になっています。
Part1
Part1 では、最終的に数字のキーパッドで入力したいコードが設定されるので、人間が操作するキーパッドで最小の入力を求めるといった問題です。
キーパッドの場所を移動するとき、複数の経路が考えられます。 それらの経路の長さは同じであったとしても、一つ前のキーパッドの操作やそのもう一つ前のキーパッドの操作では最短路が異なる可能性がありますし、その次の操作にも影響があります。
のように、キーパッドごとに与えられた入力に対してそれを実現するキー操作をすべて出力するようにしました。
その後、すべての経路を確認し、最終的に最短となる経路を算出するようにしました。答えは最終的なキーの長さを元にした複雑度として回答する必要があるので、計算して出力するようにしましょう。
Part2
Part2 では、 Part1 で2台しかいなかった中間のロボットが25台にまで増加します。かなり複雑なように感じますが、考え方は基本的に Part1 と似ています。
のようにして、ボタン間の移動でどういったパターンがあるかを事前に計測しておき、最短経路を事前に計算して記録しておきます。
重要なポイントとしては、 各ロボットは最初 A のボタンを指し示しており、次のロボットに指示を送るため最後に A のボタンを押す という点です。そのため一つのコマンドを送信する際には A のボタンからスタートし、最終的には A のボタンを押すため、一つ一つのロボットの途中の位置を記録する必要がありません。
与えられた入力値を最終的に入れるとすると、一つ前のロボットが入力する入力シーケンスを求め、その入力シー毛スを入力するための入力シーケンスを求め... と 25層繰り返すこととしたときの入力シーケンスの長さを求めるようにしました。
zip("A" + seq, seq) とすることで、"A" を頭に付けた文字列の前後の文字ペアを取得できて便利。
Day 22 に続きます。
Discussion