AoC 2020 Day 24 — Representing Hexagonal Tiling with Cube Coordinates

This is part of a series we did on the Advent of Code 2020 problems. You can see a list of all the problems we wrote about here.
If you are a fan of AoC, and had fun working on these problems, it is likely that you would be a good fit with our team. Our engineering team had a blast with it, as we like to be challenged with hard problems. If you like what you see, we are constantly looking for great talent, please consider joining us!

Day 24’s story involved renovating a hexagonally tiled floor. Each of these tiles is black on one side and white on the other. Initially, they all have their white side facing up. Like other AoC problems, this challenge is split into two parts. In part 1, we are given a list of tiles to flip over. In part 2, the tiles are then flipped daily according to specific rules.

In this post, I will be sharing my Python solution to this problem.

Defining a Coordinate System

The first task was to find a way to represent each tile in a coordinate system. Each tile has 6 neighbours in the directions: east, southeast, southwest, west, northwest, and northeast (encoded as e,se,sw,w,nw,ne respectively).

By Watchduck (a.k.a. Tilman Piesk) — Own work, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=97281922

Although we are dealing with a 2-d surface, hexagonal tiles have a nice property in that they can be elegantly expressed as in 3-d coordinates. This is done by visualising each hexagon as a cube in three dimensions.

visualising each tile as a cube

We can now define directions based on this visualization. Each tile can now be identified by a unique 3-d coordinate. We can represent these directions as numpy arrays.

Defining 3-d coordinates for hexagonal tiles

DIRS = {
    "ne": np.array([0, 1, 1]),
    "e":  np.array([1, 1, 0]),
    "se": np.array([1, 0, -1]),
    "sw": np.array([0, -1, -1]),
    "w":  np.array([-1, -1, 0]),
    "nw": np.array([-1, 0, 1])
}

Part 1

For part 1, we are given a list of tiles represented as directions from a reference tile (which we will consider the origin (0,0,0)). These directions are a concatenation of the directions (e,se,sw,w,nw,ne). The first task is to iterate through the tiles and flip them (from black to white or vice-versa). The puzzle solution is to count the number of tiles with their black side facing up at the end.

Puzzle input:
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
...

First, we need to split the directions each tile into its constituent parts.

def split_tile_directions(tile_directions: str) -> List[str]:
    res = []
    while tile_directions:
        for d in ["nw", "ne", "sw", "se", "e", "w"]:
            if tile_directions.startswith(d):
                res.append(d)
                tile_directions = tile_directions[len(d):]
                break
    return res
>>> split_tile_directions("neeswseenwwswnwswsw")
['ne', 'e', 'sw', 'se', 'e', 'nw', 'w', 'sw', 'nw', 'sw', 'sw']

Then we can use our direction vectors to compute the coordinates of the tile. The resulting coordinate can be represented as a tuple of three integers.

def get_tile(tile_directions: List[str]) -> Tuple[int, int, int]:
    res = np.array([0, 0, 0])
    for d in tile_directions:
        res += DIRS[d]
    return tuple(res.tolist())
>>> get_tile(split_tile_directions("neeswseenwwswnwswsw"))
(0, -2, -2)

We can keep track of the black tiles with a set. Tiles not in the set are assumed to be white. We can now do part 1 buy iterating over the list of tiles. If the tile is in the set, it is black so remove it from the set to make it white. If the tile is not in the set, it is white so add it to the set to make it black. Then take the size of the set to get the desired answer.

black_tiles = set()
for line in input:
    tile = get_tile(split_tile_directions(line.strip()))
    if tile in black_tiles:
        black_tiles.remove(tile)
    else:
        black_tiles.add(tile)

    print("Part 1", len(black_tiles))

Part 2

For part 2, we have to simulate some daily rules which causes the tiles to change. The rules are as follows:

Any black tile with zero or more than 2 black tiles immediately adjacent to it is flipped to white.

Any white tile with exactly 2 black tiles immediately adjacent to it is flipped to black.

The files are all flipped at once based on these rules.

Because the bounds of the room are not given, we need to first collect a list of tiles to consider. We do this by taking all the black tiles and their adjacent neighbours. These are all the tiles which may be flipped at any given day.

The tiles to consider are the black tiles and their 6 adjaced tiles

def get_all_adjacent(
    tile: Tuple[int, int, int]
) -> List[Tuple[int, int, int]]:
    res = []
    for d, vec in DIRS.items():
        res.append(tuple(np.array(tile) + vec))
    return res

def get_all_tiles_to_consider(
    black_tiles: Set[Tuple[int, int, int]]
) -> Set[Tuple[int, int, int]]:
    res = set()
    for black_tile in black_tiles:
        res.add(black_tile)
        res.update(get_all_adjacent(black_tile))
    return res

To get the desired solution. We simulate 100 days under these rules. For each day, we gather all the tiles to consider. Then, we determine which ones need to be flipped and create a new set of black tiles. We count the number of black tiles at the end to give the desired solution.

for day in range(100):
    all_tiles = get_all_tiles_to_consider(black_tiles)
    new_black_tiles = set()
    for tile in all_tiles:
        adjacent_black_tiles =  \
            len(set(get_all_adjacent(tile)) & black_tiles)
        if tile in black_tiles and adjacent_black_tiles in [1, 2]:
            new_black_tiles.add(tile)

        if tile not in black_tiles and adjacent_black_tiles == 2:
            new_black_tiles.add(tile)

        black_tiles = new_black_tiles
        print("Part 2", len(black_tiles))

The full code can be found here.

I hope you enjoyed reading about this problem. I had fun working on it, and I would encourage you to take a look at the other entries in this series. If you are passionate about software engineering and solving difficult problems, we are constantly hiring for talented engineers.