Advent of Code - Day 12

Part 1

raw_sample = """
AAAA
BBCD
BBCC
EEEC
"""

raw_mid_sample = """
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO
"""

raw_big_sample = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""

Each garden plot grows only a single type of plant and is indicated by a single letter on your map. When multiple garden plots are growing the same type of plant and are touching (horizontally or vertically), they form a region. For example:

The area of a region is simply the number of garden plots the region contains. The above map’s type A, B, and C plants are each in a region of area 4. The type E plants are in a region of area 3; the type D plants are in a region of area 1.

Each garden plot is a square and so has four sides. The perimeter of a region is the number of sides of garden plots in the region that do not touch another garden plot in the same region.

Plants of the same type can appear in multiple separate regions, and regions can even appear within other regions. For example:

OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

The above map contains five regions, one containing all of the O garden plots, and the other four each containing a single X plot.

The four X regions each have area 1 and perimeter 4. The region containing 21 type O plants is more complicated; in addition to its outer edge contributing a perimeter of 20, its boundary with each X region contributes an additional 4 to its perimeter, for a total perimeter of 36.

Multiplying that region’s area by its perimeter. The total price of fencing all regions on a map is found by adding together the price of fence for every region on the map.

In the first example, region A has price 4 10 = 40, region B has price 4 8 = 32, region C has price 4 10 = 40, region D has price 1 4 = 4, and region E has price 3 * 8 = 24. So, the total price for the first example is 140.

In the second example, the region with all of the O plants has price 21 36 = 756, and each of the four smaller X regions has price 1 4 = 4, for a total price of 772 (756 + 4 + 4 + 4 + 4).

Here’s a larger example:

RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE

It contains:

• A region of R plants with price 12 * 18 = 216.
• A region of I plants with price 4 * 8 = 32.
• A region of C plants with price 14 * 28 = 392.
• A region of F plants with price 10 * 18 = 180.
• A region of V plants with price 13 * 20 = 260.
• A region of J plants with price 11 * 20 = 220.
• A region of C plants with price 1 * 4 = 4.
• A region of E plants with price 13 * 18 = 234.
• A region of I plants with price 14 * 22 = 308.
• A region of M plants with price 5 * 12 = 60.
• A region of S plants with price 3 * 8 = 24. So, it has a total price of 1930.

What is the total price of fencing all regions on your map?

defmodule Part1 do
  def parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {line, row}, mat ->
      line
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.reduce(mat, fn {cell, col}, mat ->
        Map.put(mat, {row, col}, cell)
      end)
    end)
  end

  def find_regions(mat) do
    plots = Map.keys(mat)
    lplots = MapSet.new(Map.keys(mat))

    Enum.reduce_while(plots, {lplots, %{}}, fn plot, {leftover_plots, regions} ->
      cond do
        leftover_plots |> Enum.empty?() ->
          {:halt, {leftover_plots, regions}}

        not MapSet.member?(leftover_plots, plot) ->
          {:cont, {leftover_plots, regions}}

        true ->
          symbol = Map.fetch!(mat, plot)

          region_set =
            recurse_area(mat, plot, symbol, MapSet.new([plot]))

          region_key = (Map.keys(regions) |> length()) + 1
          regions = Map.put(regions, region_key, region_set)
          leftover_plots = MapSet.difference(leftover_plots, region_set)

          {:cont, {leftover_plots, regions}}
      end
    end)
    |> elem(1)
  end

  def find_area(region_set) do
    region_set |> MapSet.size()
  end

  def recurse_area(mat, {x, y}, symbol, visited) do
    variants = [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]

    valid_variants =
      variants
      |> Enum.filter(fn v ->
        case Map.fetch(mat, v) do
          {:ok, sym} when sym == symbol ->
            not MapSet.member?(visited, v)

          _ ->
            false
        end
      end)

    # Terminate recursion if no valid variants are found
    if Enum.empty?(valid_variants) do
      visited
    else
      Enum.reduce(valid_variants, visited, fn v, acc ->
        acc = MapSet.put(acc, v)
        recurse_area(mat, v, symbol, acc)
      end)
    end
  end

  def find_price(regions) do
    regions
    |> Enum.reduce(0, fn region_set, acc ->
      acc + find_area(region_set) * find_perimeter(region_set)
    end)
  end

  def find_perimeter(region_set) do
    region_set
    |> Enum.reduce(0, fn {x, y}, acc ->
      variants = [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]

      valid_variants =
        variants
        |> Enum.filter(fn v ->
          not MapSet.member?(region_set, v)
        end)

      acc + length(valid_variants)
    end)
  end
end

Part1.parse_input(raw_sample)
|> Part1.find_regions()
|> Map.values()
|> Part1.find_price()

Part1.parse_input(raw_mid_sample)
|> Part1.find_regions()
|> Map.values()
|> Part1.find_price()

File.read!("/Users/errantsky/elixir-projects/phoenix-projects/advent_of_code_2024/inputs/day12.txt")
|> Part1.parse_input()
|> Part1.find_regions()
|> Map.values()
|> Part1.find_price()

Part 2

Instead of area, count sides of each region to find the price.

defmodule Part2 do
  def parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {line, row}, mat ->
      line
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.reduce(mat, fn {cell, col}, mat ->
        Map.put(mat, {row, col}, cell)
      end)
    end)
  end

  def find_regions(mat) do
    plots = Map.keys(mat)
    lplots = MapSet.new(Map.keys(mat))

    Enum.reduce_while(plots, {lplots, %{}}, fn plot, {leftover_plots, regions} ->
      cond do
        leftover_plots |> Enum.empty?() ->
          {:halt, {leftover_plots, regions}}

        not MapSet.member?(leftover_plots, plot) ->
          {:cont, {leftover_plots, regions}}

        true ->
          symbol = Map.fetch!(mat, plot)

          region_set =
            recurse_area(mat, plot, symbol, MapSet.new([plot]))

          region_key = (Map.keys(regions) |> length()) + 1
          regions = Map.put(regions, region_key, region_set)
          leftover_plots = MapSet.difference(leftover_plots, region_set)

          {:cont, {leftover_plots, regions}}
      end
    end)
    |> elem(1)
  end

  def gen_variants({x, y}) do
    [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]
  end

  def surrounded?({x, y} = plot, map_set) do
    gen_variants(plot)
    |> Enum.all?(fn neighbor ->
      MapSet.member?(map_set, neighbor)
    end)
  end

  def find_sides(region_set) do
    {{min_x, _}, {max_x, _}} = region_set |> Enum.min_max()
    {{_, min_y}, {_, max_y}} = region_set |> Enum.min_max_by(fn p -> elem(p, 1) end)

    {map_by_x, map_by_y} =
      region_set
      |> Enum.reduce(
        {%{}, %{}},
        fn {x, y}, {x_map, y_map} ->
          x_map =
            Map.get_and_update(x_map, x, fn cur_val ->
              case cur_val do
                nil -> {nil, [{x, y}]}
                _ -> {cur_val, [{x, y} | cur_val]}
              end
            end)

          y_map =
            Map.get_and_update(y_map, y, fn cur_val ->
              case cur_val do
                nil -> {nil, [{x, y}]}
                _ -> {cur_val, [{x, y} | cur_val]}
              end
            end)

          {x_map, y_map}
        end
      )

    # move a line in each axis through the range
    # count all intersecting cells, exclude those surrounded

    vertical_sides =
      min_x..max_x
      |> Enum.reduce(0, fn row, acc ->
        intersecting = Map.get(map_by_x, row, [])

        Enum.count(intersecting, fn i ->
          not surrounded?(i, region_set)
        end) + acc
      end)
  end

  def find_area(region_set) do
    region_set |> MapSet.size()
  end

  def recurse_area(mat, {x, y}, symbol, visited) do
    variants = [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]

    valid_variants =
      variants
      |> Enum.filter(fn v ->
        case Map.fetch(mat, v) do
          {:ok, sym} when sym == symbol ->
            not MapSet.member?(visited, v)

          _ ->
            false
        end
      end)

    # Terminate recursion if no valid variants are found
    if Enum.empty?(valid_variants) do
      visited
    else
      Enum.reduce(valid_variants, visited, fn v, acc ->
        acc = MapSet.put(acc, v)
        recurse_area(mat, v, symbol, acc)
      end)
    end
  end

  def find_price(regions) do
    regions
    |> Enum.reduce(0, fn region_set, acc ->
      acc + find_area(region_set) * find_perimeter(region_set)
    end)
  end

  def find_perimeter(region_set) do
    region_set
    |> Enum.reduce(0, fn {x, y}, acc ->
      variants = [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]

      valid_variants =
        variants
        |> Enum.filter(fn v ->
          not MapSet.member?(region_set, v)
        end)

      acc + length(valid_variants)
    end)
  end
end

[{1, 0}, {2, 0}, {0, 1}] |> Enum.min_max_by(fn p -> elem(p, 0) end)