Christopher Bohn
Advent of Coding

Repository



2022 Advent of Code Solutions

Day 1

The problem
The solution

I like the first few days' problems -- they're simple enough that they make great computational thinking examples for my
100-level students.
Breaking the problem down into subproblems:

Keep track of how many calories an elf is carrying
Detect when we've reach the end of the list of items that elf is carrying
Convert strings to integers
Of the elves considered so far, keep track of the number of calories being carried by the elf who is carrying the most
calories (or the three elves who are carrying the most calories)
Update that count when we've finished with an elf

For part 1, we must determine whether the most-recent elf is carrying more calories than the maximum among the
previous elves
For part 2, we must determine whether the most-recent elf is carrying more calories than any of the previous
top-three


Produce the result

For part 1, the result is the maximum number of calories being carried by any one elf
For part 2, the result is the sum of the number of calories being carried by the top three


While I wouldn't expect my students to be able to provide solutions in quite so few lines as I did -- we don't teach the
Java streams API in CS1 -- they could definitely do this problem.
The only wrinkle is that a blank line isn't the only way to reach the end of an elf's list.

Refactoring opportunity
Parts 1 & 2 differ only in how many "maximum" elves we're tracking and, consequently, how we perform our update.
My part 2 solution used a set that can never grow to more than 3 items because we're tracking the top three elves.
Part 1 can be thought of as a degenerate case of tracking the top "one" elf;
this suggests that it can be solved with a set that can never grow to more than 1 item.
Which means we can use the same solution for both parts, parameterized by the top "number" of elves, which becomes the
upper limit of the size of the set.

Day 2

The problem
The solution

The subproblems for both parts are

Score a single round

Determine which hand is played by each player; adjust score based on "my" hand
Determine the outcome of the round; adjust score based on the outcome


Compute the total score

Seems pretty straight-forward.

Refactoring opportunity
Parts 1 & 2 differ in whether we determine the outcome based off of "my" hand, or whether we determine "my" hand based
off of the outcome.
Where we parameterized the commonality on Day 1, today we'll simply extract the commonality into a helper method.

Day 3

The problem
The solution


Part 1
The subproblems are

Determine an item's priority
For each knapsack, determine which items are in each compartment

Assume an even non-zero number of items


For each knapsack, determine which item is common to both compartments

Assume there is exactly one item that is common


Aha! one of the knapsacks in the sample data has 'L' as a common item, twice


Sum the priorities of all the "common items"


Part 2
The subproblems are

Determine an item's priority (solved from part 1)

Determine which items are present in exactly three knapsacks

Determine which knapsacks each item is in
I'm not sure that it matters, but what if a "triplet item" occurs multiple times in a knapsack; is it no longer a
"triplet item"? We probably could check by finding out if an elf is in more than one triplet.


Looks like I misread the problem statement originally. It seems that we don't need to find the triplets; the triplets
appear in order in the data, knapsacks {i, i+1, i+2}

Assume the number of knapsacks is divisible by 3
Determine which item is common in each triplet

Assume each triplet has exactly one "triplet item"


Sum the priorities of all the "triplet items"


Refactoring opportunity
Both problems involve finding a singular common character -- one among two strings, the other among three.

Day 4

The problem
The solution


Part 1
The subproblems are

Determine which sections each elf is responsible for

Determining the minimum and maximum section numbers should be sufficient


For each pair, determine if one elf's section range is fully covered by the other's

Comparing the minimums and maximums should be sufficient


Count the number of such pairs

Seems straight-forward enough.

Part 2
The subproblems are substantially the same. The only difference is that instead of checking for complete overlap, we're
checking for any overlap -- we just need to change the comparison.

Refactoring opportunity
As noted, the only difference between parts 1 & 2 is how the comparison happens.
I must be spending too much time with C, because my first instinct was to create a function pointer and then create a
function for each of the two ways to compare.
No, the thing to do is to extract the common part out into a helper method.

Day 5

The problem
The solution

We've hit the first puzzle whose input will require a little creativity when parsing.

Part 1
The subproblems are

Separate the initial conditions from the subsequent instructions

Assume there is exactly one blank line between them


Represent the stacks

At the risk of diving into the solution space, obviously we'll do this with a list of stacks
Determine how many stacks there are

Assume that the last line of the initial conditions is the stack numbers, beginning with ' ' followed by a '1'
Assume the stack numbers are in-order (i.e., the last index tells us how many there are)
Can we assume there are only a single-digit number of stacks?


Assume all crates are of the form "[?]"

Part of that is an assumption that a crate can be represented with a single character -- and I'm going to further
assume it's not ' '


Assume an empty space atop a stack is of the form "   "
Assume exactly one space between stacks


Follow the instructions

The regular format of the instructions will make them easy to parse
(Solution space) pop/push will be easy


Output the top of each stack, in order

Why do I have the feeling that there'll be some version of
The Towers of Hanoi before we're done?

Part 2
The difference here is how we move multiple crates from one stack to another.

Refactoring opportunity
With the difference between the two problems occurring inside a nested loop, extracting the commonality into a helper
method (more than I've already done) isn't going to work. Passing in a pointer function would do nicely, but doing the
Java equivalent is a PITA for such a small payoff. I think I'll use a boolean to indicate which of two crate movement
techniques should be used.

Day 6

The problem
The solution


Part 1
The subproblems are

Identify the first sequence of four unique characters in a string

Assume there is such a sequence
Determine when a sequence of four characters contain duplicates


Count the number of characters before the next character after that sequence


i.e., count the number of characters before that sequence plus the four characters in that sequence


Part 2
The difference here is the length of the character sequence with unique characters.

Refactoring opportunity
This is straight-forward -- I just need to parameterize the helper method that looks for the unique-character sequence.

Day 7

The problem
The solution


Part 1
The subproblems are

Parse the input
Based on the responses to commands, determine the size of each directory

The size of a "leaf" directory that has no subdirectories is the sum of the sizes of its files
The size of a non-leaf is the sum of the sizes of its files and the sizes of its directories


Determine which directories' size is at most 100000

It is very tempting to create a model of the directory structure, but the concern of course is the memory usage.
Many of these problems can be mapped to a simpler problem.
I think the reason I'm so tempted to create a model of the directory structure is because the description of the
structure is coming in BFS, but determining the directory sizes would best be done DFS.
It looks like the puzzle input has fewer than 200 directories. YOLO. So, add to the subproblems:

Build a model of the directory tree


Part 2
The new subproblems are

Determine how much space needs to be freed
Find the smallest directory whose size is greater than that amount


Refactoring
In Part 1, we looked for all directories below some threshold size.
In Part 2 we want the smallest directory above some threshold size, which can be obtained by looking for all
directories larger than the threshold and selecting the smallest.
By parameterizing the searching method with the threshold size and whether we're looking above or below the threshold,
it will serve both parts.

Day 8

Part 1
The subproblems are

Determine whether a tree is visible

From the right or left
From the top or bottom (solution space -- this may be easier if I add a subproblem of rotating the matrix)


Count the number of visible trees


Part 2

Day 9
(coming soon)