This year, Advent of Code changed : only 12 days. Eric Wastl has hit 10 years of doing this, and sensibly backed off to about half the volume of a normal year - which is also a relief to the rest of us.
Day 1: Secret Entrance
Clock arithmetic. Did it quickly with a simple algorithm. There must be a better way.
Day 2: Gift Shop
Part 1 straight forward, part 2 … trickier, there was a little gotcha in the logic if you weren’t carefully thinking about what the question meant.
Day 3: Lobby
Oh, this was a good one. First part didn’t look too hard, second part looks baffling. I know I could solve it with a tree and Djikstra or a BFS … but I didn’t want to remember how to. So I went and had dinner, came back and stared at it … and realized it was actually pretty simple, just divide and conquer. Memoisation sort of.
Day 4: Printing Department
Straight forward map manipulation. Second part was amusing, but not too challenging.
Day 5: Cafeteria
Liked this one. Ranges of numbers, do other numbers fall in those ranges? That was easy … so the elves want to know how many possible ingredients could be fresh … and the ranges overlap. Had a couple of hurdles to get through trying to collapse identical ranges and then ranges that started OR ENDED aligned with another … but I got there, and the elves can relax, they have 352,509,891,817,881 fresh ingredients available.
Day 6: Trash Compactor
Oh, this made me laugh. A funnily formatted worksheet, parse the strings, remove the excess spaces, and part 1 is easy. Part 2 … oh wait, the spaces between numbers becomes critical.
Had to write a nifty algorithm to extract the calculations from the worksheet, then it was easy.
Day 7: Laboratories
aka Lanternfish! Helps if you’ve done older AoCs. Initially it’s a simple trace rays that split at prisms, count number of splits sort of thing … but part 2 goes many-worlds, and the numbers get too big to track individually.
But the insight is that you can derive the number of rays in any given cell by counting the ones above, and above left/right, depending on a couple of basic rules. Dynamic programming …
Figured it out on the bus into work, had to spend the day itching to get home.
Day 8: Playground
Liked this. Basically it’s a set of 3d points: join the two closest to make a line, then keep joining the next two closest … sometimes you’ll append to an existing line, sometimes you’ll bridge two lines, and eventually you end up with a single branching network.
2d graphics looked like this.
Got some 3d graphics going … need to work out how to color the sets and fly through the scene.
Day 9: Movie Theater
For a given irregular shape, what is the largest rectangle you can fit inside it? A slightly odd one. I enjoyed the first part as reading and working with the coords was fun, then the second part was clearly going to be hard. I went and looked up algorithms on ray tracing and got one working for the sample; but then tried it on the second … and it was screamingly slow.
So time to generate a map and take a look. And mine is basically a big circle - slightly uneven - with a big chunk taken out of the middle. So that clearly means I can get rid of half of the problem immediately, any rectangle crossing the centreline will be invalid.
But it’s still going to be too slow to ray trace to make sure. So I take a look at the outside of the circle and … it’s not indented anywhere else … which means I probably don’t have to ray trace. All I need to do is check all four corners are inside the main polygon and give it a try.
Why I’m … unsatisfied is that if this hadn’t worked, I don’t know how to do it. Seems a bit of a cheat to have just one hole/indentation.
Day 10: Factory
Loved it and learned something new. Build a series of machines with lights that (part 1) must be on or off and (part 2) must have an input voltage.
Each machine has a series of buttons, each of which will either toggle the light on/off or add 1 to the input voltage. What’s the minimum number of button presses to get each machine into a particular state?
Solved part 1 with a breadth-first search. Part 2 similar algorithm is working but is far too slow.
Reddit talked about a package called Z3 which everyone seemed to be using. I went off and had a look, it seemed a little baffling, but I could get a simple example to work. Converting this problem into the right code … was actually pretty simple, Microsoft (and others) have done it very nicely. And it worked, very fast.
Day 11: Reactor
Loved it. A big directed graph; a wiring diagram that you have to trace through to find how many paths will go through two specific nodes.
Part 1 is easy, just count the paths from the yellow to the green node.
Part 2 is the whole graph, but count only the paths that go through the purple and blue nodes. Eyeballing the graph, you can clearly see a series of bottlenecks, so you can divide the problem into these important nodes, trace multiple smaller networks to reduce them to a single path, and then multiply the costs …
Day 12: Christmas Tree Farm
Presents - a series of polyominos - need to be placed in a grid, you need to work out if they will fit within the given space.
Sigh. Clever.
Clearly going to be too hard to run with brute force, but that didn’t stop me trying and in 500 lines of code I got the right result from the sample … this is the second grid.
00022444444.
002224.44.4.
002254544545
....555..555
....5.5..5.5I didn’t use prune and backtrack; I should have done, I chose instead to pre-calculate the combinations, and hah, silly me, the first line of part 1 runs out of heap space.
But I wasn’t worried. The third line of the same with a mere 21x5 grid and 7 presents took 7 seconds - the real data has over a thousand 40x40 grids with 300 presents so it’s never going to work.
So I thought I’d go see how to solve it on Reddit - and the answer was already there. Like the mutilated chessboard problem, there’s a simple check. All presents are 3x3, with gaps inside.
- assume every present gets placed with no overlaps at all, so like pretending they are solid. If the number of presents x 9 squares is smaller than the total area (and there’s a catch, not needed, about dimensions and fitting) then you will be able to fit them all in.
- count the actual squares each present will use - e.g. 6 or 7 etc. If there are more squares than are available in the grid, you will never be able to fit them all in, regardless of position or orientation.
- if neither of these two cases are met, you’ll need to check.
Dear reader, there were none in the third set. So there is no need to check anything.
See my public repo for the code behind all of this.