I wasn’t able to do Advent of Code 2020 last year because I spent just about every night working on my book. However, one of my goals this year was to complete 107 stars on Advent Of Code. If I can pull that off, I’ll be just 50 stars shy of full completion (of course they are the hard ones left).

As such, I decided to tackle last year after I was done working on my book. I did the first 13 challenges over a week in March, the next 4 in May, and the remaining nine challenges this month. I figured this is a good chance to review my thoughts on each of the puzzles, and what I liked and didn’t like. If you’re interested, check out the repo here.

Overall Thoughts:

Someone mentioned to me they thought this was an easier year, and I agree (however, I’ve only finished one other year). The challenges seemed fairly straightforward, I looked forward to solving the problems. I love Advent of Code, so I was glad to complete these challenges. Not as many problems stuck out as memorable as past years, but it was overall enjoyable.

Day 1

Type of Problem: Iteration

Difficulty: Easy

Rating: 4/5

An incredibly easy problem with itertools, as expected in Day 1. My main part of the code was just a call to combinations and reduce: (Note, this should have totally been a sum instead of a reduce, thanks to @hops_and_smoke to point that out.)

return next(values for values
                in itertools.combinations(entries, number_of_entries)
                if reduce(operator.add, values) == target)

Day 2

Type of Problem: Text Validation

Difficulty: Easy

Rating: 2/5

Text validation problems are not my favorite, but it was fairly straightforward. I’m not a fan of day1/day2 splits that require different algorithms (not as much reuse), but it’s still early on in this problem.

MVP of this problem (for part2 ) is the xor (^) operator:

        min_index = self.policy.min_val - 1
        max_index = self.policy.max_val - 1
        return ((self.password[min_index] == self.policy.letter) ^
                (self.password[max_index] == self.policy.letter))

Day 3

Type of Problem: Grid Manipulation

Difficulty: Easy-Medium

Rating: 3/5

The tricky part of this one was knowing how to handle infinite data, but again, itertools to the rescue

    # this is a vertical slice of trees that we can iterate over
    tree_lines = iter(zip(*trees))
    # ignore the first column
    next(tree_lines)

Day 4

Type of Problem: Text Validation

Difficulty: Easy-Medium

Rating: 1/5

This is one of those tedious problems, where the problem isn’t interesting (in my opinion, it’s completely fine if you enjoyed it); the complexity comes from the amount of code you have to write. There’s complicated text parsing, data validation with regex and range checking, and vanillla counting ofelements in a list. This leads to a high code-to-complexity ratio.

Day 5

Type of Problem: Binary Conversion

Difficulty: Easy-Medium

Rating: 5/5

One of my early favorites. The seat ID (“FBFBBFFRLR“) really was a binary number. You could figure out the exact ID by converting Fs to 0, Bs to 1, Rs to 1 and Ls to 0. This is easy if you realize this property, but a bit tougher if you don’t.

MVP was the integer parsing function. Here was my code to create a seat-ID

def to_seat_id(boarding_pass: str) -> int:
    # convert to binary and then cast to int
    row = int(boarding_pass[:7].replace('F', '0').replace('B', '1'), 2)
    column = int(boarding_pass[7:].replace('L', '0').replace('R', '1'), 2)

    return row*8 + column

Day 6

Type of Problem: Iteration

Difficulty: Easy-Medium

Rating: 3/5

Some creative use of itertools.groupby made this one a cinch. Also, using a set vs a counter made it really easy to distinguish between any yes answer and all yes answers

def get_sum_of_any_yes_counts(questions: list[str]) -> int:
    grouped_data = itertools.groupby(questions, lambda s: s != "")
    return sum(get_any_yes_count(q) for has_data, q in grouped_data if has_data)

def get_any_yes_count(questions: Iterable[str]) -> int:
    return len(set(letter for letter in chain.from_iterable(questions)))

def get_sum_of_all_yes_counts(questions: list[str]) -> int:
    grouped_data = itertools.groupby(questions, lambda s: s != "")
    return sum(get_all_yes_count(q) for has_data, q in grouped_data if has_data)

def get_all_yes_count(questions: Iterable[str]) -> int:
    question_list = list(questions)
    yes_answers = Counter(letter for letter in chain.from_iterable(question_list))

    return len([count for count in yes_answers.values()
                if count == len(question_list)])

Day 7

Type of Problem: Memoization / Recursion

Difficulty: Easy-Medium

Rating: 3/5

This was a bit lengthy of description for not too complex of a problem. Figuring out if bags can hold each other was not too hard, but you have to be comfortable with recursion

MVP of this problem is functools.cache

@functools.cache
def get_number_of_bags_inside(bag_rules: tuple[BagRule, ...], color: str) -> int:
    bag = find_rule(bag_rules, color)
    return sum([num + num * get_number_of_bags_inside(bag_rules, color)
                for num, color in bag.contains])

@functools.cache
def can_hold(bag_rule: BagRule, bag: str, rules: tuple[BagRule, ...]) -> bool:
    if any(color == bag for _, color in bag_rule.contains):
        return True
    return any(can_hold(find_rule(rules, color), bag, rules) for _, color in bag_rule.contains)

Day 8

Type of Problem: Computer Simulation

Difficulty: Medium

Rating: 2/5

I do like Computer Simulation problems where you write a virtual CPU / assembler for some custom code. The first part was fun, however, the second part felt like just mechanical where you are looping over the same algorithm from the first part, with slightly different changes.

Day 9

Type of Problem: Iteration

Difficulty: Medium

Rating: 3/5

This was okay, not great, not bad, but okay. I liked the idea quite a bit, but the code was not as fun to write as I was hoping. I used a Counter to track seen sums and that helped it out a lot. I could see this being the first real stumbling block of the year if you tried to brute force the solution.

Day 10

Type of Problem: Dynamic Programming

Difficulty: Medium-Hard

Rating: 5/5

This was one of the harder problems if you aren’t familiar with Dynamic Programming (or at the very least, not realizing this was similar to a fibonacci sequence – just with three elements). However, I was super happy with my solution for part 2

def find_all_ways_to_arrange_adapters(adapters: list[int]) -> int:
    # recurrence relation Number of Combinations C(N)  = C(N-1)+ C(N-2)+ C(N-3)
    # if N is not an adapter, then C(N) = 0
    # dynamic programming, there are overlapping recurrences, so we can do this building
    # up a table linearly
    lookup_table = defaultdict(lambda: 0, {0: 1})
    max_joltage = max(adapters) + 3
    for num in range(1, max_joltage + 1):
        lookup_table[num] = (0 if num not in adapters + [max_joltage] else
                                (lookup_table[num - 1] +
                                 lookup_table[num - 2] +
                                 lookup_table[num - 3]))
    return lookup_table[max_joltage]

Day 11

Type of Problem: Grid Manipulation

Difficulty: Easy-Medium

Rating: 3/5

I typically like grid manipulation (I always look for a use of Djikstra’s), but this one didn’t intrigue me too much. It reminded me of the previous year’s solution where you had to shoot meteors with lasers. I had to write a lot of code to get this one going, and more duplication than I wanted.

Day 12

Type of Problem: Coordinate Systems

Difficulty: Easy-Medium

Rating: 3/5

A variation of the Mars Rover Problem. It’s not a tough thing to code, but is a tad mechanical to implement. No real tricky parts in my opinion on part 1, and part2 just involved a a changing of the rules based on where a waypoint was.

Day 13

Type of Problem: Modular Arithmetic

Difficulty: Hard

Rating: 4/5

This was one of my first stumbling blocks of the year. I had to consult my algorithms book to figure out how to do inverse modulus. A lot of of my work was learning more about modular arithmetic. I spent a lot of time tweaking before I stumbled on an answer. It took me a long time to figure it out, but I was glad to finally get this problem.

Day 14

Type of Problem: Binary Manipulation

Difficulty: Medium-Hard

Rating: 3/5

Thinking of bits and masks reminds me of my C++ background, and it was alright messing with this to create the masks. I messed up a bit on part 2 because I misread the part, but I did like the “floating” aspect of the bit mask for memory. This took me a little bit, and it wasn’t my favorite, but I appreciate the variety.

Day 15

Type of Problem: Iteration / Data Structure

Difficulty: Easy-Medium

Rating: 3/5

Another not terrible, not great problem. Keeping the right data structure (in this case a lookup from number to last position seen) made it a simple problem to handle. My solution takes longer than needed (I’m sure there’s a better way), but I was happy to move on from this one.

Day 16

Type of Problem: Deduction

Difficulty: Medium

Rating: 2/5

A bunch of text validation based on position of various fields. This was similar to previous problems in previous years, but just had a lot of code to parse values and handle ranges of possibilities. The trick is to figure out what you know for sure, strip that from your problem space, and keep refining your logic until you are sure of absolutely every field.

Day 17

Type of Problem: Grid Manipulation

Difficulty: Medium-Hard

Rating: 2/5

I did not come up with an efficient algorithm for this one, but I did get it working. 3d and 4d cubes made it interesting to work with, but getting the code to run was a bit of a pain. Once you have a nice “get_neighbors” function, it gets a lot easier.

    def get_neighbors(self) -> list['Point4D']:
        OFFSET = [-1, 0, 1]
        return [self + Point4D(x,y,z,w)
                for x,y,z,w in itertools.product(OFFSET, OFFSET, OFFSET, OFFSET)
                if x != 0 or y != 0 or z != 0 or w != 0]

Day 18

Type of Problem: Parsing

Difficulty: Hard

Rating: 2/5

This one was the most unnecessarily hard problems this year. I struggled and struggled on this one, and had to take a break. I had about twelve false starts in trying to do part 2, and the code is the ugliest that I’ve put out. This reinforced for me the fact that I need to learn a bit more about how compilers handle precedence of operations, which I’ll welcome.

Day 19

Type of Problem: Graph Algorithm

Difficulty: Hard

Rating: 3/5

Right after challenge 18, I had another struggle with 19. My first solution was not tenable for part 2, as trying to get self referential nested tuples of strings turned into a nightmare to reason about. Instead, I ended up writing a graph that represented a discrete finite automata to match strings. It’s another not pretty solution, but I was happy to get through it.

Day 20

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 4/5

This was probably my favorite concept, except for the sheer amount of code I had to write (it was my longest solution for any day). I liked the idea of stitching tiles together and having to deal with rotations and flipping. Finding sea monsters was a fun twist on the image as well.

MVP was discovering that there was 8 possible orientations after flip/rotate transformations (figured out through combinatorics, not rotational geometry).

def get_permutations(self) -> list['Tile']:
        flipped_tile = self.flip_around_horizontal_axis()
        # can only be 8 ways of flipping/rotating to something unique
        return self.get_rotations() +  flipped_tile.get_rotations()

    def get_rotations(self) -> list['Tile']:
        def rotate(tile: 'Tile') -> 'Tile':
            # transpose and horizontal flip
            return Tile(self.id, [''.join(d)[::-1] for d in zip(*tile.data)])

        t1 = rotate(self)
        t2 = rotate(t1)
        t3 = rotate(t2)

        return [self, t1, t2, t3]

    def flip_around_horizontal_axis(self) -> 'Tile':
        return Tile(self.id, self.data[::-1]

Day 21

Type of Problem: Set Theory / Deduction

Difficulty: Medium

Rating: 3/5

Set theory problems are typically interesting to me, and I like using set intersections and unions to make it easier to handle questions about data. This was a better deduction algorithm than previous problems this year. This would have been easier, but I messed up earlier and didn’t make a copy of a list at the right time (curse you mutability)

Day 22

Type of Problem: Recursion

Difficulty: Easy-Medium

Rating: 2/5

This wasn’t a hard problem, I just made a silly mistake in checking for previously seen game states by concatenating two lists. However, [1] + [2,3] is the same as [1,2] + [3] in that case. Changing the code to calculate a hash instead of list concatenating solved the problem quite quickly. I had a bit more code duplication that I wanted, but I could taste the finish line and wanted to get done.

Day 23

Type of Problem: Iteration / Data Structure

Difficulty: Medium-Hard

Rating: 4/5

This was probably my second hardest problem to tackle. The first solution was easy, but if I were to use it for the second part, it would take 50 hours (at least) to solve the problem. I looked for repeating patterns, or optimizations but couldn’t come up with anything. I was manipulating string slices, and I figured that all the allocations were doing me in. Instead I made a doubly-linked list (later a singularly linked list) that let me just do some quick pointer manipulation to get an answer in about a minute. That was good enough for what I needed, especially with two days remaining.

Day 24

Type of Problem: Coordinate System

Difficulty: Medium

Rating: 4/5

This one wasn’t too hard, once you figure out a hexagonal coordinate system. I reused an old problem’s trick to keep track of hexagons on the “outskirts” of my shape, and I was able to get this pretty close.

Given a hexagon at 0,0, here are the offsets for all the directions they can be (I picked this up from a Project Euler problem way back)

DIRECTIONS = {
    'e': (0, 1),
    'w': (0, -1),
    'ne': (.5, .5),
    'nw': (.5, -.5),
    'se': (-.5, .5),
    'sw': (-.5, -.5),
}

Day 25

Type of Problem: Iteration / Encryption

Difficulty: Easy

Rating: 3/5

I kept waiting for the other shoe to drop, but it was nice to have a super easy problem at the end of the line. Two quick for loops, and this problem was solved lickity-split. And with that, all 50 stars are done.