Advent of Code 2024 Day 12: Garden Groups
このページは
2024 年の Advent of Code の Day12 の記事です。 Day11 はこちら。
Day 12: Garden Groups
今回は庭の植物にフェンスを立てる問題のようです。Part1, Part2 共にフェンスを立てたときに必要なコストを求めようというものです。
AAAA
BBCD
BBCC
EEEC
というような入力が与えられるとします。各文字は植物の種類を表しており、同じ植物はまとめて、別の種類の間にフェンスを立てるものとします。
例えば上の図のような入力の場合は
+----+
|AAAA|
+----+
+--+
|BB|
|BB|
+--+
のようなフェンスの置き方になるとします。
Part1
Part1 では、各フェンスの数とグループごとにまとめられた植物の数を掛け合わせたものをコストとして考えるというものです。
同じグループの植物の数については、 BFS や DFS を使うことで、数え上げることが出来そうです。
フェンスの数については、どのように数えると良さそうか考えてみましょう。
一番簡単に A が一つだけある場合は上下左右それぞれ 1 つずつで合計 4 つのフェンスが必要になりそうです。
A が 2 つ左右に並んだケースについて考えてみましょう。この場合は重複している赤いフェンスについては建てる必要がなさそうです。
そのため、フェンスが必要かどうかについては、上下左右に同じ文字の植物が並んでいるかを確認し、同じ文字の植物の場合はフェンスを建てない、異なる文字や端の場合はフェンスを建てるとして数え上げることが出来そうです。
コードでは最初に上下左右にフェンスが必要として 4 を足し上げ、その後同じ文字が隣り合っている数を数えて減らすようにしました。
Part2
Part2 では、フェンスが直線的に続いている場合は一つのフェンスとして、数えるものとします。
上記のようなケースの場合、 Part1 ではフェンスの数は 6 個でしたが、Part2 では以下のように 4 つとカウントするものとします。
以下のような場合は、6 個となります。
こちらのケースの場合も、同じグループになる植物の数については Part1 と同じような数え方で良さそうです。フェンスの数え方が違うためそちらを考えましょう。
のように、上下左右それぞれについて、フェンスが必要な区間を愚直に考えるようにしました。
例えば以下のようなケースで、左右のマスの座標を(0, 0), (0, 1) とします。
上部にフェンスが必要な区間は 0 マス目から 1 マス目の終わり(２マス目の開始まで) となるため、 [(0, 1), (1, 2)] と記録します。
その後、重なるもしくは連続する区間の場合はまとめて一つにすることで、フェンスをまとめることが出来ました。
上下左右それぞれ同じ処理を行うことで、グループごとに必要なフェンスの数を数え上げることが出来そうです。
最終的にはフェンスの数とグループごとの植物の数を掛け合わせてコストを求めましょう。
Day 13 に続きます。
Discussion