Advent of Code 2018
Here are my solutions to Advent of Code 2018, following up on my solutions for 2017 and 2016. In order to understand each day's two-part puzzle, you'll need to click on the header links below (e.g. Day 1: Chronal Calibration) and read the description. This year I didn't find time to race in real time when the puzzles are released; instead I'm doing batch processing, doing a couple of puzzles every few days. You can see I'm currently behind.
Imports and Utility Functions
Part 1 was just a wordy way of saying "add up the input numbers." Part 2 requires cycling through the numbers multiple times, finding the partial sum (frequency) that first appears twice (that is, was seen before).
How many ids have a letter that appears exactly 2 times? 3 times?
Now, what letters are in common among the ids that differ in exactly one position?
Find the guard that has the most minutes asleep, and the minute of the day that the guard spends asleep the most.
First make sure we can parse the log correctly:
How many units remain after fully reacting the polymer you scanned? Reacting means removing
Given a set of pointson a grid (all positive integer (x, y) coordinates), each point defines an area of grid points that are closer to it than any other point in the set (i.e. the Voronoi diagram). What is the size of the largest area (measured in number of grid points) that isn't infinite? To answer, use a
Counter over grid points in the bounding box that covers all the input points.
Originally, I thought that if a point on the perimeter of the box was closest to point
p has an infinite area. That's true for
p that are in the corners, but need not be true for all
p (consider a set of 5 points, 4 in the corners of a box, and one near the center; the center point will have a diamond-shaped area, and unless it is at the exact center, it will "leak" outside one of the edges). So I expand the bounding box by a margin. I make a guess at the necessary margin size, so my answer might not always be correct, but hey, it worked for the input I was given.
Given instructions like
Step B must be finished before step A can begin, in what order should the steps be completed? When several steps are possible, do the alphabetically first (
In part 2 I need to schedule each step; I'll keep track of
endtime[step] as a time step (initially infinitely far in the future). I'll also keep track of the number of available workers, decrementing the count when I assign a step to a worker, and incrementing the count when a step is completed.
I'll handle the list of numbers as a
deque (so I can efficiently pop from the left), and I'll create a
Tree data structure with
kids (children) fields.
I'll represent the circle as a
deque (so I can
rotate). I had a couple of off-by-one errors, due in part to the problem being 1-based not 0-based, so I put in the
verbose option; in my verbose output (unlike the problem description), the circle always starts with the position after the "current" position, and the newly-inserted marble is always last.
The basic idea of moving objects into a new configuration is easy: increment their position by their velocity to get a set of points. The hard part is figuring out when they spell a message. My assumption is that the lights are initially spread far afield; over time they will come together into a central location; then they will overshoot and go off in the other direction. My even bigger (but still resonable) assumption is that the message is spelled when the area of the bounding box of the points is a minimum. When that happens, I'll just print the configuration, and read what is there. (I won't write code to do OCR.)
That should be "
In Part 2 I need to get the time
t at which we generate the configuration
To enumerate all the squares of any width is O(n4); too much when n = 300. So I'll refactor
total_power to cache results in a summed-area table (a standard approach from computer graphics).
One-dimensional cellular automata. Fun! AT first I thought I would represent a row of plants as a string, but I realized I'd also need to track the start position of the string, so I decided it was easier to represent a row of plants as a set of index numbers of pots that are live. I'll make
grow() yield all future generations:
Cool, my answer is leet-er than
1337. But Part 2, asks for 50 billion generations. Maybe the pattern reaches a fixed point, or cycles, like the blinker in Conway's Life game. Let's plot the number of plants, and their sums, over the first couple hundred generations and see if there is a pattern:
OK, no problem: after a while the sum settles down and grows at a constant rate. I can figure out what that rate is:
It is growing by 21 each time. So my answer should be 2580 + 21 × (50 billion - 100). More generally:
Now, why does it grow by 21 each time? Well, we saw in the plot of lengths above that the length eventually remains constant; we can see the last few:
There are 21 plants in each generation; here is one generation:
We see that the plants are bunched into groups of three. What happens to a group of three?
They move one to the right each generation; moving 7 groups of 3 one to the right results in adding 21 to the sum.
I need to do the following:
- Parse the picture of the world into a data structure.
- Keep track of the carts, and have them make the right moves.
- Continue until there is a collision.
Since this has to do with headings and turns, I'm going to use complex numbers to represent points, headings, and turns; multiplying a complex heading by a complex turn results in a new heading. Then adding the heading to a point results in a new point. I'll redefine the
Y accessors to handle either the complex points used here or the tuple points used previously:
Now we need to define a
Cart, and the
World they will live in. We use the
dataclass facility from Python 3.
Now the function
madmad(world), which simulates moving the carts until a collision.
7, 3, is correct, and everything looks good!
Unfortunately, I got an error when trying it on the actual (larger) input.
Even more unfortunately, I ran out of spare time to debug this problem and to move on to the remaining days. Maybe next year!