Advent of Code 2024 - Day 14

This was a fun day.

I initially solved part 2 by printing out a map with the robots after each second. I then did some creative grepping to find the Christmas tree. Knowing what the Christmas tree looks like, I could create a unique pattern to use when searching for the Christmas tree programmatically.

The combined running time for both parts is 2.3 seconds.

https://github.com/bjorng/advent-of-code/blob/main/2024/day14/lib/day14.ex

Yeah I feel like a lot of people did things short ways (look for all unique positions? Which works somehow?) and I did lots of trial and error browsing output grids to find the tree, and then work backwards to write code to find the tree. If I knew what the tree looked like from the get-go, it would have been a lot simpler!

image602×1018 14.9 KB

(that’s what it looks like)

My code: advent_of_code/lib/y2024/day14.ex at main · sevenseacat/advent_of_code · GitHub

Name                     ips        average  deviation         median         99th %
day 14, part 1        516.12        1.94 ms     ±8.66%        1.85 ms        2.30 ms
day 14, part 2          1.41      707.27 ms     ±0.37%      707.76 ms      710.36 ms

Can you give an order of magnintude for the seconds?

My part 1 is correct, and I see some kind of horizontal or verical patterns when I print the map but nothing that resembles an actual tree.

Edit alright found it

Yesss work with those patterns, that’s how I did it. Look for the tick numbers (number of seconds elapsed) that cause those patterns. FInd the patterns of the tick numbers. Extrapolate upwards. (It’s not a massive number)

With my input, the tree was found within the first 10000 seconds.

Thank you guys. I found it by searching contiguous cells and it worked :). I’m not sure if I want to implement the pattern search because you need to know the tree shape already.

Edit: Alright, did it anyway, looking for the tip of the tree is 400ms

 Enum.reduce_while(1..10000, nil, fn sec, _ ->
      positions = Enum.map(robots, &simulate(&1, room_dimensions, sec))
      map = Map.new(positions, &{&1, true})

      if Enum.all?([{43, 57}, {42, 58}, {43, 58}, {44, 58}], &Map.has_key?(map, &1)) do
        {:halt, sec}
      else
        {:cont, nil}
      end
    end)
  end

Also it was very slow because of my modulo function:

  defp mod(0, _), do: 0
  defp mod(n, m) when n < 0, do: mod(m + n, m)
  defp mod(n, m), do: rem(n, m)

Looking at the implementation I can see why But today I learnt Integer.mod/2 exists!

Edit2: since the slow thing was the modulo, the map is actually slower. this is around 140ms:

    Enum.reduce_while(1..10000, nil, fn sec, _ ->
      positions = Enum.map(robots, &simulate(&1, room_dimensions, sec))

      if Enum.all?([{43, 57}, {42, 58}, {43, 58}, {44, 58}], & &1 in positions) do
        {:halt, sec}
      else
        {:cont, nil}
      end
    end)

Edit this will not work for any input if not everyone has the tree in the same position. I don’t know if it is the case.

I got the answer to part 2. In my case, I dumped the grid and noticed:

• The output after 27 seconds looked suspicious
• It repeated again after 101 seconds

So I just checked every 101 second jump before finding the tree (actually I went past it due to spamming the return key and had to scroll up to get the index ). Thankfully it wasn’t too far in. I can’t find the motivation to write the code to search for the tree though

With all the fuss about people using AI this year, and the interesting nature of part 2, I thought I’d feed today’s problem into ChatGPT and see what it came up with.

It solved part 1 instantly, and more efficiently than I solved it (no need to loop 100 times to figure out where things are after 100 seconds, multiply the velocity by 100 and calculate once).

It failed on part 2 - it had the interesting idea to look for a bounding box of the robots that was less than a given size, to represent the robots converging together to make a shape, but that doesn’t work because not all of the robots are involved in making the shape. I’m not super skilled at prompting but nothing I’m telling it seems to budge it from that algorithm (despite including some density-calculation functionality), so of course it blows right past the correct answer and loops infinitely.

Super interesting though!

This was the answer to a previous year though, which it has surely been trained on.

That makes sense! And is probably why it doesn’t behave the same way this year

Though the code might still work, if the density function was altered a bit…

edit: Yep, removing the bounding box calculation and using just a density calculation works perfectly. This is the code it generated:

It takes just over a second to run on my machine and gives the same answer for my real input, as my code does.