Advent of Code 2024 - Day 12

[ken-kost]

Man I got stuck on this one. First I wasn’t able to parse correctly i.e. get the groups. Tried multiple approaches and although they would work on test examples it wouldn’t on the input. Day after I cracked it but then got stuck on part 2. So I was bashing my head yet again. Went here to maybe get an idea, and I did thanks to @bjorng

My code connects all adjacent pieces of the fence.

So that’s what I tried as well. I unpacked the fence calculation from part 1 to preserve sides information and then parsed that. Now I’m behind 3 days and it’s only getting harder. But I’ll persevere.

defmodule Aoc2024.Solutions.Y24.Day12 do
  alias AoC.Input

  def parse(input, _part) do
    [{first_line, 0} | rest] =
      input
      |> Input.stream!(trim: true)
      |> Enum.with_index()

    first_chunks =
      first_line
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {e, y} -> {e, 0, y} end)
      |> Enum.chunk_by(fn {e, _, _} -> e end)

    Enum.reduce(rest, first_chunks, fn {line, x}, acc ->
      line
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {e, y} -> {e, x, y} end)
      |> Enum.chunk_by(fn {e, _, _} -> e end)
      |> Enum.reduce(acc, fn chunk, groups ->
        group_chunk(groups, chunk)
      end)
    end)
  end

  def part_one(problem) do
    problem
    |> Enum.reduce(0, fn group, acc ->
      group = Enum.map(group, fn {_, x, y} -> {x, y} end)

      fence =
        Enum.reduce(group, 0, fn point, acc ->
          acc + length(calculate_fence(point, group))
        end)

      acc + length(group) * fence
    end)
  end

  def part_two(problem) do
    problem
    |> Enum.map(fn group ->
      group = Enum.map(group, fn {_, x, y} -> {x, y} end)

      Enum.reduce(group, [], fn point, acc ->
        [{point, calculate_fence(point, group)} | acc]
      end)
    end)
    |> Enum.map(fn group ->
      h_chunks = Enum.chunk_by(group, fn {{x, _y}, _} -> x end)
      counter_h = count_sides(h_chunks, :up, 1) + count_sides(h_chunks, :down, 1)
      v_chunks = Enum.group_by(group, fn {{_x, y}, _} -> y end) |> Map.values()
      counter_v = count_sides(v_chunks, :left, 0) + count_sides(v_chunks, :right, 0)
      {length(group), counter_h + counter_v}
    end)
    |> Enum.reduce(0, fn {length, sides}, acc -> acc + length * sides end)
  end

  defp group_chunk(groups, chunk) do
    case Enum.split_with(groups, fn group -> belongs_to?(group, chunk) end) do
      {[], groups} -> [chunk | groups]
      {chunk_groups, groups} -> [Enum.concat(chunk_groups ++ [chunk]) | groups]
    end
  end

  defp belongs_to?(group, chunk) do
    Enum.any?(group, fn {e, x, y} -> {e, x + 1, y} in chunk end)
  end

  defp calculate_fence({x, y}, list) do
    result = []
    result = if {x + 1, y} in list, do: result, else: [:down | result]
    result = if {x - 1, y} in list, do: result, else: [:up | result]
    result = if {x, y + 1} in list, do: result, else: [:right | result]
    if {x, y - 1} in list, do: result, else: [:left | result]
  end

  defp count_sides(chunks, direction, index) do
    Enum.reduce(chunks, 0, fn chunk, acc ->
      acc +
        case Enum.filter(chunk, fn {_point, fences} -> direction in fences end) do
          [] ->
            0

          [chunk_up_head | chunk_up_rest] ->
            {point, _} = chunk_up_head
            e = elem(point, index)

            {_, counter} =
              Enum.reduce(chunk_up_rest, {e, 1}, fn {point, _}, {tracker, counter} ->
                if elem(point, index) + 1 == tracker do
                  {tracker - 1, counter}
                else
                  {elem(point, index), counter + 1}
                end
              end)

            counter
        end
    end)
  end
end

Also, I stumbled upon a behavior which was unexpected to me while working on this, regarding group_by/chunk_by.
I made a post here about it.

[stevensonmt]

Using :digraph_utils.strong_components to generate the regions made things very simple for part 1. Took me quite a long time to figure out how to count the sides. I was trying to do things as overlapping rectangles where every rectangle has four sides but you subtract sides for intersections but I couldn’t get it to work. Reddit post on counting corners saved me.

defmodule Day12 do
  
  def run(mode) do
    graph =
      mode
      |> input()
      |> parse()

    part_1(graph) |> IO.inspect(label: :part_1)
    part_2(graph) |> IO.inspect(label: :part_2)
  end
  defp input(:real), do: @real

  defp parse(input) do
    input
    |> graph()
    |> regions()
  end

  defp graph(input) do
    graph = :digraph.new()
    
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.each(fn {line, row} ->
      line
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.map(fn {g, col} -> {{row, col}, g} end)
      |> Enum.each(fn {{r, c} = coord, char} ->
        :digraph.add_vertex(graph, coord, char)
        :digraph.add_edge(graph, coord, coord)
      end)
    end)

    Agent.start_link(fn -> %{rows: max_rows, cols: max_cols} end, name: :COUNTERS)
    graph
  end

  defp regions(graph) do
    vs = :digraph.vertices(graph) |> Enum.map(&:digraph.vertex(graph, &1))

    for {{r1, c1}, l1} <- vs,
        {{r2, c2}, l2} <- vs -- [{{r1, c1}, l1}],
        l1 == l2,
        (r1 == r2 and abs(c1 - c2) == 1) or (c1 == c2 and abs(r1 - r2) == 1) do
      :digraph.add_edge(graph, {r1, c1}, {r2, c2})
    end

    graph
  end

  defp part_1(graph) do
    graph
    |> perimeters_and_areas_of_regions()
    |> Enum.sum_by(&cost/1)
  end

  defp part_2(graph) do
    graph
    |> sides_count_and_areas_of_regions()
    |> Enum.sum_by(&cost/1)
  end

  defp perimeters_and_areas_of_regions(graph) do
    graph
    |> :digraph_utils.strong_components()
    |> Enum.map(fn sub ->
      sub = :digraph_utils.subgraph(graph, sub)
      area = area(sub)
      {area * 4 - perimeter(sub), area}
    end)
  end

  defp perimeter(graph) do
    graph
    |> :digraph.edges()
    |> Enum.map(&:digraph.edge(graph, &1))
    |> Enum.map(fn e -> {elem(e, 1), elem(e, 2)} end)
    |> Enum.reject(fn {a, b} -> a == b end)
    |> Enum.count()
  end

  defp area(graph) do
    :digraph.vertices(graph) |> Enum.count()
  end

  defp sides_count_and_areas_of_regions(graph) do
    graph
    |> :digraph_utils.strong_components()
    |> Enum.map(fn sub -> :digraph_utils.subgraph(graph, sub) end)
    |> Enum.map(fn subg -> {sides(subg), area(subg)} end)
  end

  defp sides(graph) do
    graph
    |> :digraph.vertices()
    |> Enum.map(fn v ->
      {v, :digraph.out_neighbours(graph, v)}
    end)
    |> Enum.map(fn {v, nbrs} ->
      shape(v, nbrs, graph)
    end)
    |> Enum.sum()
  end

  defp shape(v, nbr_grp, graph) do
    set = MapSet.new(nbr_grp)

    cond do
      set in l_shape(v) -> 2 - inside_corner_occupied(graph, set, v)
      set in t_shape(v) -> 2 - inside_corner_occupied(graph, set, v)
      set == cross_shape(v) -> 4 - inside_corner_occupied(graph, set, v)
      set in i_shape(v) -> 2
      set in long_linear_shape(v) -> 0
      isolated(v) -> 4
    end
  end

  defp l_shape({r, c}) do
    [[{1, 0}, {0, 1}], [{1, 0}, {0, -1}], [{-1, 0}, {0, 1}], [{-1, 0}, {0, -1}]]
    |> Enum.map(fn [{r1, c1}, {r2, c2}] ->
      MapSet.new([{r, c}, {r + r1, c + c1}, {r + r2, c + c2}])
    end)
  end

  defp t_shape({r, c}) do
    [
      [{1, 0}, {0, 1}, {0, -1}],
      [{-1, 0}, {0, 1}, {0, -1}],
      [{1, 0}, {-1, 0}, {0, 1}],
      [{1, 0}, {-1, 0}, {0, -1}]
    ]
    |> Enum.map(fn [{r1, c1}, {r2, c2}, {r3, c3}] ->
      MapSet.new([{r, c}, {r + r1, c + c1}, {r + r2, c + c2}, {r + r3, c + c3}])
    end)
  end

  defp cross_shape({r, c}),
    do: MapSet.new([{r, c}, {r + 1, c}, {r - 1, c}, {r, c + 1}, {r, c - 1}])

  defp i_shape({r, c}) do
    [[{0, 0}, {0, 1}], [{0, 0}, {0, -1}], [{0, 0}, {1, 0}], [{0, 0}, {-1, 0}]]
    |> Enum.map(fn nbrs ->
      nbrs |> Enum.map(fn {dr, dc} -> {r + dr, c + dc} end) |> MapSet.new()
    end)
  end

  defp long_linear_shape({r, c}) do
    [
      [{0, 0}, {0, 1}, {0, -1}],
      [{0, 0}, {1, 0}, {-1, 0}]
    ]
    |> Enum.map(fn nbrs ->
      nbrs |> Enum.map(fn {dr, dc} -> {r + dr, c + dc} end) |> MapSet.new()
    end)
  end

  defp isolated(v), do: MapSet.new([v])

  defp inside_corner_occupied(graph, set, v) do
    [nw(v), sw(v), ne(v), se(v), nw_sw(v), ne_se(v), nw_ne(v), sw_se(v), nsew(v)]
    |> Enum.map(fn set1 -> MapSet.difference(set1, set) end)
    |> Enum.filter(fn set1 -> MapSet.size(set1) == 1 end)
    |> Enum.filter(fn set1 ->
      corner = set1 |> MapSet.to_list() |> hd()
      corner_occupied?(corner, graph)
    end)
    |> Enum.count()
  end

  defp nw({r, c}), do: MapSet.new([{r, c}, {r - 1, c}, {r, c - 1}, {r - 1, c - 1}])
  defp sw({r, c}), do: MapSet.new([{r, c}, {r + 1, c}, {r, c - 1}, {r + 1, c - 1}])
  defp ne({r, c}), do: MapSet.new([{r, c}, {r - 1, c}, {r, c + 1}, {r - 1, c + 1}])
  defp se({r, c}), do: MapSet.new([{r, c}, {r + 1, c}, {r, c + 1}, {r + 1, c + 1}])
  defp nw_sw(v), do: MapSet.union(nw(v), sw(v))
  defp ne_se(v), do: MapSet.union(ne(v), se(v))
  defp nw_ne(v), do: MapSet.union(nw(v), ne(v))
  defp sw_se(v), do: MapSet.union(sw(v), se(v))
  defp nsew(v), do: MapSet.union(nw_sw(v), ne_se(v))

  defp corner_occupied?(corner, graph) do
    :digraph.vertex(graph, corner)
  end

  defp cost({perimeter, area}), do: perimeter * area
end

Day12.run(:test1)
Day12.run(:test2)
Day12.run(:test3)
Day12.run(:test4)
Day12.run(:test5)
Day12.run(:real)

Reading through the posts above I’m really surprised more people did not use :digraph as the grid structure. I really hate implementing all the path tracking stuff by hand so I probably overuse it, but it felt right for this problem.