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