Advent of Code 2023, Week 2
Advent of Code
Advent of Code is a yearly Advent calendar of programming puzzles that's run since 2015, with 25 two-part problems each year, each part rewarding one "star". For 2023, after completing every previous year, I'm making a weekly blog post about that week's problems, containing my thoughts on them and how I solved them; these, of course, will contain spoilers. For the code, see:
2023 ยท personal library.
This week went a lot better than last: I won 408 points from 8 different global leaderboard placements, compared to 0 in the first week, placing me in 64th place on the global leaderboard (as of December 11).
Day 5: If You Give A Seed A Fertilizer (puzzle, code)
Solve Times: 08:15 / #100, 1:09:54 / #1908
This problem was the first one where I won any points on the global leaderboard (albeit only one), although it was followed up by a terrible performance on part 2. In this problem, you're given "maps" from seed number to soil number, soil to fertilizer, and so on up to location, which have a list of start ranges and destination ranges, and map numbers in the former to the corresponding latter. In the first part, there are a list of given seed numbers, and the goal is to find the lowest location number for any of them; in the second, the seed numbers are instead ranges (with lengths on the order of hundreds of millions), but the goal is the same.
My solution for this problem is very unsatisfying, unfortunately. For the first part, I just implemented the maps in a naive way and ran each of the initial seed numbers through them, and took the minimum one. For the second part, this wasn't tractable, so I started trying to implement the most common solution: track ranges of values instead of individual values, and split them up as they pass through the maps, then take the lowest location at the end. I tried to implement this, but couldn't get it to work because of some bugs I wasn't able to figure out. I also considered another solution of starting with locations, running them backwards through the maps to find corresponding seed numbers, and taking the lowest location that resolved to an in-range seed number, but decided against implementing it. In between frustration at the range-splitting solution not working, on a lark I tried to just put the lowest destination value listed in the location maps into the answer box, and it surprisingly worked (only on my input; other people's were not so lucky), which is unsatisfying, but I won't complain too much about being past the problem.
Day 6: Wait For It (puzzle, code)
Solve Times: 04:22 / #330, 05:16 / #133
This is a much nicer problem, forming a welcome reprieve after Day 5's difficulty. In this problem, there's a list of toy boat races with a Time and Distance given, and your goal is to win each one. You can do that by holding the button down to charge the boat for some number of milliseconds, then releasing it: it will move at a speed of 1 mm/ms (or just m/s if you prefer) per second you held the button down. The puzzle asks for the number of ways you can win each race (i.e. different lengths of time to hold the button), and part 2 just combines them into one mega-race by concatenating the existing races.
My solution for this problem was the simplest and most naive one possible, but fortunately it's short enough that that doesn't matter. For each race, I looped through values of start time i in the range [0, t - 1], using the equation d = (t - i) * i to calculate the distance, and adding 1 to the output if this distance surpasses the goal. This problem is generous enough that this solution only takes about 3.5 seconds on part 2, so I didn't have any need to make it more efficient (even though there's low-hanging fruit optimizations readily available).
Day 7: Camel Cards (puzzle, code)
Solve Times: 09:45 / #94, 18:43 / #184
This is the second problem this year where I've managed global leaderboard, although still only by a hair (if I'd been 13 seconds slower, I wouldn't have made it). It presents a list of hands for a poker-like game, each of which has a bet associated with it, and asks for the hands to be sorted using rules similar (though apparently not identical) to those in real poker. In the second part, the jacks (J) are changed to jokers, which have the lowest value of any card, but can act as whatever card gives the hand the highest-ranking type.
In order to accomplish the sorting, I used Python's functools.cmp_to_key() function to convert a comparator between two hands into something I could use to sort them. For the comparison itself, I used one of my favorite standard library features, Counter(), to convert the hand's string representation into a dictionary of card -> count. With this, I could easily get the hand's type: for example, if the counter has length 1, it's a five of a kind, and if it has length 2, it's either four of a kind (if 4 is in the counter's values) or full house (if it isn't). After adding a bit of logic to account for the case where both hands have the same type (loop through and compare them at each index until one differs), part 1 was solved. For part 2, I used the same approach, just with some extra logic added for jokers (for example, if "J" is in the counter's keys, lengths of 1 and 2 both indicate five-of-a-kind), which worked cleanly.
Day 8: Haunted Wasteland (puzzle, code)
Solve Times: 02:50 / #33, 06:34 / #14
This problem was where I really started to climb the global leaderboard, netting me 155 points. In this problem, there's a list of locations with three-letter identifiers, each of which has a "left" and "right" location associated with it. There's also a list of left/right steps that cycle infinitely. In part 1, the goal is to find how many steps it takes to get from location AAA to location ZZZ. In part 2, you instead simultaneously start at all locations ending in A, and have to find how many steps until all of your positions end in Z.
For part 1, I wrote the most straightforward code possible: track current position and step count, advance to the next position using those two values, break and return the step count when the current position is ZZZ. For the second part, I initially tried to have a list of all the starting positions, advance each one by one step at a time, and then end when all of them ended in Z, but I quickly realized this was intractable. Instead, I guessed that it was a cycle problem like this one from 2019, and pivoted to an approach where I calculated the individual step count for each starting position, and took the LCM to find the answer; this isn't a general solution, as pointed out on Reddit, but it works for this particular problem, which is good enough for AoC.
Day 9: Mirage Maintenance (puzzle, code)
Solve Times: 03:29 / #66, 04:22 / #47
This problem was another strong performance, earning 89 points, enough for 109th place on the global leaderboard at the time. In this problem you're given sequences of numbers, and have to find the next value in each sequence by finding the differences between the sequence's values, then the differences between those differences, etc. until those differences are all zero, then going back up one by one, adding to the end each time, until reaching the initial sequence again. For part 2, the challenge is the same, except at the beginning instead of the end.
This is another simple problem, where my win is attributable just to my coding speed rather than to any special tricks I used. I basically implemented it exactly as described: create a new list with one shorter length, add it to the history, and repeat until done (I used a minor optimization to stop when the list was all equal instead of all zero; this didn't affect much), then go back up calculating the new start/end values.
Day 10: Pipe Maze (puzzle, code)
Solve Times: 25:26 / #954, 1:42:26 / #1941
Unfortunately, the good times had to end, and this Saturday problem was where they did for me, with a far weaker performance that left me nowhere near the global leaderboard. In this problem, there's a pipe composed of -, |, F, L, J, and 7, the latter four looking like corners if you squint, which is surrounded by junk in the form of both disconnected bits of pipe and empty tiles. Part 1 asks for the distance to the farthest point on the pipe loop from the starting position (which is marked), and part 2 asks for the number of non-pipe positions that are surrounded by pipe (with the key complication that it's possible to squeeze through pipes that are adjacent on the text input, such as 7F next to each other).
For part 1, after some initial false starts, I decided to instead convert the pipe into a graph and use Dijkstra's to find the farthest point from the start. After converting the "S" marker on the grid to the correct pipe shape, I used my graph_from_grid utility function to convert it, using a helper path function that checked the pipe shapes at points on the grid to decide if they were traversable. This took a while to write, but ultimately worked. For part 2, my initial instinct was to use a flood fill from the inside, which failed because of the possibility of multiple disconnected regions of interior non-pipe positions. My next idea was to use flood fill from every position on the edge of the grid simultaneously, which partly worked, but didn't fully because I didn't realize the part about squeezing between pipes. In order to retrofit this to work, I added a new step: every position I considered "inside" I would manually search from to try to find a way out by squeezing between pipes. This did work, although it was very finicky to write and took dozens of minutes to write and around five seconds to execute. It's not a good solution (many better ones exist), but it at least works.
Day 11: Cosmic Expansion (puzzle, code)
Solve Times: 04:28 / #24, 06:07 / #22
After the extremely difficult (for this early in the year) day 10, this was a very easy problem where I earned 156 points, clearing my day 8 haul by 1 point. In this problem, there's a grid of "galaxies" (#) and empty space (.), and the goal is to find the sum of distances between every pair of galaxies. However, there's a twist: every row or column which contains no galaxies is actually doubled due to "cosmic expansion", and in part 2, it's instead increased to a size of 1,000,000.
This problem went so well for me because of a combination of having the right tools ready and making the right snap decisions. In order to read the input, I had the perfect helper function prewritten (even with a typo I had to panic fix): grid_set_input, which returns the (y, x) positions of all characters in a list (in this case, just #) in the input grid. Following from this, I didn't use the method of actually inserting additional rows/columns into the grid: I just made a list of empty rows/columns, and then added extra when calculating the Manhattan distance between galaxy pairs. The former method wouldn't've worked with my data representation regardless, but it was something the second part was specifically designed to counter, so avoiding it ensured I could complete part 2 quickly.