Advent of Code 2024 - Day 12

Learning Questions & Discussions Coding Challenges
,
21

The parse function for my grid returns {grid, {x_min,x_max,y_min,y_max}} because when parsing you traverse the whole thing.

If you want your grid to have that {x_max,y_max} coordinates and expect it to be correct then you will have to compute it whenever you put in the grid. There is a decent amount of puzzles that require to expand the grid, or to take only a sub part of it like today.

So I would avoid counting on those struct fields to always be up to date.

Also another tip that I do all the time, I name min and max to “a” and “o” (alpha/omega), like xa, xo instead of x_min, x_max … just because the “x” in “max” makes it such a pain to mass rename or do multi-cursor stuff when editing :smiley:

22

There is a decent amount of puzzles that require to expand the grid, or to take only a sub part of it like today.

This is my first time doing AOC so that’s a great tip.

What really help me get unstuck today was learning how to implement the Inspect protocol for debugging. Being able to easily see the example grid step by step is so beneficial. Loving how easy it is to implement things like that in Elixir with minimal code.

1 Like
23

finally managed to understand the convex and concave solution and extracted it from your solution into my own. I have never done stuff like this, so this was totally new to me.

as you can see i just mapped my list of positions into a map, to adjust for the count_corners function.

but you had x and y flipped though :wink: i flipped them back :stuck_out_tongue:

PS! What would be nice though … is if anyone had some learning material or visualization for convex and concave checks in a grid.

1 Like
24

I put the puzzles down for a bit yesterday and decided to get back to it this morning.

Here’s my pass at part 2 after reading up a bit here:

#!/usr/bin/env elixir

defmodule Day12.Part2 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 corner?({side_a, side_b, diagonal}, contiguous_region) do
    sides = [side_a, side_b]

    convex? =
      sides
      |> Enum.all?(&(not MapSet.member?(contiguous_region, &1)))

    concave? =
      sides
      |> Enum.all?(&MapSet.member?(contiguous_region, &1)) and
        not MapSet.member?(contiguous_region, diagonal)

    convex? or concave?
  end

  defp sides({x, y} = _point, %MapSet{} = contiguous_region) do
    right = {x + 1, y}
    left = {x - 1, y}
    below = {x, y + 1}
    above = {x, y - 1}
    above_left = {x - 1, y - 1}
    above_right = {x + 1, y - 1}
    below_left = {x - 1, y + 1}
    below_right = {x + 1, y + 1}

    [
      {above, left, above_left},
      {above, right, above_right},
      {below, right, below_right},
      {below, left, below_left}
    ]
    |> Enum.map(fn triple ->
      if corner?(triple, contiguous_region), do: 1, else: 0
    end)
    |> Enum.sum()
  end

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

  defp fence_cost([point | _points] = contiguous_region) when is_tuple(point) do
    area = area(contiguous_region)
    sides = sides(MapSet.new(contiguous_region))
    area * sides
  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.Part2.solve()

I had figured out the equality of sides to corners, but went in totally the wrong direction for calculating them at first. I may have also read something a while back about corner checking- felt like it rang a bell once I grasped it.

1 Like
25

@Flo0807 is this correct counting with convex and concave ?

A  A  A  A
B  B  C2 D
B  B  C2 C2
E  E  E  C2

the top c (2,1) has A+B convex and A+D as convex, so 2
the next c (2,2) has B+E convex and D concave, so 2
the top right c (3,2) has E concave and D+nil convex, so 2
the bottom right c (3,3) has E+nil convex and nil+nil convex, so 2

this equals 8?

but the big question is, where do people get this info from? where was it learned ?

1 Like
26

For part 2 I implemented a neat maze walking algorithm. Unfortunately, it only counted the outer fences and not fences around enclosed regions. My attempts to handle the enclosed regions didn’t produce the correct answer.

I went back to the drawing board and ended up with this solution:

1 Like
27

anyway i asked perplexity

https://www.perplexity.ai/search/i-have-recently-learned-about-LLX8S.QhQkuqPO1FoMe2RQ

Im very stubborn on not letting such knowledge pass me by :rofl: the question is both showing that i now fully understand it, its corner counting. And perplexity sheds some light on the background of the theory

A healthy combination of OCD and perseverance lead to me to the final refactor: advent_of_code/lib/2024/day_12/Part1_2.ex at master · jarlah/advent_of_code · GitHub (next up figure out what the others did, if it was not corner counting)

28

im now trying to dig into the alternative approaches to convex/concave corner counting and your part2 cost calculation seems a good candidate. Or maybe its hiding the same convex/concave in the code ?

for ex this

    sides = region
    |> Enum.flat_map(fn plot ->
      plot
      |> adjacent_squares
      |> Enum.filter(&fence?(grid, type, &1))
      |> Enum.map(fn square ->
        diff = sub(plot, square)
        axis = if elem(diff, 1) === 0, do: 0, else: 1
        other_axis = rem(axis + 1, 2)
        {{diff, elem(plot, axis)}, elem(plot, other_axis)}
      end)
    end)

it goes through all adjacent squares and subtracts the square (x,y) from the plot (x,y) to get a diff (x, y). Then it sets axis variable to 0 if y from diff is 0, else 1. Then it sets other_axis variable to the remainder of dividing axis (0 or 1) + 1 by 2, which can result in 2 or 1. Then end result is {{diff, elem(plot, 0 or 1)}, elem(plot, 1 or 2)} which is basically either {{diff, x}, x} or {{diff, y}, x}. Then we need to find out what this means. it returns which axis is … different? EDIT: my explanation here might be wrong, it just shows how my mind is trying to read the code :smiley:

1 Like
29

The counting looks good!

but the big question is, where do people get this info from? where was it learned ?

Like I said, I got this vector counting from a reddit post. I guess it’s the kind of math you learn when you dive into grids, 2D spaces and geometry.

1 Like
30

ok im guess im going down the long road. If i cant solve it i find someone who has and dissects it to its fine grained atoms :wink:

31

If you struggle with corner counting I suggest to look at my solution (1st post in thread). It thinks it’s straightforward to implement.

Here is the additional code not shared from the Grid module:


  def cardinal4(xy) do
    [
      translate(xy, :n),
      translate(xy, :s),
      translate(xy, :w),
      translate(xy, :e)
    ]
  end

  def translate(xy, direction, n \\ 1)
  def translate({x, y}, :n, n), do: {x, y - n}
  def translate({x, y}, :s, n), do: {x, y + n}
  def translate({x, y}, :w, n), do: {x - n, y}
  def translate({x, y}, :e, n), do: {x + n, y}
1 Like
32

thanks :slight_smile: corner counting is good now :wink: Ill look at your example, but now im trying to find the non math way to do it. I might just go back to the drawing board :wink: Or, just skip it. I have learned enough :wink: btw done thanks for tolerating my grave digging :stuck_out_tongue: i found out btw that the alternative approach was way more complex and didnt work the same on small inputs vs complex inputs. So i dropped digging more into it (i always begins with the simplest example and get it to work for all inputs, so when i suddenly get discrepancy for a larger input, I havent solved it and scraps it)

1 Like
33

No, nothing’s hiding here. :smile:

My code connects all adjacent pieces of the fence. diff represents on which side of the plot the fence is located (above, below, left, or right). If the fence is above or below I want to group this plot with all plots on the same row, otherwise I want to group plots in the same column.

For example, take the e-shaped region in the puzzle descripton. Enum.group_by/3 will produce the following groups for the region of E plots:

%{
 {{-1, 0}, 0} => [1, 2, 3, 4],     # The fence below row 0, columns 1..4
  {{-1, 0}, 2} => [1, 2, 3, 4],    # The fence below row 2, columns 1..4
  {{-1, 0}, 4} => [0, 1, 2, 3, 4], # The fence below row 4
  {{0, -1}, 0} => [1, 3],          # The fences right of column 0, rows 1 and 3
  {{0, -1}, 4} => [0, 2, 4],       # The fences right of column 4, rows, 0, 2, 4
  {{0, 1}, 0} => [0, 1, 2, 3, 4],
  {{1, 0}, 0} => [0, 1, 2, 3, 4],
  {{1, 0}, 2} => [1, 2, 3, 4],
  {{1, 0}, 4} => [1, 2, 3, 4]
}

The lists with non-consecutive numbers ([1, 3] and [0, 2, 4]) need to be split as each such list represents more than one side. After splitting we have the following lists:

[
  [1, 2, 3, 4],
  [1, 2, 3, 4],
  [0, 1, 2, 3, 4],
  [1],
  [3],
  [0],
  [2],
  [4],
  [0, 1, 2, 3, 4],
  [0, 1, 2, 3, 4],
  [1, 2, 3, 4],
  [1, 2, 3, 4]
]

There are now 12 sublists, where each sublist represents a side in the fence. By counting the number sublists, we get the number of sides.

2 Likes
34

i think the chunk_while threw me off the bus maybe … other than that your explanation makes perfect sense when you say it like this :slight_smile:

1 Like
35

My solution is not math, it’s exactly the same as Bjorn’s :slight_smile:

2 Likes
36

looked at it. I think i need to look more closely at it. But looks nicer. No wierd chunk while :smiley:

Unrelated segway:
i have been recently thinking about making an umbrella project in mix with a shared common project and sub projects for all years, and sub sub projects for all days … then they are sort of standalone … and if one day cant use the standard tooling or some depenency … i can just break it loose from the umbrella for that specific day

1 Like
37

ey … what … i can actually use normal function overloading in elixir ??

  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

this got me spinning ! learned something new! yay no more new names for functions just because i need to do recursion. Makes sense though distinct_sides/1 and distinct_sides/3 ARE in fact different. Cognitive overhead though … :smiley:

but seriously i am actually understanding whats going on with your code.

1 Like
38

Yes despite the exact same name, because of the different arity, those functions in Elixir and Erlang are totally different functions that can have their own @spec, @doc, one could be exported while the other remains private, etc.

i have been recently thinking about making an umbrella project in mix with a shared common project and sub projects for all years, and sub sub projects for all days

You do you but honestly this looks like pain :smiley:
I really like to be able to change some stuff in my shared modules and just call mix test to run all solutions for all years i’ve done without thinking about project structure.

2 Likes
39

I struggled so much on the past few days that I’m proud this one went smoothly.

I confess that I read before coding anything that counting corners was a good strategy :bulb:

Part 1:

defmodule Advent.Y2024.Day12.Part1 do
  defmodule Region do
    defstruct [:plant, :area, :perimeter, :sides, plots: MapSet.new()]
  end

  def run(puzzle) do
    puzzle
    |> parse()
    |> find_regions()
    |> Enum.map(&compute_area_and_perimeter/1)
    |> Enum.map(&(&1.area * &1.perimeter))
    |> Enum.sum()
  end

  def parse(puzzle) do
    for {row, y} <- puzzle |> String.split("\n") |> Enum.with_index(),
        {plant, x} <- row |> String.graphemes() |> Enum.with_index(),
        into: %{},
        do: {{x, y}, plant}
  end

  def find_regions(farm) do
    Enum.reduce(farm, {[], MapSet.new()}, fn {{x, y}, plant}, {regions, visited} ->
      if MapSet.member?(visited, {x, y}) do
        {regions, visited}
      else
        region = explore(farm, {x, y}, %Region{plant: plant})
        {[region | regions], MapSet.union(visited, MapSet.new(region.plots))}
      end
    end)
    |> elem(0)
  end

  def explore(farm, {x, y}, region = %Region{plant: plant, plots: plots}) do
    region = %Region{region | plots: MapSet.put(plots, {x, y})}

    for {nx, ny} <- [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}], reduce: region do
      region ->
        if Map.get(farm, {nx, ny}) == plant and not MapSet.member?(plots, {nx, ny}) do
          explore(farm, {nx, ny}, region)
        else
          region
        end
    end
  end

  defp compute_area_and_perimeter(region = %Region{plots: plots}) do
    fences =
      for {x, y} <- plots,
          {nx, ny} <- [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}],
          not MapSet.member?(plots, {nx, ny}),
          do: true

    %Region{region | area: MapSet.size(plots), perimeter: length(fences)}
  end
end

Part 2:

defmodule Advent.Y2024.Day12.Part2 do
  alias Advent.Y2024.Day12.Part1
  alias Advent.Y2024.Day12.Part1.Region

  import MapSet, only: [member?: 2]

  def run(puzzle) do
    puzzle
    |> Part1.parse()
    |> Part1.find_regions()
    |> Enum.map(&compute_area_and_sides/1)
    |> Enum.map(&(&1.area * &1.sides))
    |> Enum.sum()
  end

  defp compute_area_and_sides(region = %Region{plots: plots}) do
    corners =
      for {x, y} <- plots,
          [{d1x, d1y}, {d2x, d2y}, {d3x, d3y}] <- [
            [{-1, 0}, {-1, -1}, {0, -1}],
            [{0, -1}, {1, -1}, {1, 0}],
            [{1, 0}, {1, 1}, {0, 1}],
            [{0, 1}, {-1, 1}, {-1, 0}]
          ],
          [n1, n2, n3] = [{x + d1x, y + d1y}, {x + d2x, y + d2y}, {x + d3x, y + d3y}],
          (not member?(plots, n1) and not member?(plots, n3)) or
            (member?(plots, n1) and not member?(plots, n2) and member?(plots, n3)),
          do: true

    %Region{region | area: MapSet.size(plots), sides: length(corners)}
  end
end
40

made advancement to my setup

first i removed all input files and AOC descriptions and washed my git commit log.

then i moved every year into solutions directory and changed my mix task to generate actual mix projects that depend on a common mix project two levels above it

so now i have shared code in a common project with no umbrella :wink: and the parent project wont compile the code for the other projects since its not in the lib folder, it will only compile the mix task

1 Like