Advent of Code

A lot easier than the previous day for me. A few bugs along the way, but mostly due to me forgetting things that I shouldn’t.

We have several symbols on the map. Each represents an “antenna” with a given “frequency”. Antennas with the same symbol have the same frequency, and for each pair of antenna of the same type, it will create a “signal” in both directions at the same distance as the distance between the two antennas. To make things clearer, another example was given with just two antennas:

With # showing where the signals are. The solution of the first part is the number of unique locations within the boundaries of the grid for the signals.

Parsing the grid

def load_as_grid(fname: str | pathlib.Path) -> list[list[str]]:
    data = []
    with open(fname, 'r') as fp:
        data = fp.readlines()
    return [[c for c in row.strip()] for row in data if len(row) != 0]

I decided to use classes this time around to store the “Grid” information. I put the symbols as keys in a dict, associated to a list of positions. I also store the grid boundaries.

class Grid:
    def __init__(self, grid: list[list[str]]):
        self.symbols = {}
        self.maxrows = len(grid)
        self.maxcols = len(grid[0])
        for i, row in enumerate(grid):
            for j, s in enumerate(row):
                if s != '.':
                    if s not in self.symbols:
                        self.symbols[s] = []
                    self.symbols[s].append(Position(row=i, column=j))

def load_grid(suffix: str):
    data = load_as_grid("day8")
    return Grid(data)

Positions and vector operations

For the Position I initially went for a namedtuple like in Day 6, but since I had decided on using vector arithmetic for later I then thought it would be cleaner to make a class with the appropriate __add__, __sub__ and __mul__ methods:

class Position:
    def __init__(self, row, column):
        self.row = row
        self.column = column

    def __add__(self, other):
        return Position(self.row+other.row, self.column+other.column)
    
    def __sub__(self, other):
        return Position(self.row-other.row, self.column-other.column)
    
    def __mul__(self, other):
        if type(other) is Position:
            return Position(self.row*other.row, self.column*other.column)
        
        return Position(self.row*other, self.column*other)

That way I could add, subtract or multiply (elementwise) two vectors with the standard operators, and also scale the vector by multiplying with a scalar.

Solving Part 1

I then wrote a function to find the two signal positions based on a pair of antennas. Thanks to the overloaded operators, this becomes very easy to do, with some added boundary checks:

def find_locations(a: Position, b: Position, maxrows: int, maxcols: int) -> set[Position]:
    v = (b-a)
    p1 = b+v
    p2 = a-v

    locations = set()
    if 0 <= p1.row < maxrows and 0 <= p1.column < maxcols:
        locations.add(p1)
    if 0 <= p2.row < maxrows and 0 <= p2.column < maxcols:
        locations.add(p2)

    return locations

We return a set of locations, as we know we only need to keep unique locations. The only thing left to do is to find all the pairs. Thankfully, itertools once again comes in handy, as combinations does exactly what we need.

def find_all_locations(grid: Grid):
    unique_locations = set()
    for symbol, positions in grid.symbols.items():
        if len(positions) < 2:
            continue
        for pairs in itertools.combinations(positions, 2):
            unique_locations = unique_locations.union(find_locations(*pairs, grid.maxrows, grid.maxcols))
    return unique_locations

That… didn’t work. It took me some time to understand why I couldn’t get the right answer, then I realised that set had no way to realize which positions were duplicates. It just saw a bunch of different instances of the Position class and therefore happily included the same position multiple times. Fortunately it’s an easy fix: we just need to add an __eq__ method to overload the == operator, and a __hash__ method to be hashable. I’m not sure why it didn’t raise an exception when I used it without either, but I get it if I implement __eq__ but not __hash__. Anyway, for the hash I decided to just return the hash of the tuple (row, column). While I was in full dunder-method mode I also added a __repr__ so that I could more easily print positions.

class Position:
    ...
    def __repr__(self):
        return f"Position(row={self.row}, column={self.column})"
    
    def __eq__(self, other):
        return (self.row == other.row) and (self.column == other.column)
    
    def __hash__(self):
        return (self.row, self.column).__hash__()

Solving part 2

Part 2 only slightly changed the rules, and for once my choices in Part 1 really helped keep the changes minimal for Part 2.

Now, instead of having two signals at B + AB and A-AB, we had a signal at A + k.AB for every k that kept the signal within boundaries. This is my mathematical rewording of the problem. The text is a bit confusing, but from the example it’s clear that’s what it means (and since I got the right solution from that definition, I guess it has to work!)

So we basically only need to change the function that finds the signal locations from the pair of antennas a and b. We start by adding a and b to the set (k=0 and k=1), then we search in both directions (k>2 and k<0) until we hit the boundaries of the map.

def in_bounds(position: Position, maxrows: int, maxcols: int):
    return (0 <= position.row < maxrows and 0 <= position.column < maxcols)

def find_locations_in_line(a: Position, b: Position, maxrows: int, maxcols: int) -> set[Position]:
    v = (b-a)
    
    locations = {a, b}

    # search in a->b direction:
    k = 2
    while in_bounds((p := a + v*k), maxrows, maxcols):
        locations.add(p)
        k += 1
    
    # search in b->a direction:
    k = -1
    while in_bounds((p := a + v*k), maxrows, maxcols):
        locations.add(p)
        k -= 1

    return locations

I initially didn’t add a and b, which was my second stupid bug of the day, but I eventually noticed and corrected the code.

Advent of Code - Day 8

Day 8 - vectors and boundaries

Parsing the grid

Positions and vector operations

Solving Part 1

Solving part 2