Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ElixirAdvent Calendar 2024

Day 2
@RyoWakabayashi(若林 諒)in株式会社オーイーシー

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

Last updated at Posted at 2024-12-18

はじめに

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

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

入力の取得

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

スクリーンショット 2024-12-18 11.41.31.png

私の答え

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

回答

柵の数ではなく、柵で囲った領域の辺の数で課金されます

「辺の数」で考えるとかなり難しい、ですが、「多角形の辺の数 = 多角形の角の数」ということに気づいて解けました

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

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

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

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

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

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

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

AAX
AAA
AAA

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

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

実装したモジュール

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

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

Regions.get_corners([:left])

実行結果

[:tr, :br]

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

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

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

実行結果

[:tl]

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

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

regions = Regions.get(map)

実行結果

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

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

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

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

sum_price.(regions)

実行結果

80

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

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

標準出力

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

実行結果

236

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

別の入力例でも試します

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

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

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

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

まとめ

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

aoc2024_day12_2.png

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

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

4
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?