Advent Of Code 2021 完答した

Advent Of Code 2021 に参加して、今年も毎日コード書ききりました。。。大変だった。。。

Advent Of Code 2021
Advent Of Code 2021

Advent Of Code とは

adventofcode.com

Advent Calendar 形式で一日ずつ問題が出てくるので、それを毎日ひたすら25日まで解かせるというやつです。去年もやったんですけど、ただただ大変で、後半は問題出てきたとしても気持ちが折れかけたりします。ただ解けると楽しいんで、やってしまうという中毒性のある遊びですね。

ちなみに去年のやつです。

yosuke-furukawa.hatenablog.com

今年こそは全問何も見ずにちゃんと自分で考えて解くぞと思ってたんですけど、 day23 で気持ちが折れてしまって、解答を見てしまいました。自分との勝負ではあるものの、年末くらいはゆっくりしたいっていう気持ちに勝てませんでした。。。

今回は Rust で参戦

去年は JS だったんですけど、 Rust 勉強するかーって言って一年間 Rust で LeetCode やったり、 exercism で勉強したんで、集大成として Rust で参戦しました。

github.com

まだまだ Rust っぽい書き方ができるようになったとは言えないんですが、普通にコードは書けるようになりました。もうちょい実用的な処理を書いてみたいですね。来年はなんかライブラリとかアプリとか作ってみようかな。

思い出に残っている問題

思い出に残った問題を上げるなら以下の通り。ネタバレがあるので、これから自分で解きたい人は見ないでください。

Day 4: Giant Squid

ビンゴゲームをイカと一緒に解くっていう問題。数字が記載されているので交互にビンゴを完成させていって、勝ったらスコアが加算されるので、総スコアを答えよ、という問題。意味不明なお題で面白かったです。イカゲームと掛けたのかなこれは。。。

Day 13: Transparent Origami

折り紙を一定の座標軸で折り曲げていって、最後に出てきた画像に書いてあるアルファベットを答えさせる問題。これまで見たこと無い感じの面白い問題でしたね。

Day 14: Extended Polymerization

拡張された重合反応？っていう日本語訳になるかもだけど、要は化学元素記号みたいなものが反応されることで別な記号に生まれ変わる、その記号が反応し合うことで最終的にどういう文字列になるかという問題。

バカ正直に最初解いてて、途中から短く解けるアイデアを使ったら一発で解けてよかった。

Day 15: Chiton

よくあるスタートからエンドまでの迷路を一番効率よく辿れるパスを当てるっていう問題。 A* みたいなアルゴリズムで解こうか迷ったけど、結局 BinaryHeap を使った優先度キューみたいなもので解いてしまった。

この辺りまでは楽しいんですよね。前半の15日目くらいまでは。。。（ずっと前半やってたい）。

Day 16: Packet Decoder

なんでかよくわからないけど、エルフが出てきてバイナリーで話し始めたという所から独自のバイナリをデコードさせるっていう問題。とにかく仕様が複雑で、パケットの中にもサブパケットと呼ばれる入れ子構造になったパケットをデコードさせるので、再帰呼び出しで解く必要があり、また複雑なことにいくつかパケットのタイプが分かれてて、特別な処理が必要なパケットもあったりします。最後に leading zero で zero 値埋めがされているところとかも現実っぽい感じになっていて、とにかく「めんどくさい」問題でした。後半戦にはいったな、っていうことを思わせる問題でしたね。

Day 19: Beacon Scanner

三次元座標上にあるビーコンがあり、センサーがそれを検知するんですが、センサーの向きは教えてもらえず、ビーコンが見つかった三次元座標は渡されるものの、どの向きで発見した座標なのかはわからない、という問題です。書いただけじゃ何言ってるかわからないですね。三次元座標の原点の向きがバラバラになっているところで、すべてのセンサーが発見したビーコンの数を当てよという問題。頭の中でずっと座標をぐるぐる回転させてて、それでも全くどういうパターンが有るのかは分からず、色々座標を書いてパターンを見つけ、、、というほんと大変な問題だった。。。

Day 22: Reactor Reboot

原子炉を再起動させるために特定のパターンでボタンを押さないといけないが、こちらも三次元平面上にあるボタンをオン・オフして最後にオンになっているボタンの数を数えるという問題。書いただけじゃよくわからない問題パート2ですね。問題自体はめちゃくちゃ大変というわけではないものの、アルゴリズム力が求められるような問題でした。

Day 23: Amphipod

ここで一回力が尽きます。 Day 23 も問題自体はシンプルです。いくつかの微生物がいて、そいつらがパズルのように動くので、動いたコストの最小値を求めよ、という問題です。パズルを解ければ OK なんですが、もう day 22 で一回力尽きてたので、やる気がどうしても起きず、一回答えを見た上で解きました。気が向いたら自分でも解いてみます。

Day 24: Arithmetic Logic Unit

僕一番好きなやつですね。 Arithmetic Logic Unit というアセンブリ言語のような言語があるので、仕様どおりに計算を進めた上で、 4 つの processing unit がどのような値になるかをシミュレートするやつです。入力から出力を出すのではなく、出力から入力を推測しろという問題なので、全パターンを試そうとすると 9 ^ 14 の入力パターンを試す必要があり、そのままやると終わらないです。

自分はキャッシュを使って簡単なやり方で解いてしまったのですが、終わった後に色々見たら、 アセンブリ言語の JIT を作った猛者がいたりと、めちゃくちゃクリエイティビティなやり方で解いてる人が居て面白かったです。

https://github.com/cemeyer/advent-of-code-2021/blob/master/day24.rs#L164-L304

まとめ

去年 すぎゃーんに言われて始めた Advent Of Code だったけど、今年も継続してやることができました。しかも去年やるって言ってた Rust を学んだ上でそれで挑戦し、解くことができたのは、嬉しかったです。

来年は全部ちゃんと解けるようになりたいなーと思いつつも、健康や家族を優先にし、その中でやれる範囲でやれるようにしたいと思います。