Today’s puzzle title is “Seating System” but it’s actually a variation of a well known zero-player game called Conway’s Game of Life. Many of us may recall this game as a popular choice for work assignments in computer science courses.
Dr. John Conway, the English mathematician who created this game was last year a victim of COVID-19. If you want to know a little more about him you can read this article that was featured this week on Hacker News.
Our input is the layout of a waiting room. We have chairs and empty spaces. The chairs can be empty or occupied and no one can sit on the floor.
We start from an empty waiting room, iterate on each position to check if the seat state changes and in the end we count the number of occupied seats. if this number is equal to the previous waiting room occupied seats we arrived to the solution, otherwise we keep iterating.
If you want to follow along please download AdventOfCode2020.pbit and check Day 1 post for instructions.
Part 1
The rules are as follows:
- 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.
The first decision we have to make is to choose how are we going to
represent each room. To avoid performance issues with inner looping as
it tends to really slow down Power Query seems wise to have just a
straight table and avoid lists inside lists. Another point is the
character comparison and the sums we will need to do to check the
surrounding positions of a chair and the total of each board state.
The difference may not seem much but my board is \(98*95=9310\)
positions long. We will need at least 9310 loops to calculate one
generation. That’s a lot of loops in a language were they should be
only used as a last resort.
In order to minimize this we can replace the characters by numbers,
a 0 will mean an empty seat, 1 an occupied seat and null an empty
space.
Figure 1: Waiting room represented as a list instead of a matrix
For a seat \(x\) to change state we need to sum all the surrounding positions:
|UL| U |UR|
|L |(X)|R | -> List.Sum(UL,U,UR,L,R,DL,D,DR)
|DL| D |DR|
The seat position is fixed as the surrounding cells next to it. To avoid having to check if we are trying to access non existing positions on each loop we will calculate them once and reuse that list of positions on each new waiting room calculation. For instance, seats on the first row don’t have any of seats behind them, so they don’t need to be checked.
Figure 2: Positions to check for Row 1, Column 1 seat
Now that we have for each seat the list of positions we use a function to create a new generation from the previous one:
fnDoGeneration = (lstSeats as list, lstPos as list, nrows as number, seatsThreshold as number) as list => List.Transform( {0 .. nrows - 1}, each if lstSeats{_} <> null then let occupiedSeats = List.Sum(List.Transform(lstPos{_}, (x) => lstSeats{x})), currPos = lstSeats{_} in if currPos = 0 and occupiedSeats = 0 then 1 else if currPos = 1 and occupiedSeats > seatsThreshold then 0 else currPos else null )
This function goes to each position, sums the values around that cell, applies the rules and returns the new state.
And finally we have the main loop:
loopP1 = List.Generate( () => [Seats = fnDoGeneration(lstSeats, lstPosP1, nrows, 3), NrOccupiedSeats = 0, LastCount = - 1], each [NrOccupiedSeats] <> [LastCount], each [ Seats = fnDoGeneration(List.Buffer([Seats]), lstPosP1, nrows, 3), NrOccupiedSeats = List.Sum(Seats), LastCount = [NrOccupiedSeats] ], each [NrOccupiedSeats] ), lastCountP1 = List.Last(loopP1)
We calculate a generation, sum the number of occupied seats and
compare that number with the previous one. When they are equal we
break the loop and that’s it. Again we have used the List.Buffer as
a performance booster.
Part 2
The grand difference between this part and the first is that now when one of the surrounding chairs is a floor tile we need to continue in that direction until a chair is found. The other difference is the tolerance threshold that increased one unit.
We need to change the function that calculates the positions to be checked.
This was the code to check the chair behind the current one:
if [Index]-ll >= 0
and [Seats] <> null
and listSeats{[Index]-ll} <> null
then [Index]-ll else null
[Index] represents the current position and ll the row length. We
just checked if the position existed and returned the index of the
seat or null otherwise.
Now we loop over all the possible positions in that direction until we find a seat or we get out of bounds:
List.Generate(
() => [p=[Index]-ll],
each [p] >= 0,
each [p = if listSeats{[p]} <> null then -1 else [p]-ll],
each [p]))
All the remaining logic is the same. We use the function
fnDoGeneration and continue looping until stabilization.
Conclusion
This puzzle was a great way to pay homage to a mathematician that helped pave the way forward in the computer sciences world.
Have fun!!