Advent of Code 2024 - Day 12

At first I was scared but I found is a simple way to compute the sides.

defmodule AdventOfCode.Solutions.Y24.Day12 do
  alias AdventOfCode.Grid
  alias AoC.Input

  def parse(input, _part) do
    input |> Input.stream!() |> Grid.parse_lines(fn c -> {:ok, <<c>>} end) |> elem(0)
  end

  def part_one(full_grid) do
    regions = compute_regions(full_grid)

    regions
    |> Enum.map(&cost_p1/1)
    |> Enum.sum()
  end

  def part_two(full_grid) do
    regions = compute_regions(full_grid)

    regions
    |> Enum.map(&cost_p2/1)
    |> Enum.sum()
  end

  defp compute_regions(grid) do
    {regions, rest} =
      Enum.reduce(grid, {[], grid}, fn {pos, tag}, {regions, rest_grid} ->
        case Map.fetch(rest_grid, pos) do
          :error ->
            {regions, rest_grid}

          {:ok, _} ->
            {region, rest_grid} = take_region(rest_grid, tag, [pos])
            {[region | regions], rest_grid}
        end
      end)

    0 = map_size(rest)

    regions
  end

  defp take_region(mut_grid, tag, open, closed \\ [])

  defp take_region(mut_grid, tag, [pos | open], closed) do
    neighs = pos |> Grid.cardinal4() |> Enum.filter(fn xy -> xy not in closed && Map.get(mut_grid, xy) == tag end)
    take_region(mut_grid, tag, neighs ++ open, [pos | closed])
  end

  defp take_region(mut_grid, tag, [], closed) do
    region = Map.new(closed, &{&1, tag})

    mut_grid = Map.drop(mut_grid, closed)
    {region, mut_grid}
  end

  defp cost_p1(region) do
    area(region) * perimeter(region)
  end

  defp area(region) do
    map_size(region)
  end

  defp perimeter(region) do
    keys = Map.keys(region)

    Enum.reduce(region, 0, fn {xy, _}, acc ->
      borders = xy |> Grid.cardinal4() |> Enum.count(fn neigh -> neigh not in keys end)
      acc + borders
    end)
  end

  defp cost_p2(region) do
    area(region) * count_sides(region)
  end

  defp count_sides(region) do
    poses = Map.keys(region)

    individual_sides =
      Enum.flat_map(poses, fn pos ->
        [
          {:up, Grid.translate(pos, :n)},
          {:down, Grid.translate(pos, :s)},
          {:left, Grid.translate(pos, :w)},
          {:right, Grid.translate(pos, :e)}
        ]
        |> Enum.filter(fn {_, xy} -> xy not in poses end)
      end)

    sides_by_direction =
      Enum.group_by(
        individual_sides,
        fn
          # group sides by their orientation and level
          {:up, {_x, y}} -> {:up, y}
          {:down, {_x, y}} -> {:down, y}
          {:right, {x, _y}} -> {:right, x}
          {:left, {x, _y}} -> {:left, x}
        end,
        fn
          # keep side value by orientation and cross direction to know if their
          # are touching
          {:up, {x, _y}} -> x
          {:down, {x, _y}} -> x
          {:right, {_x, y}} -> y
          {:left, {_x, y}} -> y
        end
      )

    Enum.reduce(sides_by_direction, 0, fn {{_direction, _level}, cross_coords}, acc ->
      distinct_sides(cross_coords) + acc
    end)
  end

  defp distinct_sides(cross_coords) do
    [h | cross_coords] = Enum.sort(cross_coords)
    distinct_sides(cross_coords, h, 0)
  end

  defp distinct_sides([h | t], prev, acc) when h == prev + 1 do
    # No need to accumulate the whole side cross coordinates, we can just keep
    # the previous nuber
    distinct_sides(t, h, acc)
  end

  defp distinct_sides([h | t], _prev, acc) do
    distinct_sides(t, h, acc + 1)
  end

  defp distinct_sides([], _prev, acc) do
    acc + 1
  end
end

BEAM capability of guards like when h == prev + 1 is really neat.

1 Like

For part 2, I expanded every border tile to 1~4 entries depending on which sides the fence is on, like {{i, j}, :up} and {{i, j}, :left}, and then

  1. find and expand all border tiles
  2. pick the smallest (top-left) entry
  3. eliminate the whole border containing that entry
  4. repeat step 2~3 until the set of border entries is empty

Here’s my solution:

1 Like

This was a fun one! Took a bit of thinking outside the box (or maybe I didn’t need to think outside the box, I haven’t looked at anyone else’s solutions yet, I’ll do that now!)

The core of mine is the group_connecting function, which takes a list of coordinates and groups them together if they’re adjacent. This is how I figure out where all the regions are, and also how I split up all the borders into sides.

Name                     ips        average  deviation         median         99th %
day 12, part 1          7.16      139.70 ms     ±1.82%      139.22 ms      144.95 ms
day 12, part 2          6.84      146.22 ms     ±1.32%      145.82 ms      151.25 ms
2 Likes

I said I was going to take a break today, but I’m too addicted…

For part 1, I computed the perimeter at the same time as finding the regions, which meant part 2 was a massive troll because I had to go back and walk around the edges to find the sides anyway.

For part 2, I’m not happy with the duplication for the four directions (like day 4), but I’ve spent long enough on this.

The times are 24.371ms for part 1, and 46.861ms for part 2.

I am going to take a break for a few days from tomorrow, not sure if I’ll be back so just in case it’s been fun seeing everyone’s approaches so far!

1 Like

I appreciate the solutions others post, it’s helped me learn a lot :heart:

I used a recursive function to build a set of region positions, then iterated over individual fences, building up a map of %{fenceStart => fenceEnd, fenceEnd => fenceStart}.

Pattern matching on maps is really clean.

2 Likes

My solution solves parts 1 and 2 simultaneously. For part 2 I just count the number of corners, both inside and outside. That’s equivalent to the number of sides.

AOC 2024 Day 12 Content 0
Part 1: 1549354 in 43.439ms
Part 2: 937032 in 43.241ms
3 Likes

:exploding_head:

2 Likes

yeah … I feel dumb now :smiley:

this task is starting to annoy me. Its simple to get wall count … it was not so simple to get side count

anyone who can kick me in the right direction ? i tried to keep the code readable in the domain of the problem. I think ill read the comments here … its time …

haha … no idea what your doing … the variable names and functions doesnt speak to me :slight_smile: When i do AOC I make code with as good as quality i would do at work, so i will remember after 1 year what the code does … :rofl: But terse can also be good :wink: good work

1 Like

I verbosified it if you’re still interested.

1 Like

This one is utterly unreadable after all the golfing.

LOC: 37

defmodule Aoc2024.Day12 do
  import Enum
  import String, only: [split: 3]
  def part1(file), do: main(file, &perimeter/1)
  def part2(file), do: main(file, &num_sides/1)
  def area(region), do: length(region)
  def perimeter(region), do: count(segment_counts(region), fn {_, count} -> count == 1 end)
  def segment_counts(region), do: frequencies(flat_map(region, &s/1))
  def s(p), do: for(q <- [p], r <- g(p), do: {q, r}) ++ for(q <- g(p), r <- [inc(p)], do: {q, r})
  def inc({x, y}), do: {x + 1, y + 1}
  def g({x, y}), do: [{x + 1, y}, {x, y + 1}]
  def t1?({a, b}, {c, d}), do: (a == c and abs(d - b) == 1) or (b == d and abs(c - a) == 1)
  def t2?(meets), do: fn {a, b}, {c, d} -> t3?(a, d, meets) or t3?(b, c, meets) end
  def t3?(p, q, meets), do: p == q and not (p in meets or q in meets)

  def main(file, side_fun) do
    rows = file |> File.read!() |> split("\n", trim: true) |> map(&split(&1, "", trim: true))
    grid = for {row, i} <- with_index(rows), {x, j} <- with_index(row), into: %{}, do: {{i, j}, x}
    rs = for {_, r} <- group_by(grid, &elem(&1, 1), &elem(&1, 0)), do: contiguous(r, &t1?/2)
    sum_by(rs, fn lr -> sum_by(lr, &(area(&1) * side_fun.(&1))) end)
  end

  def contiguous([h | t], fun?) do
    reduce(t, [[h]], fn x, ys ->
      {touches, disjoint} = split_with(ys, fn y -> any?(y, &fun?.(&1, x)) end)
      [[x] ++ List.flatten(touches)] ++ disjoint
    end)
  end

  def num_sides(region) do
    s = segment_counts(region) |> filter(fn {_, count} -> count == 1 end) |> map(&elem(&1, 0))
    %{true: v, false: h} = group_by(s, fn {{x1, _}, {x2, _}} -> x1 == x2 end)
    p_counts = (v ++ h) |> flat_map(fn {{a, b}, {c, d}} -> [{a, b}, {c, d}] end) |> frequencies()
    meets = p_counts |> filter(fn {_, count} -> count > 2 end) |> map(&elem(&1, 0))
    count(contiguous(v, t2?(meets))) + count(contiguous(h, t2?(meets)))
  end
end
2 Likes

I’ve read about a simple concept for calculating corners in r/adventofcode. It checks for convex and concave corners for each direction.

def count_corners(garden, pos) do
  plant = at(garden, pos)

  [
    {up(pos), left(pos), left(pos) |> up()},
    {up(pos), right(pos), right(pos) |> up()},
    {down(pos), left(pos), left(pos) |> down()},
    {down(pos), right(pos), right(pos) |> down()}
  ]
  |> Enum.count(fn {pos1, pos2, diagonal} ->
    val1 = at(garden, pos1)
    val2 = at(garden, pos2)
    diagonal_val = at(garden, diagonal)

    # Convex corner: both adjacents are different from group
    convex_corner = val1 != plant and val2 != plant

    # Concave corner: both adjacents match group AND diagonal is different
    concave_corner = val1 == plant and val2 == plant and diagonal_val != plant

    convex_corner or concave_corner
  end)
end

Here is my full solution:

1 Like

behold, i bring code that i am highly ashamed of:

truly attrocious performance

Name           ips        average  deviation         median         99th %
p2           44.02       22.72 ms     ±4.79%       22.62 ms       25.43 ms
p1            4.37      228.70 ms     ±3.14%      227.56 ms      242.19 ms

edit: omg i made the code uglier and faster

Name           ips        average  deviation         median         99th %
p1           93.85       10.66 ms     ±7.19%       10.61 ms       12.65 ms
p2           45.60       21.93 ms     ±4.21%       21.87 ms       24.31 ms

Got part 1 first the naive cartesian way, but didn’t hang around long enough for the input to evaluate. Clearly incorrect for the problem space.

#!/usr/bin/env elixir

defmodule Day12.Part1 do
  defp parse(str) do
    [row | _rows] =
      rows =
      str
      |> String.split("\n", trim: true)
      |> Enum.map(&to_charlist/1)

    height = Enum.count(rows)
    length = Enum.count(row)

    graph = :digraph.new([:acyclic])

    for y <- 0..(height - 1) do
      for x <- 0..(length - 1) do
        value = rows |> Enum.at(y) |> Enum.at(x)
        :digraph.add_vertex(graph, {x, y}, value)
        [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
        |> Enum.filter(
          fn {n_x, n_y} = neighbor ->
            on_board?(neighbor, height, length) and rows |> Enum.at(n_y) |> Enum.at(n_x) == value
          end
        )
        |> Enum.each(fn neighbor -> :digraph.add_edge(graph, {x, y}, neighbor) end)
      end
    end

    :digraph_utils.components(graph)
  end

  defp on_board?({x, y}, height, length) when x < 0 or x >= length or y < 0 or y >= height,
    do: false

  defp on_board?(_pair, _height, _length), do: true

  defp area(contiguous_region) do
    contiguous_region |> Enum.count()
  end

  defp perimeter({x, y} = _point, %MapSet{} = contiguous_region) do
    [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
    |> Enum.map(fn neighbor ->
      if MapSet.member?(contiguous_region, neighbor), do: 0, else: 1
    end)
    |> Enum.sum()
  end

  defp perimeter(contiguous_region) do
    contiguous_region
    |> Enum.map(&perimeter(&1, contiguous_region))
    |> Enum.sum()
  end

  defp fence_cost([point|_points] = contiguous_region) when is_tuple(point) do
    area = area(contiguous_region)
    perimeter = perimeter(MapSet.new(contiguous_region))
    area * perimeter
  end

  defp fence_cost([region|_regions] = contiguous_regions) when is_list(region) do
    contiguous_regions
    |> Enum.map(&fence_cost(&1))
    |> Enum.sum()
  end

  def solve() do
    File.read!("lib/advent_of_code/year/2024/day/12/input.txt")
    |> parse()
    |> fence_cost()
    |> IO.puts()
  end
end

Day12.Part1.solve()

Switched it up by trying out :digraph. Once I figured out that the perimeter could be calculated without the rest of the map, it was a piece of cake.

Still working on part 2.

Here’s my Day 12, basic flood fill whilst counting edges for Part 1, using an ETS table to track visited squares (as I’m learning ETS also).

Part 2, realised that’s number of sides == number of corners, so counting covex and concave corners, so just added that to the Part 1 solution, and after some head scratching (and graph paper) caught the cases and got the answer.

If I can get through Part 1 tomorrow I’ll be happy, as that’s further than I got last year!

Solution for 2024 day 12
part_one: 1457298 in 68.1ms
part_two: 921636 in 67.28ms
defmodule Aoc2024.Solutions.Y24.Day12 do
  alias AoC.Input

  def parse(input, _part) do
    Input.read!(input)
    |> String.split("\n", trim: true)
  end

  def part_one(problem) do
    :ets.new(:store, [:named_table, :public, :ordered_set, :protected])
    build_matrix(problem)

    plots = :ets.tab2list(:store)

    result =
      Enum.reduce(plots, 0, fn {{x, y}, _req, _}, acc ->
        case :ets.lookup(:store, {x, y}) do
          [] ->
            acc

          [{_, req_type, _visited} = plot] ->
            case build_gardens([plot], req_type) do
              {0, 0, 0} ->
                acc

              {plot, fence, _} ->
                acc + plot * fence
            end
        end
      end)

    :ets.delete(:store)
    result
  end

  def part_two(problem) do
    :ets.new(:store, [:named_table, :public, :ordered_set, :protected])
    build_matrix(problem)

    plots = :ets.tab2list(:store)

    result =
      Enum.reduce(plots, 0, fn {{x, y}, _req, _}, acc ->
        case :ets.lookup(:store, {x, y}) do
          [] ->
            acc

          [{_, req_type, _visited} = plot] ->
            case build_gardens([plot], req_type) do
              {0, 0, 0} ->
                acc

              {plot, _fence, corners} ->
                acc + plot * corners
            end
        end
      end)

    :ets.delete(:store)
    result
  end

  def build_gardens([], _req_type), do: {0, 1, 0}

  def build_gardens([{{x, y}, type, visited}], req_type) do
    cond do
      type == req_type and visited == false ->
        :ets.insert(:store, {{x, y}, req_type, true})

        corner = check_for_corners(x, y, type)

        {south_plot, south_fence, south_corners} =
          build_gardens(:ets.lookup(:store, {x, y + 1}), req_type)

        {north_plot, north_fence, north_corners} =
          build_gardens(:ets.lookup(:store, {x, y - 1}), req_type)

        {west_plot, west_fence, west_corners} =
          build_gardens(:ets.lookup(:store, {x - 1, y}), req_type)

        {east_plot, east_fence, east_corners} =
          build_gardens(:ets.lookup(:store, {x + 1, y}), req_type)

        {south_plot + north_plot + west_plot + east_plot + 1,
         south_fence + north_fence + west_fence + east_fence,
         south_corners + north_corners + west_corners + east_corners + corner}

      type == req_type and visited == true ->
        {0, 0, 0}

      type != req_type ->
        {0, 1, 0}
    end
  end

  def check_for_corners(x, y, type) do
    n = is_requested_type?(x, y - 1, type)
    ne = is_requested_type?(x + 1, y - 1, type)
    e = is_requested_type?(x + 1, y, type)
    se = is_requested_type?(x + 1, y + 1, type)
    s = is_requested_type?(x, y + 1, type)
    sw = is_requested_type?(x - 1, y + 1, type)
    w = is_requested_type?(x - 1, y, type)
    nw = is_requested_type?(x - 1, y - 1, type)

    check_for_corner(n, ne, e) + check_for_corner(e, se, s) + check_for_corner(s, sw, w) +
      check_for_corner(w, nw, n)
  end

  def check_for_corner(n, ne, e) do
    cond do
      n == false and e == false ->
        1

      n == true and ne == false and e == true ->
        1

      true ->
        0
    end
  end

  def is_requested_type?(x, y, type) do
    case :ets.lookup(:store, {x, y}) do
      [{_, req_type, _}] ->
        req_type == type

      [] ->
        false
    end
  end

  def build_matrix(grid) do
    Enum.with_index(grid)
    |> Enum.each(fn row ->
      build_matrix_row(row)
    end)
  end

  def build_matrix_row({row, row_index}) do
    row
    |> String.graphemes()
    |> Enum.with_index()
    |> Enum.each(fn {char, col_index} ->
      :ets.insert(:store, {{col_index, row_index}, char, false})
    end)
  end
end

I created a grid struct yesterday for day 10’s challenge and spent a decent amount of my time adding to it to solve this one. Definitely going to have to implement reduce for it if we keep getting more of these.

My solution today feels much more verbose than it probably could be, but it runs in under 100 ms.

require Grid

defmodule Aoc2024.Day12 do
  @moduledoc false

  def part1(file) do
    get_input(file)
    |> assign_plots()
    |> fence_price1()
  end

  defp get_input(file) do
    File.read!(file)
    |> Grid.new(fn v -> v end)
  end

  defp assign_plots(grid) do
    for y <- 0..grid.last_y, x <- 0..grid.last_x do
      {x, y}
    end
    |> Enum.reduce({grid, 0}, fn position, {acc, plot_id} ->
      v = Grid.at(acc, position)

      if is_integer(v) do
        {acc, plot_id}
      else
        {explore_plot(acc, position, v, plot_id), plot_id + 1}
      end
    end)
    |> Tuple.to_list()
    |> List.first()
  end

  # Walk through the region from the starting point finding all points within the same plot.
  # Return an updated grid with all points within the plot updated to have the value of the given id.
  defp explore_plot(grid, position, initial, plot_id) do
    if is_integer(Grid.at(grid, position)) do
      grid
    else
      #   IO.inspect("{#{x},#{y}} #{initial} #{plot_id}")
      new = Grid.put(grid, position, plot_id)

      new
      |> Grid.neighbors(position)
      |> then(&Grid.filter(new, &1, fn v -> v == initial end))
      |> Enum.reduce(new, fn neighbor, acc ->
        explore_plot(acc, neighbor, initial, plot_id)
      end)
    end
  end

  defp fence_price1(grid) do
    counts = {%{}, %{}}

    {areas, perimeters} =
      for y <- 0..grid.last_y, x <- 0..grid.last_x do
        {x, y}
      end
      |> Enum.reduce(counts, fn position = {x, y}, {areas, perimeters} ->
        plot_id = Grid.at(grid, position)
        areas = Map.update(areas, plot_id, 1, &(&1 + 1))

        [{1, 0}, {0, 1}, {0, -1}, {-1, 0}]
        |> Enum.map(fn {dx, dy} -> {x + dx, y + dy} end)
        |> Enum.reduce({areas, perimeters}, fn neighbor, {areas, perimeters} ->
          if plot_id == Grid.at(grid, neighbor) do
            {areas, perimeters}
          else
            {areas, Map.update(perimeters, plot_id, 1, &(&1 + 1))}
          end
        end)
      end)

    Map.keys(areas)
    |> Enum.map(fn plot_id ->
      Map.get(areas, plot_id) * Map.get(perimeters, plot_id)
    end)
    |> Enum.sum()
  end

  def part2(file) do
    get_input(file)
    |> assign_plots()
    |> fence_price2()
  end

  defp fence_price2(grid) do
    areas = areas(grid)
    region_sides = region_sides(grid)

    Map.keys(areas)
    |> Enum.map(fn plot_id ->
      Map.get(areas, plot_id) * Map.get(region_sides, plot_id)
    end)
    |> Enum.sum()
  end

  defp areas(grid) do
    areas = %{}

    for y <- 0..grid.last_y, x <- 0..grid.last_x do
      {x, y}
    end
    |> Enum.reduce(areas, fn position, areas ->
      plot_id = Grid.at(grid, position)
      # Map.update(areas, plot_id, MapSet.new([position]), &(MapSet.put(&1, position)))
      Map.update(areas, plot_id, 1, &(&1 + 1))
    end)
  end

  defp region_sides(grid) do
    sides = %{}

    for y <- 0..grid.last_y, x <- 0..grid.last_x do
      {x, y}
    end
    |> Enum.reduce(sides, fn position, sides ->
      plot_id = Grid.at(grid, position)
      fsc = fence_side_cost(grid, position)
      Map.update(sides, plot_id, fsc, &(&1 + fsc))
    end)
  end

  defp fence_side_cost(grid, position) do
    n = named_neighbors(position)
    left_n = named_neighbors(n.left)
    above_n = named_neighbors(n.above)

    above_below_cost(grid, position, n.above, n.left, left_n.above) +
      above_below_cost(grid, position, n.below, n.left, left_n.below) +
      left_right_cost(grid, position, n.left, n.above, above_n.left) +
      left_right_cost(grid, position, n.right, n.above, above_n.right)
  end

  defp above_below_cost(grid, pos, ab, left, left_ab) do
    if fence_between(grid, pos, ab) and
         (fence_between(grid, pos, left) or same_plot(grid, left, left_ab)) do
      1
    else
      0
    end
  end

  defp left_right_cost(grid, pos, lr, above, above_lr) do
    if fence_between(grid, pos, lr) and
         (fence_between(grid, pos, above) or same_plot(grid, above, above_lr)) do
      1
    else
      0
    end
  end

  defp same_plot(grid, position1, position2) do
    Grid.at(grid, position1) == Grid.at(grid, position2)
  end

  defp fence_between(grid, position1, position2) do
    Grid.at(grid, position1) != Grid.at(grid, position2)
  end

  defp named_neighbors({x, y}) do
    %{left: {x - 1, y}, right: {x + 1, y}, above: {x, y - 1}, below: {x, y + 1}}
  end
end

You may be ashamed, but this helped me connect the dots for the value of creating doctests for the key helper functions. It seems like a nice middleground to keep my tests focused on the output but still make it easy to check my work step my step as I build up the code.

1 Like

I created a grid struct

If I can give some advice, do not use a special data structure for your grid.

My Grid module is a bunch of helpers, but the data structure to represent the grid is just a map of {x, y} => value. It makes it much more direct to use in all the crazy things AoC makes us do, because it works with all the standard library functions like Enum, Stream, with some libraries, etc.

Resist the urge to make everything its own type. Like the :queue module type is just a tuple of two lists. That makes debugging and implement special things easier.

1 Like

My grid struct is a wrapper around a simple map as you described. The only extra is storing the last x & y values to make it easy to generate every possible position. Which as I type that I realized I should just be doing Map.keys() for that. Too much coding, not enough thinking (or sleep)!