Advent of Code - 2015

This is a solution to Day 3 of Advent of Code 2015.

Day 3 - Perfectly Spherical Houses in a Vacuum

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.

For example:

• > delivers presents to 2 houses: one at the starting location, and one to the east.
• ^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.
• ^v^v^v^v^v delivers a bunch of presents to some very lucky children at only 2 houses.

Read input

from utils import read_input


def transformer(line):
    return list(line)

instructions = read_input(3, transformer)[0]

Part 1

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

When doing the 2021 puzzles, I learned a cool trick of using complex numbers for 2D directions from Tess Ferrandez so I wanted to try it out here.

The way it works is that for a complex number x + yj, x is the x coordinate and y is the y coordinate.

Adding +1 moves east, -1 moves west, +1j moves north and -1j moves south.

After each instruction, we calculate the new position as complex number and add it to a set. Sets only keep unique entries so even if we visit a house again, it won't be counted as double.

The initial position 0 + 0*1j is same as just 0 but for the sake of clarity, I like to keep the non-existent imaginary part there to give a hint for the reader on what's happening.

def how_many_houses(instructions):
    current_position = 0 + 0 * 1j
    
    visited = set([current_position])
    for instruction in instructions:
        match instruction:
            case '^':
                current_position += 1j
            case 'v':
                current_position -= 1j
            case '>':
                current_position += 1
            case '<':
                current_position -= 1

        visited.add(current_position)
    
    return len(visited)

result = how_many_houses(instructions)
print(f'Solution: {result}')
assert result == 2081

Part 2

The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.

Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.

This year, how many houses receive at least one present?

For example:

• ^v delivers presents to 3 houses, because Santa goes north, and then Robo-Santa goes south.
• ^>v< now delivers presents to 3 houses, and Santa and Robo-Santa end up back where they started.
• ^v^v^v^v^v now delivers presents to 11 houses, with Santa going one direction and Robo-Santa going the other.

For the second part, we keep track of both positions in a list and use the modulo of the instruction index (to alternate between 0 and 1) and otherwise keep the logic the same.

def double_duty(instructions):
    positions = [
        0 + 0 * 1j,
        0 + 0 * 1j
    ]
    
    visited = set(positions)
    
    for idx, instruction in enumerate(instructions):
        match instruction:
            case '^':
                positions[idx % 2] += 1j
            case 'v':
                positions[idx % 2] += -1j
            case '>':
                positions[idx % 2] += 1
            case '<':
                positions[idx % 2] += -1

        visited.add(positions[idx % 2])

    return len(visited)

result = double_duty(instructions)

print(f'Solution: {result}')       
assert result == 2341

Appendix A: Generalized solution

Occasionally I add an Appendix at the end to showcase a piece of code or an interesting tidbit that I didn't want to mix with the real solution.

This solution can be generalized to allow any number of operators (maybe Mrs. Claus will join the taskforce one year).

def christmas_travel(instructions, operators=1):
    positions = [0 + 0 * 1j for _ in range(operators)]
    
    visited = set(positions)
    
    for idx, instruction in enumerate(instructions):
        operator = idx % operators
        match instruction:
            case '^':
                positions[operator] += 1j
            case 'v':
                positions[operator] += -1j
            case '>':
                positions[operator] += 1
            case '<':
                positions[operator] += -1

        visited.add(positions[operator])

    return len(visited)

assert christmas_travel(instructions, 1) == 2081
assert christmas_travel(instructions, 2) == 2341

Appendix B: Using a dictionary

My initial solution used a dictionary to keep track of how many times we visited each place. Since that wasn't eventually necessary in part 2 either, I refactored it out in favor of using sets.

Here's who you'd do it with a Counter that is a specialized dictionary that provides nice helper functions for different counting related operations like most_common that returns a list of tuples (value, key) sorted by value descending.

from collections import Counter

# other code here
visited = Counter()
# more code

# Log a visit
visited[positions[operator]] += 1

# rest of the code

# Get most common places
visited.most_common()