Advent of Code 2023 part 3

Days 11-15

Intro

As a reminder, if you wish to reference my solution, you can find all my solutions at https://github.com/abnew123/aoc2023 .

Day 11 (Cosmic Expansion)

This definitely harkened back to older AoCs. I love this type of problem as it really forces you to plan a setup that scales. The initial part 1 I had was actually expanding the universe (by inserting rows/columns in), but obviously when part 2 is to do that times a million it didn’t work. Instead, I stored empty column and rows, and added 999,999 each pair of galaxies that cross the empty row/column.

There’s some interesting big O ideas here. Prestoring a left and right number of empties can reduce the addition phase to O(n) as it becomes two scans. Probably the whole day can be done in O(n), but it’s already fast enough currently.

Day 12 (Hot Springs)

Big fan of the name play here with springs both referring to hot springs and mechanical springs. Brute force recursion handles part 1 fine, but part 2 definitely gets to scales where you need to wait a long time for it to finish (if it finishes at all). Great day to start with dynamic programming, but I personally went with a roughly equivalent approach of memoizing and going chunk by chunk rather than spring by spring. Basic idea is that if a group is 5,4,5 and you see a spring at the start, you can fast forward 5 cells and do a single check rather than try all 2^5 cases of possibilities for those 5 cells.

Day 13 (Point of Incidence)

This was definitely a day where my part 1 really set me up for failure. The only difference between the two parts is that part 1 looks for perfect reflections, and part 2 looks for off by one reflections, but it’s surprisingly hard to jam that in after the fact. I initially made copies of the grids where I flipped one point, but that had two major issues. One is that this meant a lot of false positives (the original 0 smudge solution returns for all 1 smudge grids), the other is that it’s extremely slow as you need to do many different flip tests. Instead, a much simpler way was the alter the original check to allow for some degree of non perfectness. Then it’s possible to change maxErrors from 0 to 1 and preserve everything else.

Day 14 (Parabolic Reflector Dish)

My best day of the bunch. Part 1 can be directly done, even with a very inefficient stone moving solution. Part 2 is too big to be directly brute forced, at least with my solution. Instead, the key is the find a repeat, as once stones hit the same positions after a cycle, the future is fully solved (as the cycle algorithm is deterministic). The big issue here funnily was the detection of that repeat. Incredibly, the default deepHashCode method Java uses for arrays actually had a hash collision for two of my stone setups. Never seen a hash collision before where I didn’t purposely induce it.

Day 15 (Lens Library)

Very cute problem, even if I wasn’t able to do it on time. Any CS student would immediately recognize the acronym of “Holiday ASCII String Helper”, and that’s indeed what’s done here. The day basically teaches you first what a hashing algorithm is, then how to use it for a hashmap. I always enjoyed similar problems in school (e.g. how to code an array list class in Java), so this was a refreshingly familar and fun one.

Times

To read this, left to right is “Day”, “Part 1 time”, “Part 1 rank”, “Part 1 global points”, “Part 2 time”, “Part 2 rank”, “Part 2 global points”.

Not a particularly good showing. Day 15 is whatever since I started late and had to pause between parts, but even most the days I started on time I placed outside the top 1000.

Run time:

Up to about 0.6 seconds total run time for the first 15 days. Day 12 part 2 in particular is a doozy as mentioned, it alone is about 25% of the runtime (~150ms).