Advent of Code 2020: Day 17

, 10 min read
advent of code 2020

Part 1

As your flight slowly drifts through the sky, the Elves at the Mythical Information Bureau at the North Pole contact you. They’d like some help debugging a malfunctioning experimental energy source aboard one of their super-secret imaging satellites.

The experimental energy source is based on cutting-edge technology: a set of Conway Cubes contained in a pocket dimension! When you hear it’s having problems, you can’t help but agree to take a look.

The pocket dimension contains an infinite 3-dimensional grid. At every integer 3-dimensional coordinate (x,y,z), there exists a single cube which is either active or inactive. In the initial state of the pocket dimension, almost all cubes start inactive. The only exception to this is a small flat region of cubes (your puzzle input); the cubes in this region start in the specified active (#) or inactive (.) state.

The energy source then proceeds to boot up by executing six cycles.

During a cycle, all cubes simultaneously change their state according to the following rules:

1
2
3
4
5
6
7
    If a cube is active and precisely 2 or 3 of its
    neighbours are also active, the cube remains active.
    Otherwise, the cube becomes inactive.

    If a cube is inactive, but exactly 3 of its neighbours
    are active, the cube becomes active. Otherwise, the cube
    remains inactive.

Starting with your given initial configuration, simulate six cycles. How many cubes are left in the active state after the sixth cycle?

You can read the full text here. Today we are solving a puzzle which is clearly based on Conway’s game of life. So we start with an initial configuration of active and inactive cubes. We also have rules which state what should happen to each cube during a cycle.

The satellite view
The satellite view

The first thing we do is read in our input which looks similar to this:

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

The coordinates at the top left are (0, 0, 0) and the bottom right, (2, 2, 0). This a is a slice in the x-y plane. There are cubes at all other z-coordinates, but initially they are all inactive.

I’ve decided that we are going to use a map to store the position of only the active cubes. This means we don’t have to allocate a large array which stores a mostly empty world.

Thus, we need to read the initial configuration in and place it in our map,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
std::fstream myfile("input", std::ios_base::in);
std::string line;
int lineno = 0;
std::unordered_map<long int, char> world_initial;
while(std::getline(myfile, line)){
    for(size_t colno=0; colno<line.size(); colno++)
        if (line[colno] == '#'){
            world_initial[key_xyzw(lineno, colno, 0)] = 1;
        }
    lineno++;
}
myfile.close();

Hopefully, most of this makes sense. We just open the file, loop through the file and setting the x-coordinate as the line number, and the y-coordinate as the column of the string. The complication comes in key_xyzw(lineno, colno, 0, 0). As we previously discussed, I want to store the world in a map, but I want to keep the hash function simple. Thus instead of using an array<int 4> as the key, I’m encoding the 3 (but 4 later) coordinates into a single number. This is quite simple to do, but it has some limitations. The function to encode the coordinates looks like this:

1
2
3
4
5
6
7
8
long int key_xyzw(int x, int y, int z){
    long int key = x+HALF;
    key *= MAX_IND;
    key += y+HALF;
    key *= MAX_IND;
    key += z+HALF;
    return key;
}

Thus, the key is equal to

1
key = (x+HALF)*(MAX_IND)^2 + (y+HALF)*(MAX_IND) + (z+HALF)

where MAX_IND=1000 and HALF=500. However, these can be increased. This means we can recover the x, y, z and with the following procedure,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void get_xyzw(long int key, int &x, int &y, int &z){
    z = key % MAX_IND - HALF;
    key -= z;
    key /= MAX_IND;

    y = key % MAX_IND - HALF;
    key -= y;
    key /= MAX_IND;

    x = key - HALF;
}

Great! We’ve encoded 3 coordinates in a single number, but the coordinates may not exceed either [-HALF, +HALF] otherwise, everything breaks.

Now we can loop through our world, count the neighbours for every cube and decide what to do in the next cycle. Thus full cycle code is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
std::unordered_map<long int, char> world = world_initial;
std::unordered_map<long int, char>::iterator it;
for (int cycle = 1; cycle <= num_cycles; cycle++) {
    std::unordered_map<long int, char> new_world;
    int new_active = 0;
    for (int x = range[0] - cycle; x <= range[1] + cycle; x++)
        for (int y = range[2] - cycle; y <= range[3] + cycle; y++)
            for (int z = range[4] - cycle; z <= range[5] + cycle; z++) {
                long int key = key_xyzw(x, y, z);
                int active = count_active_neighbours(world, x, y, z);
                it = world.find(key);
                if ((it != world.end()) &&
                        ((active == 3) || (active == 2)) ||
                    ((it == world.end()) && (active == 3))) {
                    new_world[key] = 1;
                    new_active++;
                }
            }
    world = new_world;
    ans1 = new_active;
}

All we do in the code above is generate a new world, which we can fill with our new active cubes. Then we loop through every possible x, y and z coordinates. Assuming our world initially occupies 0 to 7 in the x-axis, then the range of new active cubes is -1 to 8, based on the current rules. Thus, the range could increase by 1 step, in each direction, every cycle.

Thus, we loop over every current cube and calculate how many of it’s neighbours are active by doing lookups into our map. If the rules suggest the cube should become active, we store it in the new world.

After we have tried every possible cube, we swap our new world to become the world and continue. After 6 cycles, we have completed, and we just need to return the number of active cubes. I’ve skipped over the count_active_neighbours function but it is quite simple and can be found on Github.

Anyway, that’s all we have to do to unlock our first ⭐.

The full code can be found on github

Part 2

For some reason, your simulated results don’t match what the experimental energy source engineers expected. Apparently, the pocket dimension actually has four spatial dimensions, not three.

The pocket dimension contains an infinite 4-dimensional grid. At every integer 4-dimensional coordinate (x,y,z,w), there exists a single cube (really, a hypercube) which is still either active or inactive.

You can read the full text here. Nice! All we need to do now is extend the code to include a fourth dimension. In our code, this is really simple we just need to modify our key functions. For example, the key encoding would now look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
long int key_xyzw(int x, int y, int z, int w) {
    long int key = x + HALF;
    key *= MAX_IND;
    key += y + HALF;
    key *= MAX_IND;
    key += z + HALF;
    key *= MAX_IND;
    key += w + HALF;
    return key;
}

Awesome! We’ve easily added the fourth dimension, w. Then we must also add an extra loop into our main cycle code to ensure we loop through this fourth dimension,

1
2
3
4
for (int x = range[0] - cycle; x <= range[1] + cycle; x++)
    for (int y = range[2] - cycle; y <= range[3] + cycle; y++)
        for (int z = range[4] - cycle; z <= range[5] + cycle; z++)
            for (int w = range[6] - cycle; w <= range[7] + cycle; w++)

And that’s it! We have now solved the problem in 4 dimensions, and we’ve got a full house ⭐⭐.

The full code can be found on github

Reflections

My code today is a little more functional than usual. I would also say that it is relatively readable, but it absolutely could be improved. There is clearly a lot of copy and pasting between part 1 and part 2. This could be reduced, but I have little appetite for that currently.

I think the complexity of our solution today should be fairly good. We are using an unordered_map to store only the active cubes, which means we have a low memory footprint. Furthermore, the lookup of neighbouring cells in the unordered_map should also be O(1)-time complexity, as well as inserting values into the new world.

I think today, both parts of the problem should scale as O(N)-space, where N is the number of active cubes. However, the time complexity will be a little worse as I essentially check every cube in a cubic region which grows with the number of cycles, thus O(M^3) where M is the number of cycles for part 1 and O(M^4) in part 2 as we have 4 dimensions.

However, this can be improved. As the rules mean that only cubes which directly neighbour an active cube can become active themselves. Thus, we only need to check neighbour cubes, instead of every cube in a region of M^3. If I modified the code to do this, then the problem would scale as O(N * M)-time and O(N)-space, where N is the number of active cubes and M is the number of cycles.

The following code implements this technique:

 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
world = world_initial;
for (int cycle = 1; cycle <= num_cycles; cycle++) {
    std::unordered_map<long int, char> new_world;
    int new_active = 0;
    for(auto cube : world){
        get_xyzw(cube.first, x, y, z, w);
        for (int xi = x - 1; xi <= x + 1; xi++)
            for (int yi = y - 1; yi <= y + 1; yi++)
                for (int zi = z - 1; zi <= z + 1; zi++)
                    for (int wi = w - 1; wi <= w + 1; wi++){
                        long int key = key_xyzw(xi, yi, zi, wi);
                        it = new_world.find(key);
                        if (it != new_world.end()) continue;

                        int active = count_active_neighbours(world, xi, yi, zi, wi);

                        it = world.find(key);
                        if ((it != world.end()) && ((active == 3) || (active == 2)) ||
                            ((it == world.end()) && (active == 3))) {
                            new_world[key] = 1;
                            new_active++;
                        }
                    }
    }
    world = new_world;
    ans2 = new_active;
}

However, while this should scale better than my previous code, it actually takes longer for a small problem size. I assume this could be sped up by accelerating my coordinate encoding. Anyway, thanks for reading - I hope it was fun. See you tomorrow!

. . . .

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