Advent of Code 2020: Day 11

Part 1

Your plane lands with plenty of time to spare. The final leg of your journey is a ferry that goes directly to the tropical island where you can finally start your vacation. As you reach the waiting area to board the ferry, you realize you’re so early, nobody else has even arrived yet!

By modeling the process people use to choose (or abandon) their seat in the waiting area, you’re pretty sure you can predict the best place to sit. You make a quick map of the seat layout (your puzzle input).

The seat layout fits neatly on a grid. Each position is either floor (.), an empty seat (L), or an occupied seat (#). For example, the initial seat layout might look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL

Now, you just need to model the people who will be arriving shortly. Fortunately, people are entirely predictable and always follow a simple set of rules. All decisions are based on the number of occupied seats adjacent to a given seat (one of the eight positions immediately up, down, left, right, or diagonal from the seat). The following rules are applied to every seat simultaneously:

If a seat is empty (L) and there are no occupied seats adjacent to it, the seat becomes occupied.

If a seat is occupied (#) and four or more seats adjacent to it are also occupied, the seat becomes empty. Otherwise, the seat’s state does not change.

Floor (.) never changes; seats don’t move, and nobody sits on the floor. Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?

You can read the full text here. We are back to our 2D grids and maps. Today we have to simulate how seats get occupied in an airport. In general, people want to sit on seats that have nobody around them, and if the seats around them fill up too much, then they will get up and move. Not too complicated. First of all, we need to load the map into memory. For this we’re using a vector of vector’s which store char’s. The choice of container here is not massively important.

Our input code is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

std::vector<std::vector<char>> mymap;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
	std::vector<char> l;
	for(auto c : line)
		l.push_back(c);
	mymap.push_back(l);
}
myfile.close();

Great! We have the input in an easy to use format. Now we need to write a function which takes the seats in their current state and evolves them all into a new state. We’re using the following function signature,

1
2
3
4

int process_step1(
        std::vector<std::vector<char>> &mymap,
        std::vector<std::vector<char>> &mymap_new
    )

We take in references to our vector containers, which at time of call are identical. We can then loop over the first map, and process what should happen to each seat, applying this change to the new map.

Our method is as follows: we loop over every position in the map. If the position is not a seat, then we move on. If the position is a seat, we must loop over its neighbours and calculate how many of the neighbouring seats are occupied.

We’ve included some boundschecking:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// What range of neighbours to check?
int li = std::max(int(i)-1, 0);
int lj = std::max(int(j)-1, 0);
int hi = std::min(i+2, mymap.size());
int hj = std::min(j+2, mymap[0].size());
// Count occupied neighbours
int occ = 0;
for(int ni=li; ni<hi; ni++){
	for(int nj=lj; nj<hj; nj++){
		if (mymap[ni][nj] == '#')
			occ++;
	}
}

Somewhat, simple, not the most elegant.

Following the rules given in the description, we update the new map depending on our current state and our surrounding neighbours:

1
2
3
4

if ((mymap[i][j] == '#') && (occ >= 5))
	mymap_new[i][j] = 'L';
if ((mymap[i][j] == 'L') && (occ == 0))
	mymap_new[i][j] = '#';

Note: I’m using 5, not 4, for my first if statement because I’ve counted the seat that I am checking. With this function written, we can run the simulation,

1
2
3
4
5
6
7
8

std::vector<std::vector<char>> mymap_old = mymap;
std::vector<std::vector<char>> mymap_new = mymap;
while (occ != last_occ){
	last_occ = occ;
	mymap_old = mymap_new;
	occ = process_step1(mymap_old, mymap_new);
}
ans1 = occ;

We just loop until the number of occupied seats becomes constant. It is possible that the number of occupied seats could be the same before convergence, e.g. two different configurations giving the same total count, however, this is quite unlikely and we get away with it here. That’s the first ⭐ in the bag!

Part 2

As soon as people start to arrive, you realize your mistake. People don’t just care about adjacent seats - they care about the first seat they can see in each of those eight directions!

Also, people seem to be more tolerant than you expected: it now takes five or more visible occupied seats for an occupied seat to become empty (rather than four or more from the previous rules). The other rules still apply: empty seats that see no occupied seats become occupied, seats matching no rule don’t change, and the floor never changes.

Given the new visibility method and the rule change for occupied seats becoming empty, once equilibrium is reached, how many seats end up occupied?

You can read the full text here. This follows on from part 1 quite easily. We can copy the function that we wrote in part 1 and just modify the method of calculating neighbouring occupied seats.

Instead of just looping over our nearest 8 neighbours, we are going to cast our rays in the the 8 possible directions. I’ve tried to implement this as succinctly as I could,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

std::vector<std::pair<int, int>> directions = {
	{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
};
int occ = 0;
for (auto dir : directions){
	std::pair<int, int> start = {i, j};
	start.first += dir.first;
	start.second += dir.second;
	// Now fire the ray until we hit a seat
	while( (start.first>=0) && (start.first<int(mymap.size())) &&
		   (start.second>=0) && (start.second<int(mymap[0].size())) ){
		if (mymap[start.first][start.second] == 'L') break;
		else if (mymap[start.first][start.second] == '#'){
			occ++;
			break;
		}
		start.first += dir.first;
		start.second += dir.second;
	}
}

At the top of the code snippet I define the 8 possible directions that we can look in. In the for loop we set our current position to the current seat and step forward once along our curent line of sight. We use a while loop to keep marching the ray forward until we either break or reach the end of our map.

We break if we hit a chair. If the chair is occupied we add it to our neighbour count.

Now we just have to wire this new function up the same as before and run until convergence. However, we must remember to reset our map to the values we initially loaded from the input. That’s all folks, both ⭐⭐ unlocked.

Reflections

I think the solutions we have implemented today are optimal, or at least very close to optimal. The first part of the problem has an easy to calculate complexity. Assume that we have N rows and M columns in our map. For each step in our iteration, we loop over the whole input and process each location. For each location, we either continue, or we check it’s neighbours, which is a fixed number. Thus, the problem scales as O(N * M)-time and space for each step in the iteration. The memory scaling just comes from storing the entire map in memory, all of the time.

For part 2, the complexity is slightly different. For each chair, we cast our rays in eight directions which continue until they hit another chair or the end of the map. Consider the worst case in which we have a chair in the top corner and no other chairs along the diagonals. In this case we could step max(N, M) times. Therefore in the worst-case scenario our time complexity is given as O(N * M * max(N, M)).

I’m assuming the map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

I’m not entirely convinced there is much further optimisation which can be achieved for this puzzle. However, please get in touch if you have any suggestions! 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

Comments