# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python # Advent of Code 2015 - Day 3

## 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:

• Using a Point class to represent Santa’s location
• Using Complex numbers to represent Santa’s location. It’s nearly identical, but quite a bit quicker.

## 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

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:

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

for vector in data: # read char by char
current_location += VECTORS[vector]

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:

• First I’ve created a `VECTORS` dictionary.
• Recall that a dictionary is composed of key:value pairs.
• In this case, our keys are the four navigation arrows (`^`, `v`, `>`, `<`) and their corresponding values are each a `Vector`, made up of `x,y` values that will result in the desired adjacent `Point`.
• Then we read in the single line of input data.
• We create a variable called `current_location` and initialise it to our starting location, i.e.the `Point` at `0, 0`.
• We add this starting location to our set of visited locations.
• We then process each character in the input data.
• Each character will be a navigation arrow.
• We use this to look up the appropriate `Vector` value.
• We add this `Vector` value to our `current_location`, to obtain a new `current_location`. It will always be adjacent to our old `current_location`.
• We add the new `current_location` to our set of visited locations.

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()
robosanta_visited_locations = set()

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

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

Here’s what’s going on:

• This time, we need to store two locations which will update throughout. I.e. the current location for Santa, called `santa_location`, and the current location for Robo-Santa, called `robosanta_location`. They both start at Point `0,0`.
• We now need two sets; one for each collection of unique points that have been visited by each of Santa and Robo-Santa.
• We process all the navigation instructions in the data, one character at a time, as before.
• Once again, we use enumerate to keep track of what iteration we’re currently performing. We store this in `i`.
• If the current character index position has a remainder of 1 after dividing by 2, then it must be an instruction for Santa.
• If the current character index position has a remainder of 0 after dividing by 2, then it must be an instruction for Robo-Santa.
• Update the appropraite current location, and the appropriate set, as required.
• Finally, obtain the union of the two sets (using the `|` operator), to determine the unique locations across both Santa’s set and Robo-Santa’s set. Recall that the union of a set means this: 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:

current_location = 0+0j
visited_locations = set()

for vector in data:
current_location += VECTORS[vector]

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

santa_location = robosanta_location = 0+0j

santa_visited_locations = set()
robosanta_visited_locations = set()

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

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")
``````
• Instead of using a dataclass to represent points and vectors, I’m simply storing each point and vector as a complex number. This saves on creating classes.
• We don’t have to write any code to be able to add points to vectors, since it’s easy to add complex numbers together.

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
``````