Advent of Code 2024 Day 19: Linen Layout
このページは
2024 年の Advent of Code の Day19 の記事です。
Day18 の内容はこちら。
Day 19: Linen Layout
今回の舞台は温泉です。温泉に来たにも関わらず、入場料を支払うのに必要なお金を持っていないことに気づきました。仕方なく帰ろうとしていたところ、スタッフが呼び止め、 タオルを整理すること を手伝うことでタダで入場させてくれることを提案してくれました。
この温泉にあるタオルには、色のついたストライプのパターンがついています。どのパターンも何枚でも手に入れることが出来ます。色は 白(w)、青(u)、黒(b)、赤(r)、緑(g) の 5 種類からなります。また、タオルを反転させてパターンを逆順にすることはできません。
温泉のブランディング担当者が、ディスプレイさせたいタオルのストライプパターンを準備しています。同じタオルを何枚も使うことも出来ますが、ディスプレイさせたいタオルのストライプパターンと同じ順序で並べる必要があります。
Part1
Part1 は、
- 使用できるタオルのストライプパターンの一覧
- ディスプレイさせたいタオルのストライプパターン
が与えられるので、使用できるタオルを使って、ディスプレイさせたいタオルのストライプパターンを作ることができるか?という問題です。最終的には作成できるディスプレイパターンが何種類かを答える必要があります。
例えば、 r
, wr
, br
, b
というタオルがあった場合に、以下のディスプレイパターンが与えられた場合を考えましょう。ディスプレイさせたいタオルのストライプパターンが brwrr
の場合、図にすると以下のようになります。
この場合、ディスプレイパターンは 以下のような 2 通りを作成することが出来ます。
この問題については以下のような再帰関数で解きました。
- 残りのディスプレイパターンに合致するタオルがあれば、それ以後のディスプレイパターンを再帰的に探索
- 合致するタオルがない場合、そのディスプレイパターンは作成できないとして終了
として再帰的に探索することで、与えられたディスプレイパターンが構築可能かを判定することが出来ます。
Part2
Part1 では、ディスプレイパターンが構築可能かを問う問題でしたが、Part2 ではディスプレイパターンが構築可能な場合、タオルの組み合わせが何通りあるかを求める問題です。最終的にはすべての組み合わせの数を足し合わせたものを求める問題です。
これは Part1 と同様に再帰関数で解くことが出来、Part1 のコードを少し変えることで解くことが出来ます。
Part1 では構築可能かを判定するだけでしたが、今回は組み合わせの数を数える必要があるため、以下のように修正しました。
- 最後まで合致するタオルがあれば、そのディスプレイパターンは作成可能として、組み合わせの数を 1 として返す
- 現在のディスプレイパターンに合致するタオルがあるかを試して、合致するタオルがあれば、それ以後のディスプレイパターンを再帰的に探索し、組み合わせの数を足し合わせる
として再帰的に探索することで、ディスプレイパターンが構築可能な場合の組み合わせの数を求めることが出来ます。
Day20 に続きます。
Discussion