Advent of code 2024 Day 12 Part 1 を Livebook で楽しむ

## はじめに

Advent of code 2024 Day 12 の Part 1 を解きます

問題文はこちら

https://adventofcode.com/2024/day/12

実装したノートブックはこちら

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2024/2024_day12_part1.livemd

## セットアップ

Kino AOC をインストールします

```elixir
Mix.install([
  {:kino_aoc, "~> 0.1"}
])
```

Kino AOC の使い方はこちらを参照

https://qiita.com/RyoWakabayashi/items/3d3abcf9134cee4dff05

## 入力の取得

"Advent of Code Helper" スマートセルを追加し、 Day 12 の入力を取得します

![スクリーンショット 2024-12-18 11.41.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/8fa415b6-5e87-ed67-1807-d9422c32aa14.png)

## 私の答え

私の答えです。
折りたたんでおきます。
▶を押して開いてください。

<details><summary>回答</summary>

小さい入力例で考えてみます

```elixir
small_sample_input =
  """
  AAAA
  BBCD
  BBCC
  EEEC
  """
  |> String.trim()
```

とりあえず、座標と植物のマップに変換します

```elixir
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
```

```elixir
map = parse_map.(small_sample_input)
```

実行結果

```elixir
%{
  {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
```

実装したモジュール

```elixir
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
```

```elixir
regions = Regions.get(map)
```

実行結果

```elixir
%{
  "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}]}]
}
```

領域毎に価格（単価=面積*柵の数）を計算します

```elixir
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
```

```elixir
sum_price.(regions)
```

実行結果

```elixir
140
```

大きい入力例に対しても実行してみます

```elixir
"""
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""
|> String.trim()
|> parse_map.()
|> Regions.get()
|> IO.inspect()
|> sum_price.()
```

標準出力

```elixir
%{
  "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}
      ]
    }
  ]
}
```

実行結果

```elixir
1930
```

実際の入力に対して実行すれば答えが出ます

```elixir
puzzle_input
|> parse_map.()
|> Regions.get()
|> sum_price.()
```

</details>

## まとめ

問題文から ChatGPT に画像を生成してもらいました

![aoc2024_day12_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/bc1e4186-e1c4-5c53-78e8-b790db27a350.png)

難産でしたが、何とか自力でクリアできました

Part 2 はこちら

https://qiita.com/RyoWakabayashi/private/ece609c3d6abd2880391