Advent of Code 2020: Day 20

, 14 min read
advent of code 2020

Part 1

The high-speed train leaves the forest and quickly carries you south. You can even see a desert in the distance! Since you have some spare time, you might as well see if there was anything interesting in the image the Mythical Information Bureau satellite captured.

After decoding the satellite messages, you discover that the data actually contains many small images created by the satellite’s camera array. The camera array consists of many cameras; rather than produce a single square image, they produce many smaller square image tiles that need to be reassembled back into a single image.

Each camera in the camera array returns a single monochrome image tile with a random unique ID number. The tiles (your puzzle input) arrived in a random order.

Worse yet, the camera array appears to be malfunctioning: each image tile has been rotated and flipped to a random orientation. Your first task is to reassemble the original image by orienting the tiles so they fit together.

To show how the tiles should be reassembled, each tile’s image data includes a border that should line up exactly with its adjacent tiles. All tiles have this border, and the border lines up exactly when the tiles are both oriented correctly. Tiles at the edge of the image also have this border, but the outermost edges won’t line up with any other tiles.

To check that you’ve assembled the image correctly, multiply the IDs of the four corner tiles together. Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?

You can read the full text here. This is like a really difficult jigsaw. Unfortunately, the write up to this puzzle is delayed, due to Christmas festivities. Still, I will be back up to date from now onwards.

Impossible jigsaw
Can we flip *every* piece?

We have been given 144 tiles, imagine these as jigsaw pieces. We need to put these together into a single image by matching up all of the pieces with the same edges. For example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
#.##...##.

Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#.

In the example above “Tile 2311” has the same bottom row as the “Tile 1951” has top row. Thus, these pieces could be stuck together. However, this was just lucky. In this jigsaw sometimes we need to flip the jigsaw tiles horizontally, vertically or rotate them. Thus, for each jigsaw piece, there are 8 possible orientations.

As always we must start by parsing the input,

 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
// Load the input and generate the permutations
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
    if (line[0] == 'T'){
        int id = std::stoi(line.substr(5, 4));

        std::array<std::array<int, 10>, 10> contents;
        for(auto &c : contents)
           c.fill(0);

        for(int j=0; j<10; j++){
            std::getline(myfile, line);
            for(size_t i=0; i<line.size(); i++)
                if (line[i] == '#')
                    contents[j][i] = 1;
        }

        // If first tile, we will use this as our starting point
        if (processed_tiles.size() == 0)
            processed_tiles.push_back(Tile(id, contents));
        else
            tiles.push_back(make_permuations(Tile(id, contents)));
    }
}
myfile.close();

This is not too difficult. In the above code, we just loop through looking the line with the “Tile: XXX”. We parse the XXX, and then we know there is a tile 10x10 directly below it. For now, we store the tile as 1’s and 0’s in a 2D array. If the tile grid was a “#” we store 1, else 0.

How do we store the tiles for further use? I’ve decided to take advantage of classes in C++.

1
2
3
4
5
6
7
8
9
class Tile {
    public:
        int id;
        std::array<std::array<int, 10>, 10> contents;
        std::array<int, 4> neighbours;
        Tile(int i, std::array<std::array<int, 10>, 10> arr) : id(i), contents(arr) {        
            neighbours.fill(-1);
        };
    }

The Tile is set up to store it’s ID, content and the indices of all of the neighbours. If the tile is on edge such that a neighbour is missing, then it is -1 (the default value).

Excellent! The eagle-eyed among you may have noticed the make_permuations. This is a simple function which takes a single tile and generates all 8 possible representations. This is achieved with,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
std::vector<Tile> make_permuations(Tile tile){
    // Generate the 8 permutations for each tile
    std::vector<Tile> tiles;
    for (auto t : {tile, tile.transpose()}){
        tiles.push_back(t);
        tiles.push_back(t.flip_horizontal());
        tiles.push_back(t.flip_vertical());
        tiles.push_back(t.flip_vertical().flip_horizontal());
    }
    return tiles;
}

where the flip methods are defined as,

1
2
3
4
5
6
Tile flip_horizontal(){
    std::array<std::array<int, 10>, 10> arr = contents;
    for(auto &v : arr)
        std::reverse(v.begin(), v.end());
    return Tile(id, arr);
}

Wow! Well, this got complex fast so let’s just take a second to recap where we are. We’ve managed to parse the input, so we can read in each tile and store the contents of each tile in a 2D array. But, at this stage, we don’t know whether we need to flip/rotate the tiles. Thus, we generate all 8 possible versions of each tile and store them in our vector of tiles.

Thus, for the whole input, we have 144 tiles, each with 8 variations and we have all of these in memory. Now, we need to figure out which tiles are connected to which tile and how they are all oriented.

We start by just taking a random tile, we choose the first tile we read in, and just pick a given orientation; namely, we just take the initial configuration. We take this as our starting piece. We store this in a new list of processed tiles.

Now, for this tile, we loop over all 132 other tiles, all 8 orientations looking for pieces which we connect to. For example, take the next tile. We loop over all 8 configurations and check if the left side of the tile 2 matches the right side of the current tile, and so on for each side. If we find a match, then we know which tile we neighbour, and we know the correct orientation. Thus we add the match to our processed list and remove all 8 versions from the unprocessed storage.

To aid this we’ve added some methods to the Tile class which can easily return each of the 4 edges,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
std::array<int, 10> side(int nside){
    // Get the array side 0:U, 1:D, 2:L, 3:R
    if (nside == 0)
        return contents[0];
    else if (nside == 1)
        return contents[9];
    else if (nside == 2){
        std::array<int, 10> left;
        for(int i=0; i<10; i++)
            left[i] = contents[i][0];
        return left;
    }
    else{
        std::array<int, 10> right;
        for(int i=0; i<10; i++)
            right[i] = contents[i][9];
        return right;
    }
}

We start by calling our find_neighbours function on a random tile.

 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
void find_neighbours(
        std::vector<std::vector<Tile>> &tiles,
        std::list<Tile> &processed_tiles,
        Tile &tile,
        int ind
    ){
    std::vector<std::pair<int, int>> side_pairs = {{0, 1}, {1, 0}, {2, 3}, {3, 2}};
    // Find unprocessed neighbours from rotated/flipped possibilites
    std::vector<std::vector<Tile>>::iterator it = tiles.begin();
    while(it != tiles.end()){
        int neigh = processed_tiles.size();
        int found = 0;
        for(auto t : *it){
            for(auto sp : side_pairs){
                if (are_neighbours(tile, t, sp.first, sp.second, ind, neigh) > 0){
                    processed_tiles.push_back(t);
                    found = 1;
                    break;
                }
            }
            if (found > 0) break;
        }
        // This tile is processed, we picked which permutation out of 8 we needed,
        // thus we can remove them
        if (found > 0)
            it = tiles.erase(it);
        else
            it = std::next(it);
    }
}

The code above identifies all the neighbours of tile, by looping over all orientations of all unprocessed tiles and comparing their sides. We use the erase method to remove all the permutations once we have identified the correct version of a tile.

After applying this on every tile,

1
2
3
4
5
6
7
// Loop through and find every tiles neighbours
std::list<Tile>::iterator it = processed_tiles.begin();
int ind = 0;
while(it != processed_tiles.end()){
    find_neighbours(tiles, processed_tiles, *it, ind++);
    it = std::next(it);
}

we now have a list of tiles which are all orientated correctly, but furthermore they each store the index of all of their neighbours. This was implicitly stored by the are_neighbours function upon successful matching,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int are_neighbours(Tile &t1, Tile &t2, int side1, int side2, int ind, int neigh){
    // If we are neighbours, and we don't have neighbours then set us to be neighbours
    if ((t1.side(side1) == t2.side(side2)) && (t1.neighbours[side1] == -1)){
        t1.neighbours[side1] = neigh;
        t2.neighbours[side2] = ind;
        return 1;
    }
    // Else, return 0 and do nothing
    return 0;
}

Great! We have a list of tiles, each of which knows the identity of its neighbours. Thus, we just need to loop over each tile and identify those in corners, e.g. ones that are missing both a horizontal and a vertical neighbour, which are stored as -1’s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Part 1: find the corner IDs
ans1 = 1;
Tile top_left = processed_tiles.front();
for(auto &t : processed_tiles){
    // Find the corners
    if ((std::min(t.neighbours[0], t.neighbours[1]) < 0) &&
        (std::min(t.neighbours[2], t.neighbours[3]) < 0))
            ans1 *= t.id;
    // Also find top left corner
    if ((t.neighbours[0] == -1) && (t.neighbours[2] == -1))
        top_left = t;
}

That was a lot of work… maybe I’ve over-complicated this, but anyway, we have the first ⭐!

The full code can be found on github

Part 2

Now, you’re ready to check the image for sea monsters.

The borders of each tile are not part of the actual image; start by removing them.

Now, you’re ready to search for sea monsters! Because your image is monochrome, a sea monster will look like this:

1
2
3
                  #
#    ##    ##    ###
 #  #  #  #  #  #   

When looking for this pattern in the image, the spaces can be anything; only the # need to match. Also, you might need to rotate or flip your image before it’s oriented correctly to find sea monsters.

How many # are not part of a sea monster?

You can read the full text here.

I guess we should have expected this. We are going to need to put the whole image together. At the end of part 1, when we identified the corners, I also identified the top left corner. Starting from the top left corner, we can loop along the columns, and down the rows, stitching all of the images together. Unfortunately, my choices of data structure make this a little bit fiddly.

The first step is to put the tiles into a 2D structure. Thus I can access the top left tile with grid[0][0] where the tile to the left and below are grid[0][1] and grid[1][0], respectively.

Then, with this stored. I can loop through all of the tiles in the image and stitch them together into strings, where each string represents a row in the image. This yields,

1
std::vector<std::string> image = generate_image_from_grid(rows);

Great! We have a vector of strings in order so we can draw our image. I haven’t included the code for this because it’s a little dull and not really important, but you can find it on github.

Now the exciting part, how do we find the monsters in our image?

1
2
3
                  #
#    ##    ##    ###
 #  #  #  #  #  #   

Well, assuming that our image is oriented the correct way, we can take any starting point of (i, j) and ensure that the positions, (i, j+18), (i+1, j+0), (i+1, j+5) etc. are all ‘#’s. I’ve written this in the following way,

 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
std::vector<std::string> idenfity_monsters(std::vector<std::string> total_image) {
    for (size_t i = 0; i < total_image.size() - 2; i++) {
        for (size_t j = 0; j < total_image.size() - 19; j++) {
            bool monster = true;
            for (auto k : {18})
                if (total_image[i][j + k] != '#')
                    monster = false;
            for (auto k : {0, 5, 6, 11, 12, 17, 18, 19})
                if (total_image[i + 1][j + k] != '#')
                    monster = false;
            for (auto k : {1, 4, 7, 10, 13, 16})
                if (total_image[i + 2][j + k] != '#')
                    monster = false;

            if (monster == true) {
                for (auto k : {18})
                    total_image[i][j + k] = 'O';
                for (auto k : {0, 5, 6, 11, 12, 17, 18, 19})
                    total_image[i + 1][j + k] = 'O';
                for (auto k : {1, 4, 7, 10, 13, 16})
                    total_image[i + 2][j + k] = 'O';
            }
        }
    }
    return total_image;
}

When we do find a monster, we go through and replace it with “O"s. Thus, finally, all we need to do is count the number of “#“s in the final image. Wow, well that was a lot of code today, but we finally have both stars ⭐⭐!

The full code can be found on github

Reflections

I don’t really like my code for this puzzle. I found it a little clumsy the method which I go from no neighbours to all neighbours. I also found it a little fiddly to turn this into a vector; thus, I can easily output the image. I think I’ll spend some time looking through other peoples solution to this puzzle to gain a few techniques of how I could have improved this.

In the first part of this puzzle we have to identify which orientation of each tile we need to solve our puzzle. For this I start with a random tile and then loop through N-1 tiles, and then N-2 etc. Thus, this algorithm scales as O(N^2)-time, where N is the number of tiles. In space we’re storing 8 version of each tile at peak memory usage, thus, O(N)-space.

This gets us most of the way through part 1. Then, for part 2, I start off doing a bunch of memory manipulation. The code for this a little clumsy, but the complexity is quite simple, O(N)-time and space.

Finally, we loop over the whole image and look for the monster pattern. This pretty much scales with the number of tiles (which is proportional to the total image size). Thus, this scales as O(N)-time.

Overall the algorithm is O(N^2)-time and O(N)-space. I suspect this can be improved by using a hashmap of edges in part 1, thus the image creation can be achieved in a single pass. This would reduce the time complexity to O(N)-time. I’m assuming the map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

This was quite a challenging puzzle, particularly part 2. Fortunately, my naive approach to part 1 meant that we were well placed to generate the whole image and search for monsters. I hope you enjoyed reading, and I look forward to seeing you all again over the next week.

As always, feel free to leave feedback on my code and algorithms. I’m particularly interested to hear how I could have made today’s code more concise.

. . . .

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