Dazbo's Advent of Code solutions, written in Python

Day 3: Perfectly Spherical Houses in a Vacuum

setdictionarydecoratorenumerateComplex Numbers

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.

**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.

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`

.

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:

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

.

- Recall that a
- 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!

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?**

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:

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

- Once again, we use enumerate to keep track of what iteration we’re currently performing. We store this in
- 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
```

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

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