README.md

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

• The problem
• The solution

Part 1

The subproblems are

• Determine the tree heights
• 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

The subproblems are

• Determine the tree heights
• Determine the scenic score for each tree
  • For each tree, determine the distance, in each direction, to the next tree that is at least as tall
  • Multiply those distances
• Report the greatest scenic score

Refactoring

Extracted the code that generates a matrix of tree heights. The structure between the code that computes tree visibility and the scenic score are essentially identical; the not-inconsiderable difference is that one works on a boolean matrix, and the other works on an integer matrix. I suppose I could make the boolean matrix be an integer matrix of 0s and 1s, but that would pain me almost as much as the structural DRY issue. So, just this once, I'm going to pinch my nose and accept the structural DRY issue.

Well... I'm going to take the part 2 code in a (very) slightly different direction than the part 1 code.

Day 9

• The problem
• The solution

Part 1

The subproblems are

• Determine whether the head and tail are touching
• Determine what direction the tail should move
• Both of the previous subproblems include the subproblem of finding the distance between the head and tail along each dimension
• Track which locations the tail has visited
• Count those locations

Part 2

The subproblems are essentially the same as before, substituting "the head" and "tail" with "a knot" and "the next knot"

Refactoring

We'll replace the explicit head and tail with an array of Positions.

Day 10

• The problem
• The solution, including the computer

It looks like it's time to start building this year's "computer."

Part 1

The subproblems are

• Parse the input
• Process no-ops (advance the cycle counter by one)
• Process addition (update the accumulator and advance the cycle counter by 2)
• Determine the "signal strength" at cycle 40n+20
  • I've already determined in the larger sample that there are an odd number of no-ops within the first 20 instructions, which means that the signal strength might be measured in the middle of an instruction (i.e, we cannot simply advance the cycle counter by 2 for addition)
    • Yes, I realize the instructions also make this pretty clear

Looking at the "computer," it needs to

• Do the parsing and processing, described above
• Advance to a specific clock cycle, which may be in the middle of an instruction
  • Presumably, if the "program" has terminated, then there's no expectation of advancing to that clock cycle
• Report the signal strength

An interesting twist: the signal strength we're looking for is the signal strength during the clock cycle -- not before, not after. That means that the clock cycle has advanced, but the accumulator hasn't updated.

Part 2

• Determine whether to illuminate the pixel for the current clock cycle
• Determine the accumulator's value before the current instruction's result is latched in
• Determine whether that value falls within the sprite's range

Refactoring

Recognizing that we're now looking at many things that happen before the results are latched-in at the end of the cycle, I'm revisiting the signal strength code.

Day 11

• The problem
• The solution

Oof. This is a long description. Probably because the input is so verbose, and then you have the example.

Part 1

The subproblems are

• Parse the input to obtain, for each monkey, its
  • starting items -- not only the value (worry level), but also the order
  • relationship between the new and old worry levels
    • after examining the input, all operations appear to be addition or multiplication, and the first operand is always the old value
  • test operation and the true/false target monkeys
    • after examining the input, all tests are whether the worry level is divisible by some integer
• Determine which monkey will throw an item next
• Reduce an item's worry level immediately before it is thrown
• Track how many (probably non-unique) items a monkey inspects across the many rounds
• Determine the two most active monkeys after 20 rounds

Part 2

The part 2 description seems to be forecasting that the Monkey class will be used and modified again in the coming day(s). If that happens, then I'll move Monkey to be an outer class instead of an inner class. For now, I just need to modify it so that the boredom modification is optional.

Refactoring

Since parts 1 & 2 differ only in whether to use the boredom modification and the number of rounds, I can create a parameterized method.

There's more to it than that

It looks like part 2 isn't saying to abandon the divisor now to replace the modifier later.

I guess we're supposed to figure out the new modifier for part 2. That is more interesting, to say the least.

Both the description and my code (without a boredom modifier) agree that after 1 round:

Monkey 0 inspected items 2 times.
Monkey 1 inspected items 4 times.
Monkey 2 inspected items 3 times.
Monkey 3 inspected items 6 times.

but after 20, the description says

Monkey 0 inspected items 99 times.
Monkey 1 inspected items 97 times.
Monkey 2 inspected items 8 times.
Monkey 3 inspected items 103 times.

but my code (without a boredom modifier) says

Monkey 0 inspected items 96 times.
Monkey 1 inspected items 100 times.
Monkey 2 inspected items 7 times.
Monkey 3 inspected items 103 times.

Thought #1

I wonder if what we're seeing suggests the final pre-throw modifier is history based; that is, no modifier on the first inspection, but then the monkey gets a little bored at something it's seen before. The obvious thing to try is to have no modification the first time that the monkey inspects an item (preserving the correct result from round 1) and then divide by 3 if the monkey has seen it before.

No, that isn't it, either. After 20 rounds:

Monkey 0 inspected items 96 times.
Monkey 1 inspected items 100 times.
Monkey 2 inspected items 10 times.
Monkey 3 inspected items 102 times.

Thought #2

It doesn't seem likely that the AOC creator would want us to blindly guess at possible modifications.

Maybe the answer to whether there is no modifier in part 2 is "both."

Perhaps the hint is in the test for which monkey will receive the item -- it's a test for whether the worry level is divisible by some value. We can keep the worry levels down to manageable values while also preserving the outcome of this test for any given inspection by assigning the worry level to the remainder of that notional division. Then the remainder is some other value between 0 and the original worry level, which will be the same as the modulus operator's result (and this remainder will also produce the same modulus result).

How will this affect subsequent throws? All operations are multiplication or addition. Suppose the original value is i = n \times testDivisor + remainder for some value n. In the case of addition, i + j = n \times testDivisor + remainder + j and the resulting modulus is unchanged. In the case of multiplication, if we view it as repeated addition then the same argument holds.

Either I'm barking up the wrong tree, or we were seeing overflow errors earlier.

== After round 20 ==
Monkey 0 inspected items 95 times.
Monkey 1 inspected items 101 times.
Monkey 2 inspected items 9 times.
Monkey 3 inspected items 99 times.

Shazbot.

Thought #3

I'm sure I'm on the right track. I think I was off-base with my answer to how it will affect subsequent throws. The problem is that taking the remainder of i \div testDivisor_x might not preserve the modulus of i \div testDivisor_y.

We need to use a divisor that would preserve both -- that is, the divisor must be a multiple of both testDivisor_x and testDivisor_y.

Okay, seriously!? How does Java not have a least common multiple function?

And let's make the worry levels long instead of int just to give us a little more room to grow.

== After round 20 ==
Monkey 0 inspected items 99 times.
Monkey 1 inspected items 97 times.
Monkey 2 inspected items 8 times.
Monkey 3 inspected items 103 times.

Shack!

Day 12

First, a closing thought on yesterday's problem. The concept I stumbled upon is the Chinese Remainder Theorem which apparently has an Advent of Code reputation.

And now on to today's adventure.

• The problem
• The solution

Part 1

Speaking of AOC staples, it looks like today we need to implement a shortest path algorithm.

The subproblems are

• Create locations and build a reachability graph (unweighted, directional)
  • Compare heights
• Find the shortest path from the start to the finish

My critique of my part 1 solution

• I'm not thrilled that I'm storing the distance from the start as a Location attribute; I suppose the alternative is to create a Map<Location,Integer>

Part 2

The difference is that we're now examining many possible starting locations. A naïve approach would be to run the algorithm I developed for part 1, which starts at start, using each 'a' Location as a starting point, in turn. Alternatively, we could work backwards from finish and find the distance of each Location to the finish. Then look for the shortest distance to the finish from the 'a' Locations.

Day 13

• The problem
• The solution

Part 1

The subproblems are

• Decode packets
  • Pairs of packets, each on its own line, with pairs separated by blank lines
  • A packet is a list
  • A list consists of integers and lists
• Validate pairs of packets
  1. When two integers are in the same position in both lists, the lesser must occur in the first list
     • If we encounter non-equal integers before anything else, we are done
     • If we have equal integers, fewer than two integers, then advance deeper into the lists
  2. Convert a solitary integer to a list of only that integer
  3. When two lists are adjacent, compare their elements using rules 1-3
     • If integer comparison does not establish the validation, then compare list lengths
       • If all integer pairs are equal then the shorter list must be the first list
     • If we have lists of the same length with identical elements, then advance deeper into the containing lists

Part 2

The subproblems are

• Add the divider packets (trivial)
• Sort the packets
• Determine the indicies of the divider packets (using 1-based indexing)

Since I created a compareTo() method as part of Part 1, Part 2 is easy.

Day 14

• The problem
• The solution

Part 1

The subproblems are

• Determine which locations are blocked
• Determine where a unit of sand moves to
  • Can it move?
  • Down, diagonally left, diagonally right?
• Determine the final status of a unit of sand
  • Stationary, blocking a location
  • Falling forever

Part 2

Same subproblems, except that falling forever isn't an option. Instead, we'll have to pretend there's an infinitely-long floor.

Day 15

• The problem
• The solution

Part 1

The subproblems are

• Parse the input to determine where each sensor is and where its nearest beacon is
• Determine which positions cannot contain a beacon (i.e., which positions are no closer to the sensor than the beacon)

Creating a 6,862,736 x 6,004,906 matrix is a bit of a memory hog. What? You don't have several terabytes just lying around? Clearly we need to go back to tracking the Sensor data and dynamically determine whether a given position is covered.

Part 2

Hah! My CSCE 231 students who remember how to compute an address in a nested array will recognize what's happening here.

Our task is to find the one location that is not covered by a sensor and then compute its linear position in a nested array -- er, um -- to compute its tuning frequency.

Is there a smarter (faster) way than iterating over 16 trillion positions? Probably. What do we know?

For any given sensor at (x,y) whose nearest sensor is distance d away, the sensor covers the square (x-d/2,y-d/2) through (x+d/2,y+d/2) plus several other locations. While 16 trillion locations is a bit much, we could handle 4 million rows, where each row is a set of covered ranges. When we look for that one uncovered spot, we only have to examine the rows -- or rather, row, that isn't fully covered by a range.

Refactoring opportunity

The ranges could also be used to solve part 1 (no surprise there). I don't think I'll do that, though, since I can optimize the part 2 solution for non-negative indices.

Day 16

• The problem
• The solution

Part 1

The subproblems are

• Parse the input to determine how much flow is possible with each valve and to create a graph of the tunnels
• Find the (partial) walk that maximizes the flow within the allotted time

I'm feeling a dynamic programming solution is in order.

Part 2

...

Day 17

(coming soon)