Advent of Code 2020: Day 24

, 11 min read
advent of code 2020

Part 1

Your raft makes it to the tropical island; it turns out that the small crab was an excellent navigator. You make your way to the resort.

As you enter the lobby, you discover a small problem: the floor is being renovated. You can’t even reach the check-in desk until they’ve finished installing the new tile floor.

The tiles are all hexagonal; they need to be arranged in a hex grid with a very specific color pattern. Not in the mood to wait, you offer to help figure out the pattern.

The tiles are all white on one side and black on the other. They start with the white side facing up. The lobby is large enough to fit whatever pattern might need to appear there.

A member of the renovation crew gives you a list of the tiles that need to be flipped over (your puzzle input). Each line in the list identifies a single tile that needs to be flipped by giving a series of steps starting from a reference tile in the very center of the room. (Every line starts from the same reference tile.)

Because the tiles are hexagonal, every tile has six neighbors: east, southeast, southwest, west, northwest, and northeast. These directions are given in your list, respectively, as e, se, sw, w, nw, and ne. A tile is identified by a series of these directions with no delimiters; for example, esenee identifies the tile you land on if you start at the reference tile and then move one tile east, one tile southeast, one tile northeast, and one tile east.

Each time a tile is identified, it flips from white to black or from black to white. Tiles might be flipped more than once.

Go through the renovation crew’s list and determine which tiles they need to flip. After all of the instructions have been followed, how many tiles are left with the black side up?

You can read the full text here. The hexagons are back. Fortunately, I’ve solved hexagon problems before. As have many veteran advent of coders.

Nice tiled floor
Hexagon tiled floor

I think today we will start with the input, as usual. In this problem the input is a series of lines, each line is a string which describes the steps taken to go from some reference tile to another tile. Each time a tile is visited, we flip it.

Consider the line below,

1
nwwswee

Which means “North West”, “West”, “South West”, “East” and “East”. I’m going to give each of the directions a number,

1
2
 0   1   2  3   4   5
 W, NW, NE, E, SE, SW

Thus, we go through the input file and make a vector of these numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
std::vector<std::vector<int>> directions;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
    std::vector<int> direction;
    size_t col = 0;
    while(col < line.size()) {
        if (line[col] == 'n'){
            col++;
            if (line[col] == 'w')
                direction.push_back(1);
            else if (line[col] == 'e')
                direction.push_back(2);
            col++;
        }
        else if (line[col] == 's'){
            col++;
            if (line[col] == 'w')
                direction.push_back(5);
            else if (line[col] == 'e')
                direction.push_back(4);
            col++;
        }
        else if (line[col] == 'w'){
            direction.push_back(0);
            col++;
        }
        else if (line[col] == 'e'){
            direction.push_back(3);
            col++;
        }
    }
    directions.push_back(direction);
}
myfile.close();

This code just maps the characters, as described above, into a vector of integers representing each hexagon’s direction. We achieve this with string manipulation. Every direction is either a single character or two characters.

Now we need a way to navigate to each of these tiles from our starting position, (0, 0). For this I’m following this convention. This convention can be derived from this. I’ll breifly explain it below, but please see the original source it is much better.

Consider a row of hexagons,

1
2
3
| 0, 0 | 0, 1 | 0, 2 | 0, 3 |
    | 1, 0 | 1, 1 | 1, 2 | 1, 3 |
| 2, 0 | 2, 1 | 2, 2 | 2, 3 |

Where the two numbers show the row and column number, respectively. Imagine you are at (2, 1). If you go south east you end up at (1, 1), the column number didn’t change. However, if you go south east again from (1, 1), you arrive at (0, 2). Thus, the column number did change. On even rows going south east keeps the column number the same, but on odd rows, it increases by 1. Conversely, going south west from an even row decreases the column number by 1, but from an odd row, it remains the same. Thus, we have these parity rules which can handle the offsets of the hexagonal grid. We can then implement this in code.

1
2
3
4
5
std::pair<int, int> calculate_neighbour_loc(std::pair<int, int> coord, int direction){
    int parity = coord.second & 1;
    std::pair<int, int> dir = direction_offset[parity][direction];
    return {coord.first + dir.first, coord.second + dir.second};
}

Given some coordinates, coord, we first check the parity and then we can just use some pre-generated look up tables to determine what we should add to both our row and column to step in a given direction. These look up tables are as follows,

1
2
3
4
5
6
// 0   1   2  3   4   5
// W, NW, NE, E, SE, SW
const std::vector<std::vector< std::pair<int, int> > > direction_offset = {
    {{+1,  0}, { 0, -1}, {-1, -1}, {-1,  0}, {-1, +1}, { 0, +1}},
    {{+1,  0}, {+1, -1}, { 0, -1}, {-1,  0}, { 0, +1}, {+1, +1}},
};

The first row is for odd rows, and the second row is for even rows. The 6 pairs of directions in each row tell us how to step west, north west, north east, east, south east and southwest, respectively.

Now, we set up our grid of tiles as a map which defaults to zero in every location. We loop over all of the input directions, and calculate which hexagon we are at and just change the colour. If it was white, 0, we swap to black, 1 and vice versa.

1
2
3
4
5
6
7
8
9
// Flip tiles from input
std::map<std::pair<int, int>, int> grid;
for (auto direction : directions){
    std::pair<int, int> loc = {0, 0};
    for(auto d : direction){
        loc = calculate_neighbour_loc(loc, d);   
    }
    grid[loc] ^= 1;
}

Now just pass over the grid and count all of the black tiles,

1
2
3
4
5
6
7
8
int count_black(std::map<std::pair<int, int>, int> &grid){
    int tot = 0;
    for(auto &kv : grid){
        if (kv.second == 1)
            tot++;
    }
    return tot;
}

Woo the first ⭐ of Christmas Eve!

The full code can be found on github

Part 2

The tile floor in the lobby is meant to be a living art exhibit. Every day, the tiles are all flipped according to the following rules:

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

Here, tiles immediately adjacent means the six tiles directly touching the tile in question.

The rules are applied simultaneously to every tile; put another way, it is first determined which tiles need to be flipped, then they are all flipped at the same time.

How many tiles will be black after 100 days?

You can read the full text here. This is similar to previous problems. We now need to be able to identify neighbours of each tile and check how many of them are black.

Let’s start by taking our map from part 1 and removing every location that is 0. Thus, the map will now only contain locations where the tiles are black.

1
2
3
4
5
6
for(auto it = grid.begin(); it != grid.end();){
    if(it->second == 0)
        it = grid.erase(it);
    else
        ++it;
}

Awesome. Every location in our map grid now corresponds to a black hexagon. We just need to write a function that loops over the grid and generates a new map with different coloured tiles based on the above rules. I’ll paste the code below it and then we can walk through it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
std::map<std::pair<int, int>, int> flip_tiles(std::map<std::pair<int, int>, int> grid){
    std::map<std::pair<int, int>, int> new_grid;

    for(auto &kv : grid){
        int black_neighbours = 0;

        // Test the neighbours of our currently black tile
        for (int j=0; j<6; j++){
            // Get tile location
            std::pair<int, int> loc = calculate_neighbour_loc(kv.first, j);

            // If this is a black tile, skip, becuase we will test is seperately
            if (grid.find(loc) != grid.end()){
                black_neighbours++;
                continue;
            }

            // Count black neighbours
            int neighbours = 0;
            for(int i=0; i<6; i++)
                if (grid.find(calculate_neighbour_loc(loc, i)) != grid.end()){
                    neighbours += 1;
                    if (neighbours > 2)
                        break;
                }

            // Should we turn black?
            if (neighbours == 2)
                new_grid[loc] = 1;
        }

        // Test the current black tile
        if ((black_neighbours == 2) || (black_neighbours == 1))
            new_grid[kv.first] = 1;
    }

    return new_grid;
}

We loop over every tile in our map. We don’t need to loop over every possible tile. Why? Black tiles can turn white, they are tiles in our map. But, white tiles can turn black. However, the white tiles that turn black must be neighbours of black tiles; thus we can loop over every tile which may change by only considering black tiles and their immediate neighbours.

That' what we do here. For every black tile, we loop over all 6 adjacent neighbours. For these neighbours, we check that they aren’t black. If they are, we skip them and as we will consider them later in the loop, but we increment our black neighbour count.

If the neighbour is white, we then loop over all 6 of its neighbours and count how many are black. We do this by just checking if the neighbours are in our map. If they are, they are black, else they must be white. We can exit early if we have more than 2 neighbours.

Finally, once we have checked and updated all 6 neighbour tiles to the current black tile, we now know how many black neighbours the current tile has. Thus, we can decide whether to update. We store all of the updated tiles in a new map.

All we do now is repeat this process 100 times,

1
2
3
4
// Flip 100 times
for(int i=0; i<100; i++)
    grid = flip_tiles(grid);
ans2 = count_black(grid);

And count how many black tiles remain. Both ⭐⭐ - now we just need to wait for Christmas day.

The full code can be found on github

Reflections

I think our solution today is relatively straightforward and very readable. However, it was incredibly beneficial to have already met hexagonal grids; thus, I could focus on other aspects of the problem.

In part 1 we just read in all of the directions, store the tile in a hashmap and then count how many are black at the end. Thus, our space complexity will go like O(N) with a O(log N)-time complexity, where N is the number of directions. The O(log N)-time complexity comes from the insertion into a map. We can improve this by using a unordered_map but there is no default unordered_map for a std::pair<int, int> key.

In part 2 we loop over every black tile in the map and look up the neighbours. Thus, the problem scales as O(M)-space and O(M * log M)-time where M where is the number of black tiles which increases over time.

My solution is not optimal, instead just pre-allocating a fairly large 2D array would give a much better time complexity, at the cost of increased memory usage. Thus, in practice, you need to decide if you are memory-bound or CPU time bound for this problem.

Anyway, thanks for reading, and I’ll hopefully see you tomorrow. However, I suspect that you may be busy; Merry Christmas.

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts