2021 Advent of Code Solutions
Day 1
A nice little warmup exercise in which we iterate over a list. Notice that I get to use Java's new multiline strings.
Day 2
Can we follow instructions? Yes we can. This isn't a particularly challenging problem. Beside using Java's new Records, I'm also using Java's new style of switch statements.
Day 3
My CSCE 231 students should be able to do this problem in their sleep -- bit masks are cool.
Day 4
This problem is a little more interesting since there are two stringly types in the data, and one of them (the Bingo cards) requires a delimiter between instances. Defining a custom class to represent Bingo cards simplifies the post-parsing problem.
Day 5
This is a pretty straight-forward problem. The only real challenge is that there are two significant sub-problems: computing the line segments and computing the vent map. I suppose an alternative approach would be to compute the y=mx+b form of the lines and algebraically determining their intersections.
I definitely need to get into the habit of thinking about computationally less-complex approaches. The straight-forward design I came up with for Day 5 is O(num_lines * num_rows * num_columns); the algebraic approach would be O(num_lines^2), so not too much of a big deal on this problem. But (I'm sure) there will be some problems whose straight-forward solution are a tad intractable.
Day 6
For example, in the problem statement practically screams that the obvious solution grows exponentially. Normally, death would keep the population under control, but I guess Death Takes a Holiday. One little extra gotcha: 26984457539 > Integer.MAX_INT, so I need to use a long integer.
Day 7
Naively trying each position is reasonable: O(num_crabs * max_distance). Or, we could follow a similar model of Day 6, in which we track the number of crabs in each position, which would be O(max_distance^2). These are both very manageable, so I'll go with tracking each crab since that requires less upfront work.
Part 2 looks a bit more interesting. We could go for an O(num_crabs * max_distance^2) solution, or we could recognize what Euler recognized: ∑_{i=1}^{n}i = n(n+1)/2.
Day 8
Seven-segment displays are cool. This has the potential to be a pain. Part 1 looks okay -- examining only the output patterns, count the number of patterns of length 2, 3, 4, or 7.
For part 2, I think set operations are the way to go. For simplicity in this explanation, I'm going to use numerals to depict the sets of illuminated segments.
- Those we know from length alone:
- 1 is the only digit of length 2
- 7 is the only digit of length 3
- 4 is the only digit of length 4
- 8 is the only digit of length 7
- 7\1 gives us the top segment
- Considering the length-6 digits:
- 9 is the only one for which 4\digit = ø, giving us the lower-left segment
- 6 is the only one for which 1\digit ≠ ø, giving us the upper-right segment
- 0 remains, giving us the central segment
- (9\7)\4 gives us the bottom segment
- 1{upper-right segment} gives us the lower-right segment
- The upper-left segment remains
- Considering the length-5 digits:
- 3 is the only digit for which digit U 1 = digit
- 5 is the only remaining digit for which digit U 4 = 9
- 2 remains
It turns out we can ascertain the digits without needing to record the segments. That's nifty.
Day 9
Part 1 doesn't look too fancy I'll simplify the adjacency-check a little by
making the heightmap larger by two in each dimension so that I can create a
"frame" of MAX_VALUEs.
Hmmm -- While that O(num_rows * num_columns) algorithm took a fraction of a second, it was noticeable on the human scale. I don't think there's a better big-O approach, but the constant factors could be in play if I were to look for optimizations.
Part 2 defines "basin" okay, but requires a little thought to express as numbers. In the examples, the basins seem to be monotonic until reaching height 9. Monotonic makes sense, given the definition "...flow downward to a single low point," but what about a location of height 6 that has a basin on either side?
- I'm going to assume, for now, that there are locations whose height is less
than 9 that are between two basins -- the simple check to see if there's an
adjacent location of greater height potentially could count a location as
being in two locations otherwise. If I'm wrong, I'll fix it.
- Come to think of it, plateaus would also be a problem for the simple check. The examples don't have any plateaus.
- I'm going to change my part 1 code to create a height-9 frame. That's enough for the low-point calculation and will simply part 2 a little. I'm also going to change my part 1 code to record the low points so that I don't have to re-calculate them for part 2.
- We'll go for a finite element approach.
Hmm. Part 2 takes a few seconds, but no surprise there -- it's now O(n^5).
Day 10
This looks like a job for a stack!
Update: Yes, yes it was a job for a stack. Some maps simplified matters but were not essential.