Advent of Code 2024 Day 1: Historian Hysteria
Advent of Code とは
Advent of Code では、 12 月の 1 日から 25 日まで毎日新しい問題が公開されます。
2015 年から毎年開催されていて、今年でもう 10 回目となるようです。記念すべきイヤーですね。
問題は毎日 2 つ公開され、一つ目の問題は比較的簡単な問題、二つ目の問題は基本的に同じ入力を使うものの、条件が変わり難易度が上がったものとなっています。そのため、別のアプローチを考える必要があります。
問題の解答としては、与えられた入力に対して、指示に従って作成した出力を提出すればよいものとなっています。そのため、言語の縛りや実行時間の縛りなどもなく自由に問題に取り組むことができるようになっています。
今回は普段書き慣れている Python でアルゴリズムを解きつつ、Rust など他の言語でどのように書けるのか試してみて、他の言語での書き方を学習していきたいと思います。
Day 1: Historian Hysteria
物語のスタートです。どうやら "Chief Historian" を探す旅のようですね。
3 4
4 3
2 5
1 3
3 9
3 3
のような左右二つに ID が並べられているので、左のリスト、右のリストを小さいものから順に比較し、差の絶対値の合計を求めよというのが最初のタスクのようです。
Part1
まずはそれぞれを左右に分けて別々のリストに入れた後、小さいもの順に比較していけば良さそうです。
"小さいものから" アクセスするためには、リストのソートや、ヒープキューなどの構造を使うとできそうです。
Python では、 heapq モジュールを使うとヒープキューを使用することができるので、それを使用しました。
Rust だと BinaryHeap を使用するとヒープキューを作成できそうです。ただし、Python の heapq は最小ヒープだった一方、 BinaryHeap では最大ヒープになる点に注意が必要そうです。 Python で最大ヒープを作成するときは符号を反転させるなどしましたが、 Rust では Reverse<T> を使うのはわかりやすくていいですね
Part2
Part1 の問題を解くと、Part2 の問題が現れます。次の問題は左の各 ID が右の ID リストに何回出てくるか数え、左の ID の値と右の ID リストの出現回数を掛け合わせ、その合計値を求めるというもの。
Python の場合は、defaultdict を使って数えるのが楽ですね。結果は足し合わせなので、右のリストの ID の出現回数を数えるのと同時に、左の ID の出現回数も数えておくと良さそうです。
Rust の場合は .entry() を使うことで、 Python の defaultdict のように、値が存在しない場合でも初期値を設定できます。
.entry() の API については以下サイトで詳しく解説されており、とても参考になりました。
以上、 Python と Rust で Day1 を解いてみました。Day 2 に続きます。他の言語でも試してみたい。
Day2 はこちら。
Discussion