はじめに
Advent of code 2024 Day 12 の Part 1 を解きます
問題文はこちら
実装したノートブックはこちら
セットアップ
Kino AOC をインストールします
Mix.install([
{:kino_aoc, "~> 0.1"}
])
Kino AOC の使い方はこちらを参照
入力の取得
"Advent of Code Helper" スマートセルを追加し、 Day 12 の入力を取得します
私の答え
私の答えです。
折りたたんでおきます。
▶を押して開いてください。
回答
小さい入力例で考えてみます
small_sample_input =
"""
AAAA
BBCD
BBCC
EEEC
"""
|> String.trim()
とりあえず、座標と植物のマップに変換します
parse_map = fn input ->
input
|> String.split("\n")
|> Enum.with_index()
|> Enum.flat_map(fn {row, row_index} ->
row
|> String.codepoints()
|> Enum.with_index()
|> Enum.map(fn {plant, col_index} ->
{{row_index, col_index}, plant}
end)
end)
|> Enum.into(%{})
end
map = parse_map.(small_sample_input)
実行結果
%{
{0, 0} => "A",
{0, 1} => "A",
{0, 2} => "A",
{0, 3} => "A",
{1, 0} => "B",
{1, 1} => "B",
{1, 2} => "C",
{1, 3} => "D",
{2, 0} => "B",
{2, 1} => "B",
{2, 2} => "C",
{2, 3} => "C",
{3, 0} => "E",
{3, 1} => "E",
{3, 2} => "E",
{3, 3} => "C"
}
領域毎に切り分けて柵の数と面積（単価）を算出するモジュールを作ります
上下左右の位置に同じ植物があれば接続可能、という考え方で領域をつなげていきます
例えば、以下のケースで真ん中の座標についてチェックする場合を考えます
XBX
AAB
XAX
- 上は違う植物なので接続不可、上に柵を一つ作る
- 下は同じ植物なので接続可能、柵は作らない
- 左は同じ植物なので接続可能、柵は作らない
- 右は違う植物なので接続不可、右に柵を一つ作る
これにより、中央の座標には柵が二つあり、左と下に接続可能なことがわかります
重要なのは merge_sub_regions 関数で、複数の領域に接続できた場合、領域を併合する処理を行っています
例えば以下の図で中央の座標をチェックした場合、左と上の領域を一つの領域としてまとめています
XAAAX
XXAXX
AAAXX
AXXXX
AXXXX
実装したモジュール
defmodule Regions do
@next_points [
{-1, 0},
{1, 0},
{0, -1},
{0, 1}
]
@initial_region %{
price: 0,
fences: 0,
points: []
}
def get(map) do
map
|> Enum.reduce(%{}, fn {point, plant}, acc_regions ->
region = connect_point(point, plant, map, acc_regions)
Map.put(acc_regions, plant, region)
end)
end
defp connect_point(point, plant, map, acc_regions) do
{cur_r, cur_c} = point
{num_fences, new_points} =
@next_points
|> Enum.reduce({0, []}, fn {mov_r, move_c}, {acc_fences, acc_points} ->
next_point = {cur_r + mov_r, cur_c + move_c}
case Map.get(map, next_point) do
^plant ->
{acc_fences, [next_point | acc_points]}
_ ->
{acc_fences + 1, acc_points}
end
end)
new_points = [point | new_points]
case Map.get(acc_regions, plant) do
nil ->
[
%{
price: 1,
fences: num_fences,
points: new_points
}
]
sub_regions ->
connected_regions =
sub_regions
|> Enum.filter(fn %{points: points} ->
Enum.any?(new_points, fn point ->
Enum.member?(points, point)
end)
end)
not_connected_regions = sub_regions -- connected_regions
merged_region =
connected_regions
|> merge_sub_regions()
|> then(fn %{price: price, fences: fences, points: points} ->
%{
price: price + 1,
fences: fences + num_fences,
points: Enum.uniq(new_points ++ points)
}
end)
[merged_region | not_connected_regions]
end
end
defp merge_sub_regions(connected_regions) do
connected_regions
|> Enum.reduce(@initial_region, fn sub_region, acc_sub_region ->
%{
price: acc_sub_region.price + sub_region.price,
fences: acc_sub_region.fences + sub_region.fences,
points: acc_sub_region.points ++ sub_region.points
}
end)
end
end
regions = Regions.get(map)
実行結果
%{
"A" => [%{price: 4, fences: 10, points: [{0, 3}, {0, 2}, {0, 1}, {0, 0}]}],
"B" => [%{price: 4, fences: 8, points: [{2, 1}, {2, 0}, {1, 1}, {1, 0}]}],
"C" => [%{price: 4, fences: 10, points: [{3, 3}, {2, 3}, {2, 2}, {1, 2}]}],
"D" => [%{price: 1, fences: 4, points: [{1, 3}]}],
"E" => [%{price: 3, fences: 8, points: [{3, 2}, {3, 1}, {3, 0}]}]
}
領域毎に価格（単価=面積*柵の数）を計算します
sum_price = fn regions ->
regions
|> Enum.map(fn {_, sub_regions} ->
sub_regions
|> Enum.map(fn %{price: price, fences: fences} ->
price * fences
end)
|> Enum.sum()
end)
|> Enum.sum()
end
sum_price.(regions)
実行結果
140
大きい入力例に対しても実行してみます
"""
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""
|> String.trim()
|> parse_map.()
|> Regions.get()
|> IO.inspect()
|> sum_price.()
標準出力
%{
"C" => [
%{
price: 14,
fences: 28,
points: [
{1, 8},
{1, 7},
{5, 4},
{5, 5},
{4, 4},
{3, 4},
{3, 5},
{3, 3},
{1, 6},
{2, 6},
{0, 6},
{2, 5},
{6, 5},
{0, 7}
]
},
%{price: 1, fences: 4, points: [{4, 7}]}
],
"E" => [
%{
price: 13,
fences: 18,
points: [
{9, 9},
{9, 8},
{8, 9},
{8, 8},
{7, 9},
{4, 9},
{5, 9},
{6, 9},
{6, 8},
{5, 8},
{8, 7},
{9, 7},
{7, 8}
]
}
],
"F" => [
%{
price: 10,
fences: 18,
points: [
{3, 7},
{3, 8},
{2, 7},
{3, 9},
{2, 9},
{0, 8},
{0, 9},
{2, 8},
{1, 9},
{4, 8}
]
}
],
"I" => [
%{price: 4, fences: 8, points: [{1, 5}, {1, 4}, {0, 5}, {0, 4}]},
%{
price: 14,
fences: 22,
points: [
{6, 2},
{6, 3},
{7, 2},
{5, 2},
{7, 4},
{7, 5},
{7, 3},
{6, 4},
{7, 1},
{8, 2},
{8, 3},
{9, 3},
{8, 1},
{8, 5}
]
}
],
"J" => [
%{
price: 11,
fences: 20,
points: [
{5, 7},
{5, 6},
{6, 7},
{4, 5},
{4, 6},
{7, 7},
{7, 6},
{3, 6},
{8, 6},
{6, 6},
{9, 6}
]
}
],
"M" => [
%{price: 5, fences: 12, points: [{9, 1}, {9, 2}, {9, 0}, {7, 0}, {8, 0}]}
],
"R" => [
%{
price: 12,
fences: 18,
points: [
{1, 3},
{1, 2},
{2, 3},
{0, 3},
{1, 1},
{1, 0},
{0, 1},
{0, 0},
{2, 2},
{3, 2},
{0, 2},
{2, 4}
]
}
],
"S" => [%{price: 3, fences: 8, points: [{9, 4}, {9, 5}, {8, 4}]}],
"V" => [
%{
price: 13,
fences: 20,
points: [
{5, 0},
{5, 1},
{6, 0},
{4, 0},
{6, 1},
{5, 3},
{4, 3},
{3, 1},
{3, 0},
{4, 1},
{2, 1},
{4, 2},
{2, 0}
]
}
]
}
実行結果
1930
実際の入力に対して実行すれば答えが出ます
puzzle_input
|> parse_map.()
|> Regions.get()
|> sum_price.()
まとめ
問題文から ChatGPT に画像を生成してもらいました
難産でしたが、何とか自力でクリアできました
Part 2 はこちら