DEV Community

Cover image for Seating System
Robert Mion
Robert Mion

Posted on

Seating System

#adventofcode #algorithms #computerscience #programming

Advent of Code 2020 Day 11

Try the simulator

Simulator of Part 1

Task: Solve for X where... 

X = the number of seats occupied once seat occupation no longer changes
Enter fullscreen mode Exit fullscreen mode

Example input 

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
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A waiting area where
  • . is the floor
  • L is an empty seat
  • # is an occupied seat

Part 1

  1. This puzzle type again?
  2. How does this puzzle compare?
  3. Writing a working algorithm
  4. Build a simulator

This puzzle type again?

How does this puzzle compare?

  • This puzzle's grid is 2D
  • This puzzle's grid remains a constant size
  • This puzzle's tiles can be one of 3 states
  • This puzzle's tiles eventually stop changing state

Writing a working algorithm

Set the stage

Process the input into an array of arrays:
  Split the input at each new line character into an array of strings
  Split each string into an array of characters

Create an array of 8 pairs that represent the coordinates of each cell's adjacent cells
Enter fullscreen mode Exit fullscreen mode

Pad the array with a 1-element shell:

Turn an array like this:
L.L
.L.
L.L

Into an array like this:
.....
.L.L.
..L..
.L.L.
.....
Enter fullscreen mode Exit fullscreen mode

The main loop:

Do at least one time, then again only if an array of cells to switch is not empty:
  Empty the array of cells
  For each cell in the grid of seats, except for the bordering cells:
    Check each adjacent cell and accumulate tallies for each of the three possible characters found: . # L
    If the current cell contains an 'L' and the number of '#'s found is 0
      Add the cell's coordinates to the list of switchers with an instruction to change it's value to '#'
    Else, if the current cell contains an '#' and the number of '#'s found is 4 or more
      Add the cell's coordinates to the list of switchers with an instruction to change it's value to 'L'

For each coordinate and instruction set in the list of switchers
  Update the cell in the grid of seats at the current location to the value specified
Enter fullscreen mode Exit fullscreen mode

Lastly, calculate the count of occupied seats:

For each nested array in the grid of seats
  Accumulate a sum - starting at 0 - of the count of '#' characters in each array

Return the sum
Enter fullscreen mode Exit fullscreen mode

Build a simulator

  • This felt like an easy task given how many times I built similar-functioning simulators for the challenges referenced above

Try the simulator for Part 1
Simulator of Part 1

Part 2

  1. What a fun twist!
  2. Writing newly-needed sub-routines
  3. Updating the working algorithm
  4. Updating the simulator

What a fun twist!

Instead of checking the eight adjacent cells:

.....
.!!!.
.!S!.
.!!!.
.....
Enter fullscreen mode Exit fullscreen mode

We must check in straight lines in all eight directions, until we find a seat or we exceeded the boundary of the room:

!.!.!
.!!!.
!!S!!
.!!!.
!.!.!
Enter fullscreen mode Exit fullscreen mode

Writing newly-needed sub-routines

  1. Check if the next-checked cell is within the boundary of the room
  2. Recursively check the next cell along a straight line until we find a seat or exceed the boundary of the room

Function: isAtAValidLocation() 

Expects two parameters
  1. Row index
  2. Column index

Return false, unless:
  Both indices are greater than or equal to 0
  And Row is less than the length of the number of arrays in the outer-most array
  And Column is less than the length of any nested array (they are all the same length)
Enter fullscreen mode Exit fullscreen mode

Function: firstVisibleSeat() 

Expects two parameters
  1. A pair of coordinates representing the direction to travel from an origin point
  2. A pair of coordinates representing the originating row and column indices

Return '.' to indicate 'No seat found', unless:
  The next cell along the path 'isAtAValidLocation'
  If the next cell is at a valid location
    And its value is '.'
      Continue along the path
    Else - its value is not '.'
      Return its value - being either 'L' or '#'
Enter fullscreen mode Exit fullscreen mode

Updating the working algorithm

  • Same setup to process the input into an array
  • Removed the process of padding the array

The new main loop:

Do at least one time, then again only if an array of cells to switch is not empty:
  Empty the array of cells
  For each cell in the grid of seats:
    Continue along a straight line - starting from each adjacent cell and continuing until either a seat is found or reaching the boundary of the room - and accumulate tallies for each of the three possible characters found: . # L
    If the current cell contains an 'L' and the number of '#'s found is 0
      Add the cell's coordinates to the list of switchers with an instruction to change it's value to '#'
    Else, if the current cell contains an '#' and the number of '#'s found is 5 or more
      Add the cell's coordinates to the list of switchers with an instruction to change it's value to 'L'

For each coordinate and instruction set in the list of switchers
  Update the cell in the grid of seats at the current location to the value specified
Enter fullscreen mode Exit fullscreen mode

Updating the simulator

Aside from copy-pasting the code from my algorithm into the page's script, this required adding logic to toggle which part's function to call based on which button was pressed.

I got sloppy with my copy-pasting and created a small headache to troubleshoot.

Overall, no big deal.

Try the simulator for Part 2
Simulator of Part 2

Top comments (0)

Read next

mauricefreund profile image

Sometimes it's the little things

MauriceFreund -

moh_moh701 profile image

C# Advanced:Operator Overloading

mohamed Tayel -

thisweekinjavascript profile image

TC39 JavaScript Updates, TypeScript 5.7 Beta, Node.js v20.18.0 and more

James -

sahrohit profile image

Parallelizing Sorting Algorithms using OpenMP

Rohit Sah -