Part 1

I’m back after a month-long break of blog posting on Advent of Code! That’s actually not that bad, because I now have a fresh look on the solutions I have implemented. And when I say fresh look, I actually mean a critical look on the implementations. So what’s going to be shown in this blog post is actually a refactored version of what I did on that particular day.

On Day 11, we have to treat some sort of seating system where a seat is vacant or not based on some specific rules. Let’s take a look at the example we are given:

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

In this example, we are told that (.) represents floor space that never changes state, (L) represents an empty seat, and (#) represents an occupied seat. The rules used to determine if a seat is vacant or occupied are the following:

• 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.

What’s funny about this problem is that, quite surprisingly, these rules eventually converge to a stable state where seats don’t change state anymore. We are thus told to determine how many seats are occupied once the system stabilize.

If we have to break down this problem, here’s what we might want to do:

• How should we be representing the seating space? A simple list of strings should do the trick. Let’s call this variable previous_seats.
• We know that we have to loop the process of changing the state of some seats. Since we do not know how many iterations are necessary to reach the stable state, we know for sure that we’re going to use a while loop.
• Then, what is the condition to stop looping? Reaching a stable state means that the system is identical from an iteration to the next. This means that we probably will have to declare another variable to represent the seat space after we have applied the rules (let’s call it next_seats).
• This poses the following question: how should I create the contents of next_seats? To answer this question, we can recall what we said on Day 8 about copies. Because we are manipulating a list of strings, which are immutable in Python, we are safe with shallow copies.
• Now, what is the body of our loop? In our loop, we wish to look at the seats in previous_seats and create the contents of next_seats. To do so, we need to :
  • Loop through each row of seats, and then loop through each seat in this row;
  • For each seat in a row, we need to compute the number of occupied seats;
  • Based on this number of occupied seats, we need to update the state (or not) the state of the current seat.
• Then, when the while loop is over, we can count the number of occupied seats, and we should be getting our result.

With all that, we can build the following solution to Part 1:

def seat_is_empty(seat):
    return seat == "L"


def seat_is_occupied(seat):
    return seat == "#"
    

def count_neighbours(previous_seats, seat_row, seat_column):
    nb_rows, nb_columns = len(previous_seats), len(previous_seats[0])
    # We create a list of adjacent position to the current seat position
    adjacent_positions = [(seat_row - 1, seat_column - 1), (seat_row - 1, seat_column), (seat_row - 1, seat_column + 1),
                          (seat_row, seat_column - 1),                                  (seat_row, seat_column + 1),
                          (seat_row + 1, seat_column - 1), (seat_row + 1, seat_column), (seat_row + 1, seat_column + 1)]
    occupied_adjacent_seats_count = 0
    for row_pos, column_pos in adjacent_positions:
        if not (0 <= row_pos < nb_rows and 0 <= column_pos < nb_column):
            continue  # Invalid coordinates
        target_check = seats[row_pos][column_pos]
        if target_check == "#":
            occupied_adjacent_seats_count += 1
    return occupied_adjacent_seats_count
    
    
# Suppose we have parsed the input into a `seats` variable
previous_seats = seats
next_seats = None
while previous_seats != next_seats:
    # These lines are here to make sure that the rules are being applied
    # Updating `previous_seats` at the end of the loop will cause the loop to stop immediately after one iteration
    if next_seats:
        previous_seats = next_seats
    next_seats = []
    for i in range(nb_rows):
        # We initialize an empty row that we will append to `next_seats`
        row = ""
        for j in range(nb_columns):
            if seat_is_empty(previous_seats[i][j]) and count_neighbours(previous_seats, i, j) == 0:
                row += "#"
            elif seat_is_occupied(previous_seats[i][j]) and count_neighbours(previous_seats, i, j) >= 4:
                row += "L"
            else:
                row += previous_seats[i][j]
        next_seats.append(row)

# When the loop is over, we can count the number of occupied seats.
occupied_seats = [seat for values in next_seats for seat in values].count("#")
print(occupied_seats)

Part 2

Part 2 says that the rules are slightly modified:

• Instead of adjacent seats, we are now looking at all directions until we see a seat. This means that the algorithm needs to expand from neighbourhood to “first seat seen”.
• Instead of 4 or more adjacent seats, an occupied seat becomes vacant if there are 5 or more occupied seats in its sight.

Other than that, the seating area stabilizes again and we have to count the number of occupied seats when it has reached equilibrium.

Obviously, the second change does not really impact the algorithm we have built for Part 1. The real change here is that, instead of looking at the direct neighbours, we keep on looking in each direction until we find a seat.

We can then adapt what we have done for Part 1 to check for neighbours by adding a loop that continues until we reach a seat or the limits of the seating space. If we keep the rest of the program identical, here’s what we can do for the count_neighbours() function:

def count_neighbours(seats, seat_row, seat_column):
    nb_rows, nb_columns = len(previous_seats), len(previous_seats[0])
    count = 0
    # adjacent_positions will allow us to "spread" the neighbourhood in all directions
    adjacent_positions = [(-1, -1), (-1, 0), (-1, 1),
                          (0, -1),           (0, 1),
                          (1, -1),  (1, 0),  (1, 1)]
    for spread_row, spread_col in adjacent_positions:
        # We create `row_test` and `column_test` to initialize the initial seat position each time we are
        # spreading in a new direction.
        row_test, column_test = seat_row, seat_column

        # The only way to stop this loop is to:
        #   - Reach the borders of the seating space
        #   - Reach a seat (vacant or occupied)
        while True:
            row_test, column_test = row_test + spread_row, column_test + spread_col
            if not (0 <= row_test < nb_rows and 0 <= column_test < nb_columns):
                break
            if seats[row_test][column_test] == "L":
                break
            if seats[row_test][column_test] == "#":
                count += 1
                break
    return count

The rest of the program should remain the same except for the rule to change an occupied seat to a vacant seat, so basically changing a 4 into a 5.

Concepts and Difficulties

This problem is actually an example of a quite common class of problems: cellular automaton. What’s fascinating with these problems is that there are some configuration that converge to a stable state, just like what we have here. These also can produce really awesome animations if you were to show how the seats gets occupied or not. See for example all the results of this Reddit search on /r/adventofcode.

There are again quite a few interesting points to cover in these solutions. First, we are looking at adjacent positions instead of adjacent seats. This actually prevents us from having issues with indices getting out of bounds as we can simply check for their values. Then, we once again have to think about what kind of copies we want to create in our solutions. And finally, we have to juggle through all the rules to produce a solution that takes care of the simultaneous application of all the rules. This is actually a key point: we don’t want to modify the previous state but instead want to create a new one (hence the need for a second variable).