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

## はじめに

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

問題文はこちら

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

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

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

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/932fa600eba29e2def9c

## セットアップ

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()
```

座標と植物のマップにするところまでは Part 1 と同じです

```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"
}
```

外向きに角がある = 「上と右、上と左、下と右、下と左」のいずれかに柵があるということです

ややこしいのは内向きの角です

以下のような状況で内向きの角が存在します

```
AAX
AAA
AAA
```

中央から見たとき、上と右はどちらも柵がなく、右上の植物が別の植物になっています

このような状態をチェックし、外向きの角と内向きの角の両方を数えることで角の数 = 辺の数がカウントできます

実装したモジュール

```elixir
defmodule Regions do
  @next_points [
    {:top, {-1, 0}},
    {:bottom, {1, 0}},
    {:left, {0, -1}},
    {:right, {0, 1}}
  ]

  @corner_points %{
    tl: {-1, -1},
    tr: {-1, 1},
    bl: {1, -1},
    br: {1, 1}
  }

  @initial_region %{
    price: 0,
    num_corners: 0,
    points: []
  }

  def get(map) do
    map_with_corners =
      map
      |> get_points_corners()
      |> get_num_corners()
    
    map_with_corners
    |> Enum.reduce(%{}, fn {_, %{plant: plant}} = area, acc_regions ->
      region = connect_point(area, map_with_corners, acc_regions)
      Map.put(acc_regions, plant, region)
    end)
  end

  def get_points_corners(map) do
    map
    |> Enum.into(%{}, fn {point, plant} ->
      {cur_r, cur_c} = point

      directions =
        @next_points
        |> Enum.reduce([], fn {direction, {mov_r, move_c}}, acc_directions ->
          next_point = {cur_r + mov_r, cur_c + move_c}

          case Map.get(map, next_point) do
            ^plant ->
              [direction | acc_directions]

            _ ->
              acc_directions
          end
        end)

      {
        point,
        %{
          plant: plant,
          corners: get_corners(directions),
          not_corners: get_not_corners(directions)
        }
      }
    end)
  end

  def get_corners(directions) do
    [
      {:tl, :top, :left},
      {:tr, :top, :right},
      {:bl, :bottom, :left},
      {:br, :bottom, :right}
    ]
    |> Enum.filter(fn {_, vertical, horizontal} ->
      if !Enum.member?(directions, vertical) and !Enum.member?(directions, horizontal) do
        :tl
      else
        nil
      end
    end)
    |> Enum.map(fn {corner, _, _} ->
      corner
    end)
  end

  def get_not_corners(directions) do
    [
      {:tl, :top, :left},
      {:tr, :top, :right},
      {:bl, :bottom, :left},
      {:br, :bottom, :right}
    ]
    |> Enum.filter(fn {_, vertical, horizontal} ->
      if Enum.member?(directions, vertical) and Enum.member?(directions, horizontal) do
        :tl
      else
        nil
      end
    end)
    |> Enum.map(fn {corner, _, _} ->
      corner
    end)
  end

  defp get_num_corners(map) do
    map
    |> Enum.into(%{}, fn {point, %{plant: plant, corners: corners, not_corners: not_corners}} ->
      num_outside_corners = length(corners)
      {cur_r, cur_c} = point

      num_inside_corners =
        not_corners
        |> Enum.count(fn not_coner ->
          {mov_r, move_c} = Map.get(@corner_points, not_coner)
          corner_point = {cur_r + mov_r, cur_c + move_c}
  
          case Map.get(map, corner_point) do
            nil -> false
            %{plant: target_plant} ->
              plant != target_plant
          end
        end)

      {
        point,
        %{
          plant: plant,
          num_corners: num_outside_corners + num_inside_corners
        }
      }
    end)
  end

  defp connect_point(area, map, acc_regions) do
    {point, %{plant: plant, num_corners: new_corners}} = area
    {cur_r, cur_c} = point

    new_points =
      @next_points
      |> Enum.reduce([], fn {_, {mov_r, move_c}}, acc_points ->
        next_point = {cur_r + mov_r, cur_c + move_c}

        case Map.get(map, next_point) do
          nil ->
            acc_points

          next_area ->
            if next_area.plant == plant do
              [next_point | acc_points]
            else
              acc_points
            end
        end
      end)

    new_points = [point | new_points]

    case Map.get(acc_regions, plant) do
      nil ->
        [
          %{
            price: 1,
            num_corners: new_corners,
            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, num_corners: num_corners, points: points} ->
            %{
              price: price + 1,
              num_corners: num_corners + new_corners,
              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,
        num_corners: acc_sub_region.num_corners + sub_region.num_corners,
        points: acc_sub_region.points ++ sub_region.points
      }
    end)
  end
end
```

「開いている方向」を元に外向きの角を取得する関数を試してみます

```elixir
Regions.get_corners([:left])
```

実行結果

```elixir
[:tr, :br]
```

左側が開いているので、右上と右下が角になっています

「開いている方向」を元に内向きの角候補（隣接する２方向共に開いている向き）を取得する関数を試してみます

```elixir
Regions.get_not_corners([:top, :left])
```

実行結果

```elixir
[:tl]
```

上と左が開いているため、左上が内向きの角候補です

小さな入力例で領域を取得してみます

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

実行結果

```elixir
%{
  "A" => [%{price: 4, points: [{0, 3}, {0, 2}, {0, 1}, {0, 0}], num_corners: 4}],
  "B" => [%{price: 4, points: [{2, 1}, {2, 0}, {1, 1}, {1, 0}], num_corners: 4}],
  "C" => [%{price: 4, points: [{3, 3}, {2, 3}, {2, 2}, {1, 2}], num_corners: 8}],
  "D" => [%{price: 1, points: [{1, 3}], num_corners: 4}],
  "E" => [%{price: 3, points: [{3, 2}, {3, 1}, {3, 0}], num_corners: 4}]
}
```

領域毎に角の数が正しく取得できています

これを元に料金を計算します

```elixir
sum_price = fn regions ->
  regions
  |> Enum.map(fn {_, sub_regions} ->
    sub_regions
    |> Enum.map(fn %{price: price, num_corners: num_corners} ->
      price * num_corners
    end)
    |> Enum.sum()
  end)
  |> Enum.sum()
end
```

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

実行結果

```elixir
80
```

少し大きな入力例でも実行してみます

```elixir
"""
EEEEE
EXXXX
EEEEE
EXXXX
EEEEE
"""
|> String.trim()
|> parse_map.()
|> Regions.get()
|> IO.inspect()
|> sum_price.()
```

標準出力

```elixir
%{
  "E" => [
    %{
      price: 17,
      points: [
        {4, 4},
        {4, 3},
        {4, 2},
        {4, 1},
        {4, 0},
        {3, 0},
        {2, 0},
        {2, 4},
        {2, 3},
        {2, 2},
        {2, 1},
        {1, 0},
        {0, 0},
        {0, 4},
        {0, 3},
        {0, 2},
        {0, 1}
      ],
      num_corners: 12
    }
  ],
  "X" => [
    %{price: 4, points: [{3, 4}, {3, 3}, {3, 2}, {3, 1}], num_corners: 4},
    %{price: 4, points: [{1, 4}, {1, 3}, {1, 2}, {1, 1}], num_corners: 4}
  ]
}
```

実行結果

```elixir
236
```

内向きの角も正しくカウントできています

別の入力例でも試します

```elixir
"""
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA
"""
|> String.trim()
|> parse_map.()
|> Regions.get()
|> IO.inspect()
|> sum_price.()
```

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

実際の入力で実行すれば答えが出ます

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

</details>

## まとめ

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

![aoc2024_day12_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/9e50ed9c-250b-5672-9a79-7f5c912b53f1.png)

最初は「辺の数」で考えて詰みそうになりました

発想の転換が必要な問題でした