Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Perfectly Spherical Houses in a Vacuum

Advent of Code 2015 - Day 3

Day 3: Perfectly Spherical Houses in a Vacuum

Useful Links

‹›

Concepts and Packages Demonstrated

setdictionarydecoratorenumerateComplex Numbers

Page Contents

Problem Intro

We’re told that Santa is delivering presents to an infinite 2D grid of houses. We’re given a set of instructions that tells Santa how to navigate. With each instruction, Santa moves exactly one unit either north (^), south (v), east (>) or west (<).

The instructions are all on a single line of data, that looks something like this:

>^^v^<>v<<<v<v^>>v^^

I’ve solved today’s puzzle using two nearly identical solutions:

Part 1

How many houses receive at least one present?

This is simple enough to solve. We just need to track every location we’ve visited. At the end, we need to determine how many locations we visited. We don’t care about the order, and we don’t care about how many times a location was visited. Only whether it was visited or not.

Whenever you see a problem with these characteristics, then your brain should be screaming sets as the obvious way to go about it.

Setup

First we’ll do our imports and set up the Point and Vector classes we’ll use.

from dataclasses import dataclass
from pathlib import Path
import time

SCRIPT_DIR = Path(__file__).parent 
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")

@dataclass(frozen=True)
class Point:
    """ Class for storing a point x,y coordinate """
    x: int
    y: int
    
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

class Vector(Point):
    """ Same as a Point class. But more intuitive to treat deltas as vectors than points. """

We’ve made our Point class a dataclass, using the @dataclass decorator. Making it a dataclass saves us having to write a load of repetitive code. For example, we don’t have to supply an __init__() method, nor a __hash__() method to make instances of this class hashable.

Note that I’ve added an __add__() method, which overrides the __add__() method on the base object class. By doing this, we can add objects together by using the + operator. I.e. it allows us to write code like this:

new_thing = thing + other_thing

Specifically, our __add__() implementation creates a new Point object, by adding up the x and y values of two Point objects.

The next thing to note is that I’ve created a Vector class. But it’s actually identical to the Point class. In fact, I’ve created the Vector class by extending (subclassing) the Point class, but without adding any new methods, or overriding any existing methods. Thus, a Vector is still composed of nothing more than an x value, and a y value. Why have I bothered to create two classes that are identical? Well, it’s just to make the subsequent code more intuitive. For example, we can add two points together, but it’s more intuitive to add a Vector to a Point, to arrive at a new Point.

Solving

We only need to add this:

VECTORS = {
    '^': Vector(0, 1),
    '>': Vector(1, 0),
    'v': Vector(0, -1),
    '<': Vector(-1, 0)
}

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read()

    current_location = Point(0, 0)
    visited_locations = set()
    visited_locations.add(current_location)

    for vector in data: # read char by char
        current_location += VECTORS[vector]
        visited_locations.add(current_location)

    print(f"Santa visited {len(visited_locations)} locations.")

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

Explaining the above:

Finally, we count how many unique locations there are in current_locations, using len(current_locations). Every unique location will have received at least one present.

Easy!

Part 2

Now we have Robo-Santa! Santa and Robo-Santa take turns processing the instructions. Santa processes the 1st, 3rd, 5th instructions, etc. Robo-Santa processes teh 2nd, 4th, 6h instructions, etc.

As before, how many houses receive at least one present?

Solving

Not much needs to be added:

    santa_location = robosanta_location = Point(0,0)

    santa_visited_locations = set()
    santa_visited_locations.add(santa_location)
    robosanta_visited_locations = set()
    robosanta_visited_locations.add(robosanta_location)

    for i, vector in enumerate(data):
        if i % 2 == 1:
            santa_location += VECTORS[vector]
            santa_visited_locations.add(santa_location)
        else:
            robosanta_location += VECTORS[vector]
            robosanta_visited_locations.add(robosanta_location)

    visited_locations = santa_visited_locations | robosanta_visited_locations
    print(f"Santa and Robosanta visited {len(visited_locations)} locations.")

Here’s what’s going on:

Union

The output looks like this:

Santa visited 2592 locations.
Santa and Robosanta visited 2360 locations.
Execution time: 0.0219 seconds

Solving Using Complex Numbers

This solution is nearly identical to the previous solution. However, instead of using custom Point and Vector classes, I’m storing all points and vectors as complex numbers. If you’re unfamiliar with complex numbers (which really aren’t that complex) or how to use them in Python, first check out my introduction to complex numbers.

from pathlib import Path
import time

SCRIPT_DIR = Path(__file__).parent 
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")

VECTORS = {         # Store vectors as complex numbers
    '^': 0+1j,
    '>': 1+0j,
    'v': 0-1j,
    '<': -1+0j
}

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read()

    current_location = 0+0j
    visited_locations = set()
    visited_locations.add(current_location)

    for vector in data:
        current_location += VECTORS[vector]
        visited_locations.add(current_location)

    print(f"Santa visited {len(visited_locations)} locations.")

    santa_location = robosanta_location = 0+0j

    santa_visited_locations = set()
    santa_visited_locations.add(santa_location)
    robosanta_visited_locations = set()
    robosanta_visited_locations.add(robosanta_location)

    for i, vector in enumerate(data):
        if i % 2 == 1:
            santa_location += VECTORS[vector]
            santa_visited_locations.add(santa_location)
        else:
            robosanta_location += VECTORS[vector]
            robosanta_visited_locations.add(robosanta_location)

    visited_locations = santa_visited_locations | robosanta_visited_locations
    print(f"Santa and Robosanta visited {len(visited_locations)} locations.")

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

The output is just as before, but the code runs a lot quicker! Nearly six times faster. So, working with complex numbers is inherently faster than building our own classes to do the same job.

Santa visited 2592 locations.
Santa and Robosanta visited 2360 locations.
Execution time: 0.0037 seconds

‹›