Link to Advent of Code day 16

Not super happy with this day, but because of myself: I think the code for part 1 is okay; I rushed part 2 to catch up on the days I missed, and so the code is slow and not very elegant. I'll explain what could be improved in this post tho, I just didn't have time to implement it.

Part 1

Rules

The rules of today are simple to explain and understand. We have a map of mirrors, looking like this:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....

There is a beam entering from the top-left corner from the left and heading to the right. It's behavior will then depends of the tile it encounters:

1. . is an empty tile, it continue its way
2. / and \ are 90 degrees mirrors. The beam will turn according to the angle of the mirror
3. | and - are splitters. If the beam is coming on the flat side, it will split in 2 different beams. For example, if the beam is going to the west and encounter a | splitter, it will split in one beam going North and one beam Going south. If the beam do not encounter the flat side, it will go through the splitter.

With the previous example, the beam path will look like this:

>|<<<\....
|v-.\^....
.v...|->>>
.v...v^.|.
.v...v^...
.v...v^..\
.v../2\\..
<->-/vv|..
.|<<<2-|.\
.v//.|.v..

One the beam is simulated, we just count the energized tiles, which are the tiles were a beam was moving. With this example, we would have 46 energized tiles:

######....
.#...#....
.#...#####
.#...##...
.#...##...
.#...##...
.#..####..
########..
.#######..
.#...#.#..

Lets start solving this !

Code

First, I start by writing an implementation for the beam. I though the easier way would just to have a point, with values y, x and a value direction. The value direction would be the the index of an array, containing the values to add to y, x to move in the correct direction.

For example, to move north, the values to add to y, x are -1, 0.

I then implements 3 methods for convenience: a method move, which will apply the modifier we just talked about to move the beam. And the methods rotate_slash and rotate_bslash, which will rotate the beam in the correct direction when encountering a mirror:

from dataclasses import dataclass

EMPTY = "."
SLASH = "/"
BSLASH = "\\"
VERTICAL = "|"
HORIZONTAL = "-"

NORTH = 0
SOUTH = 1
WEST = 2
EAST = 3

DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]


@dataclass
class Beam:
    y: int
    x: int
    direction: int

    def advance(self):
        y_delta, x_delta = DIRECTIONS[self.direction]
        self.y += y_delta
        self.x += x_delta

    def rotate_slash(self):
        self.direction = {
            NORTH: EAST,
            EAST: NORTH,
            SOUTH: WEST,
            WEST: SOUTH,
        }[self.direction]

    def rotate_bslash(self):
        self.direction = {
            NORTH: WEST,
            EAST: SOUTH,
            SOUTH: EAST,
            WEST: NORTH,
        }[self.direction]

    def __hash__(self):
        return hash((self.y, self.x, self.direction))

Note that I also implemented the __hash__ method, because I plan to use some set a bit later.

We then have to implements the mirror map class. Processing the path of a beam is straightforward, there is only 2 cases we need to handle:

1. There could be an infinite loop with a beam. To handle this, the map will contains an history field. If at some point, a beam find itself in a state (y, x, direction) which is already in the history field, we stop to simulate this beam.
2. We need to handle the fact that a beam can split in 2, and that we would have to process the 2 beams. For this, I added a field beams to the map, in which we can push the beams we have to process. This way if a beam split, we just have to push 2 beams into this field, and stop processing the current beam.

With this, we call the method process, which will process beams into self.beams until there is none remaining. The method process_beam will just simulate a beam, tile by tile, until it enters an infinite loop, or go outside of the map:

from collections import deque
from copy import copy


class MirrorMap:
    def __init__(self, mirrors: list[list[str]]):
        self.beams = deque([Beam(0, 0, EAST)])
        self.mirrors = mirrors
        self.history = set()

    def process(self):
        while self.beams:
            current_beam = self.beams.pop()
            self.process_beam(current_beam)

    def process_beam(self, beam: Beam):
        while True:
            if beam in self.history or self.out_of_map(beam):
                return

            self.history.add(copy(beam))
            tile = self.mirrors[beam.y][beam.x]

            if tile == SLASH:
                beam.rotate_slash()
            elif tile == BSLASH:
                beam.rotate_bslash()
            elif tile == VERTICAL and beam.direction in (EAST, WEST):
                up_beam = Beam(beam.y - 1, beam.x, NORTH)
                down_beam = Beam(beam.y + 1, beam.x, SOUTH)
                self.beams.append(up_beam)
                self.beams.append(down_beam)
                return

            elif tile == HORIZONTAL and beam.direction in (NORTH, SOUTH):
                left_beam = Beam(beam.y, beam.x - 1, WEST)
                right_beam = Beam(beam.y, beam.x + 1, EAST)
                self.beams.append(left_beam)
                self.beams.append(right_beam)
                return
            beam.advance()

    def out_of_map(self, beam: Beam) -> bool:
        return beam.y < 0 or beam.x < 0 or beam.y >= len(self.mirrors) or beam.x >= len(self.mirrors[0])

Once this is done, we have to calculate the amount of energized tiles. Since two beams on the same tile will still count as one energized tile, a set with only the coordinates y, x of each beam in the history is a good way to get rid of duplicates:

class MirrorMap:

    # ...

    def get_energized_tiles(self) -> int:
        return len({(t.y, t.x) for t in self.history})

The part one then just consist of calling process and get_energized_tiles on the mirror map. I did not detailed the parse function which has nothing specially interesting:

def part_one(input_file: str):
    mirror_map = get_mirrors_map(input_file)
    mirror_map.process()
    return mirror_map.get_energized_tiles()

Part 2

Rules & Solution

This is were things get ugly.

The twist for part 2 is that we have to simulate each beam coming from each edge of the map.

By lack of time, I just implemented a bruteforce method, simulating every possible beam from each direction:

class MirrorMap:
    # ...

    def clear(self):
        """Reset the MirrorMap instance to a new state, by cleaning the history and beams """
        self.beams = deque()
        self.history = set()

def part_two(input_file: str):
    mirror_map = get_mirrors_map(input_file)
    max_energized_tiles_nbr = 0
    height = len(mirror_map.mirrors)
    width = len(mirror_map.mirrors[0])

    # Top -> South
    for x in range(width):
        mirror_map.clear()
        mirror_map.beams.append(Beam(0, x, SOUTH))
        mirror_map.process()
        max_energized_tiles_nbr = max(max_energized_tiles_nbr, mirror_map.get_energized_tiles())

    # Bottom -> North
    # Same logic ...

    # Left -> East
    # Same logic ...

    # Right -> West
    # Same logic ...

    return max_energized_tiles_nbr

Of course this is super slow. The solution I would like to implement, when I have time, is to keep an history per beam. This should be implemented in a way were given a Beam coordinates and directions, we could retrieve all the tiles which the beam would go through. With this, we could do caching, and avoid computing a huge part of the simulations.

Anyway, I'll try to come back on this when have I time, but day 16 is still solved !

---

All the code is available on github