Advent of Code

Day 15: aaaaargh. That was painfully long. But the end result is really fast and, I think, not too stupid. Day 15 is not about clever math, and I don’t think there really is a “trick” to making it work. Anyway, let’s get into it.

Part 1 - box-pushing

We have another map, with a robot and a set of instructions. This time the robot is a box-pusher (so we also have boxes). And the instructions are simply a list of directions. So the example input is:

Where @ is the robot, # are walls, 0 are boxes and . are empty spaces. Then we have the list of movements in order. We have to determine where all the boxes will be, with the rules being:

I’m not going to go through all my attempts at making this work (you can check my commits if you’re into that kind of things), so let’s directly explain the version that did work nicely. I went object-oriented for this one, as it seemed like the most natural way of implementing things.

Position = namedtuple("Position", ["row", "column"])

up = lambda r, c : Position(r-1, c)
down = lambda r, c : Position(r+1, c)
left = lambda r, c : Position(r, c-1)
right = lambda r, c : Position(r, c+1)

movements = {'^': up, 
             'v': down,
             '<': left,
             '>': right}
movements_keys = {val: key for key, val in movements.items()}

I’ve done similar things in previous rounds: that way we can pass “direction” as lambda functions to other methods, which makes the rest of the code a lot more neat as we avoid systematically having to lookup a string-to-callable dictionary. We only need that dictionary when parsing the string from the input.

The most important class that we define is the MoveableItem. It keeps track of the position of an item, and has two important methods: moveable, which checks if the item can move in a given direction, and move, which performs the actual movement. An item is moveable in a direction if the grid in that direction is empty or if it contains an object which is also moveable in that direction. To perform the move, it first has to push any item that is in the way by calling their move method, then it has to update the grid to remove itself from the current position, updating its positions, and adding itself back to the grid.

class MoveableItem:
    def __init__(self, grid: dict[Position, Box], row: int, column: int):
        self.grid = grid
        self.row = row
        self.column = column
        self.symbol = '?'

    @property
    def position(self) -> Position:
        return Position(self.row, self.column)
    
    def moveable(self, direction: Callable) -> bool:
        p = direction(*self.position)
        if self.grid.get(p) is None:
            return True
        return self.grid[p].moveable(direction)
    
    def move(self, direction: Callable) -> bool:
        if not self.moveable(direction):
            return False

        p = direction(*self.position)
        if self.grid.get(p) is not None:
            self.grid[p].move(direction)

        self.grid[self.position] = None
        self.row, self.column = p.row, p.column
        self.grid[p] = self

        return True

    def __repr__(self) -> str:
        return self.symbol + f"({self.row}, {self.column})"

A wall, meanwhile, cannot move, so we implement a very simple Wall class, which tells anyone who asks that no, they are not moveable:

class Wall:
    def __init__(self):
        self.symbol = '#'
    
    def moveable(self, direction: Callable) -> bool:
        return False

A box is a moveable item with the box symbol, and an addition function to compute the “GPS” coordinates which are to be summed to get the puzzle answer.

class Box(MoveableItem):
    def __init__(self, grid: dict[Position, Box], row: int, column: int):
        super().__init__(grid, row, column)
        self.symbol = 'O'

    @property
    def gps(self) -> int:
        return self.row*100 + self.column

class Robot(MoveableItem):
    def __init__(self, grid, row: int, column: int):
        super().__init__(grid, row, column)
        self.symbol = '@'

Now we have to initialize the grid and get the list of movements by parsing the input file. Since walls only need to tell that they are not moveable, we actually only need one instance of Wall, which we will point to from each position in the grid where there’s a wall. Otherwise, each time we find a box or the robot, we instanciate the relevant class and add a reference to the grid, which will be a dictionary mapping Position to MoveableItem or Wall (or None if there’s nothing).

Item = None | MoveableItem | Wall

def normal_grid(grid_data: list[str]) -> tuple[dict[Position, Item], Robot]:
    grid = {}
    robot = None
    w = Wall()
    for r, row in enumerate(grid_data):
        for c, val in enumerate(row):
            if val == '#':
                grid[Position(r, c)] = w
            elif val == 'O':
                b = Box(grid, r, c)
                grid[Position(r, c)] = b
            elif val == '@':
                assert robot is None
                robot = Robot(grid, r, c)
                grid[Position(r, c)] = robot
    return grid, robot

def parse_input() -> tuple[dict[Position, Item], Robot, list[Callable]]:
    with open(fname, 'r') as fp:
        data = fp.read()

    grid, instructions = data.split('\n\n')
    grid = grid.split('\n')
    grid, robot = parse_grid(grid)

    moves = []
    for s in instructions.replace('\n', ''):
        moves.append(movements[s])
    return grid, robot, moves

Once we’ve done all of that, applying the moves becomes extremely easy and satisfying:

def apply_moves(grid: dict[Position, Item], 
                robot: Robot,
                moves: list[Callable]) -> tuple[dict[Position, Item], Robot]:
    for d in moves:
        robot.move(d)

    return grid, robot

grid, robot, moves = parse_input()
grid, robot = apply_moves(grid, robot, moves)
boxes = [b for b in grid.values() if type(b) == Box]
print(sum(set(b.gps for b in boxes)))

That’s it: just move the robot, and the interactions between the classes will take care of the rest. robot.move(d) will automatically “push” any box in the way.

Part 2 - thicc boxes

For part two, we make everything wider. We take the same map, but double the width of the walls and the boxes, with only the robot staying the same. So the example map looks like:

The good thing is that, at least with my implementation, it doesn’t change anything for the walls and the robot. But we need a new class for the large boxes to implement these new behaviours. I’ve gone through many possible solutions, but eventually I settled on a LargeBox class that inherits Box and modifies it like this:

class LargeBox(Box):
    def __init__(self, grid: dict[Position, Box], row: int, column: int):
        super().__init__(grid, row, column)

    @property
    def positions(self) -> list[Position]:
        return [Position(self.row, self.column), Position(self.row, self.column+1)]

    def get_neighbours(self, direction: Callable) -> set[None | Box | LargeBox | Wall | Robot]:
        if direction == left:
            return set([self.grid.get(Position(self.row, self.column-1))])
        if direction == right:
            return set([self.grid.get(Position(self.row, self.column+2))])
        if direction == up:
            return set([self.grid.get(Position(self.row-1, self.column)), self.grid.get(Position(self.row-1, self.column+1))])
        if direction == down:
            return set([self.grid.get(Position(self.row+1, self.column)), self.grid.get(Position(self.row+1, self.column+1))])

    def _moveable_to(self, p: Position, direction: Callable) -> bool:
        if self.grid.get(p) is None:
            return True
        return self.grid[p].moveable(direction)

    def moveable(self, direction: Callable) -> bool:
        neighbours = self.get_neighbours(direction)
        for n in neighbours:
            if n is not None and not n.moveable(direction):
                return False
        return True
    
    def move(self, direction: Callable) -> bool:
        if not self.moveable(direction):
            return False
        
        neighbours = self.get_neighbours(direction)

        for n in neighbours:
            if n is not None:
                n.move(direction)

        for p in self.positions:
            self.grid[p] = None
        self.row, self.column = direction(*self.position)
        for p in self.positions:
            self.grid[p] = self
        
        return True

We also need a new grid parsing function, which is the same as the old one but we double the column position to get the right “enlarged” coordinates, and we put two walls or a LargeBox wherever they are needed.

def wide_grid(map: list[str]) -> tuple[dict[Position, Item], Robot]:
    grid = {}
    robot = None
    w = Wall()
    for r, row in enumerate(map):
        for c, val in enumerate(row):
            if val == '#':
                grid[Position(r, c*2)] = w
                grid[Position(r, c*2+1)] = w
            elif val == 'O':
                b = LargeBox(grid, r, c*2)
                grid[Position(r, c*2)] = b
                grid[Position(r, c*2+1)] = b
            elif val == '@':
                assert robot is None
                robot = Robot(grid, r, c*2)
                grid[Position(r, c*2)] = robot
    return grid, robot

And with those modifications in place, we can now move the robot in the updated grid, and it works nicely.