Advent of Code 2024 5: Print Queue
このページは
2024 年の Advent of Code の Day5 の記事です。 Day4 はこちら。
尚、これまでは Rust と Python の両方のコードを載せていましたが、間に合わないので Python のコードのみ載せています。気が向いたら Rust のコードも載せるかもしれません。
Day 5: Print Queue
1|10
11|20
のように X|Y で与えられる入力と、
75,47,61,53,29
というように長さが奇数のカンマで区切られた数列の二種類が与えられます。
Part1
1|10
11|20
といった | で区切られた数字のペアは、それぞれ依存関係を表しているようです。
数列の中でそれぞれのペアがあるときは、 | で区切られた順序に従っている必要があるようです。
数列に表れる数値がすべてその依存関係に従っているかを確認し、従っている場合には数列の中央の数値を足し合わせていくという問題です。
| で区切られた数字のペアは大量にあり、数列を見る度にすべての数字のペアをチェックすることは無駄となってしまいます。
数字のペアの前の文字を見たときに、その数字に依存する数字は何か、後の文字を見たときに、その数字が依存している数字は何かを見れるように defaultdict を使って依存関係を保存しておきます。
数列の中の各数字をチェックし、その数字に依存している数字、その数字が依存している数字を取り出し、それぞれの数字が数列の中に含まれているかチェックします。
数列の中に含まれている場合は、 index の前後関係が正しいかをチェックすれば良さそうです。
Part2
Part2 では、 Part1 の条件に合わなかった数列が対象になります。
条件に合わなかった数列を、条件に合うようにソートし、ソート後の数列の中央の数値を足し合わせていくという問題です。
こういった依存関係を表すものをソートする場合、トポロジカルソートが使えそうですね。
実装面倒だなと思っていたところ、Python には TopologicalSorter が graphlib にあるのでこちらが使えそうです。
実装は以下のように。
Day 6 に続く。
Discussion