Advent of Code 2024 Day 20: Race Condition
このページは
2024 年の Advent of Code の Day20 の記事です。
Day19 の内容はこちら。
Day 20: Race Condition
今回は CPU が舞台のようです。近くに居た "プログラム" が "レース" を仕掛けてきました。どうやら "Race condition" フェスティバルが開催されるタイミングだったようです。(競合状態の Race condition とかけてるのかな)
プログラム達はできるだけ短いピコ秒でゴールすることを競い合います。勝者には自分専用の Mutex が与えられるようです。 (ロックをとれるということでしょうか)
レースの地図が与えられます。地図は以下のようなもので、 # が壁、. がコース、 S がスタート地点、 G がゴール地点を表します。
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
移動には 1 ピコ秒かかります。
Part1
同じマップの場合、同じスピードで進むとどれも同時にゴールしてしまい、とてもつまらない競技になってしまうため、新しい競技ルールとして "チート可能" というものが付け加えられました。
このルールでは、 2 ピコ秒の間、壁をすり抜ける ことができるようになります。その後はコースに戻る必要があるため、実際は一つだけ壁を無効化することができます。ルールを違反咲いた場合は segmentation fault が発生するようです。 (実際のプログラムみたいですね)
また、チートは一度だけ使うことが出来るようです。
さて、この "チート" が可能になった場合、どこでチート機能を使うかによって、ゴールまでの最短路が変わってきます。
Part1 では チートを使うことで 100 ピコ秒以上短縮できるパターンはいくつあるか を求めよという問題です。
- チートを使うことで何ピコ秒短縮できるか
- 100 ピコ秒以上短縮できるパターンの数え上げ
というように分解して考えてみました。
何ピコ秒短縮できるか、について毎回最短路を求めてしまうと計算量が大きくなりすぎるため、各コースそれぞれで、スタートからの最短距離 と ゴールからの最短距離 を求めておき、チートを使う場所を変えた場合の最短距離を求めることで、何ピコ秒短縮できるかを求めました。
例えば以下のようなマップがあったとします。
######
#S...#
####.#
##E..#
######
このような場合、スタートからの最短距離とゴールからの最短距離を求めると以下のようになります
######
#S123#
####4#
##E65#
######
######
#S654#
####3#
##E12#
######
こうすると、各マスごとにスタートからの最短距離とゴールまでの最短距離がわかった状態になります。
あとは、チートを行ったときに
- チートを行うマスまでのスタートからの最短距離
- チートを行う際の移動距離 (2 ピコ秒)
- チートを行った後のマスからのゴールまでの最短距離
を求めることで、チートを行った場合の最短距離を求めることができます。何秒短縮できたかについては、チートを行うマス (
実際の実装では
のようにして、スタートからの最短距離とゴールからの最短距離を求めておき、
のようにして、チートを行った際に閾値以上のショートカットが出来ているかをチェックするようにしました。
Part2
Part1 では 2 ピコ秒までのチートが許されていましたが、Part2 では 20 ピコ秒までのチートが許可されるようになりました。20 ピコ秒を使い切る必要はないものの、20 ピコ以下を使ったとしても残りを再度使うことは出来ないようです。また、チート開始から終了までのマスが同じチート経路は 1 つとしてカウントします。
この場合に 100 ピコ秒以上短縮できるパターンはいくつあるか を求める問題です。
こちらも基本的には Part1 と同様に考えました。まず各マスについて、スタートからの最短距離と、ゴールからの最短距離を求めておきます。
Part2 では、20 ピコ秒まで利用できるので、各マスにおいて 今のマスからチートするとして、20 ピコ秒以内で到達出来るマスを探索し、100 ピコ秒以上短縮できるか をチェックするようにしました。
のようにして、あるマスからチートを開始するとして、20 ピコ秒以内で到達出来る且つ 100 ピコ秒以上短縮できるか探索するようにしました。
各マスごとに数え上げるようにしましたが、もっと効率的な方法があるかもしれません。
Day 21 に続きます。
Discussion