DEV Community

Cover image for Lobby Layout
Robert Mion
Robert Mion

Posted on

Lobby Layout

#adventofcode #programming #algorithms #computerscience

Advent of Code 2020 Day 24

Try the simulator!

Puzzle algorithm simulator

Task: Solve for X where... 

X = number of tiles with black side face up
Enter fullscreen mode Exit fullscreen mode
  1. After flipping each tile in the input
  2. After flipping 100 times according to a formula

Example input 

seswneswswsenwwnwse
wsweesenenewnwwnwsenewsenwwsesesenwne
wseweeenwnesenwwwswnew
...
Enter fullscreen mode Exit fullscreen mode

Each line:

  • represents a destination tile
  • contains up to 6 directions: e,se,sw,w,nw,ne

Part 1 - in stages

  1. Extracting each direction from each line
  2. Creating a coordinate system
  3. Performing the flips
  4. Counting the tiles with black side facing up
  5. Visualizing the tile floor

Extracting each direction from each line

RegEx to the rescue:

This Regular Expression:
/e|se|sw|w|nw|ne/g

For this line:
wseweeenwnesenwwwswnew

Generates this list:
w,se,w,e,e,e,nw,ne,se,nw,w,w,sw,ne,w
Enter fullscreen mode Exit fullscreen mode

Creating a coordinate system

This took me considerable thought, trial and error - all on paper.

  3 2 
 4 0 1
  5 6

Nope.
------

 ne  e  se
 +1 +1 +1
[ 0, 0, 0 ]
 -1 -1 -1
 sw  w  nw

Nope.
------

   -1    -1
   up    left
[   0,    0   ]
   down  right
   +1    +1

Closer!
------

   nw  ne  
  w  00  e
   sw  se

e  [ 0, 2]   
se [ 1, 1]   
sw [ 1,-1]   
w  [ 0,-2]   
nw [-1,-1]   
ne [-1, 1]

BINGO!
Enter fullscreen mode Exit fullscreen mode

Performing the flips 

Create a dictionary mapping coordinates to boolean values that represent whether white or black is face-up
Create a legend mapping the six directional strings to a relative coordinate system matching what is written above
For each tile path - starting from the coordinate [0,0]
  For each extracted direction within the tile path
    Update each of the accumulating coordinate's values to reflect the sum of that value and the value at the same index in the looked-up direction's coordinates (e.g. [0,0] on sw becomes [1,-1]; then on nw becomes [0,-2])
  Look for a key in the dictionary matching the final coordinate
    If it exists, flip the boolean of the coordinate (e.g. 0 to 1 or vice versa)
    If it doesn't exist, set it to 0 - signifying that it started as white and is now turned upside down to black
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of the pathfinding portion of my algorithm
Pathfinding algorithm

Counting the tiles with black side facing up 

Generate a list containing only the values from the now-filled dictionary of coordinate-boolean mappings
Filter the list to include only values of 0 - representing black-side face-up tiles
Return the length of the filtered list
Enter fullscreen mode Exit fullscreen mode

Visualizing the tile floor 

Create a unique list of coordinates of each target tile from the processed input list of tiles
Determine four values from the unique list of coordinates:
  1. Smallest value in first location:  minY
  2. Largest value in first location:   maxY
  3. Smallest value in second location: minX
  4. Largest value in second location:  maxX
Create an array of arrays - with space characters for values - with the following sizes:
  The outer array has a length one larger than maxY - minY
  Each nested array has a length one larger than maxX - minX
For each tile in the processed object storing tile locations and boolean values
  If the tile is black-side face-up - has a value of 0 - then update two locations in the 2D array:
    1. The location whose row equals the sum of the middle row index and the coordinate in the first location of the tile's coordinate, and whose column equals the sum of the middle index and the coordinate in the second location of the tile's coordinate: Update it to '<'
    2. The location one index to the right: Update it to '>'
Display the grid by joining each value in the nested arrays into a string, then join each nested array into a string, separating with a new line character
Enter fullscreen mode Exit fullscreen mode

Here's how that looks:

       <>

 <><>    
<>  <>  <>
 <>      
<>    <> 
 <>      

-----
Legend:
<> = tiles with black side face up
Enter fullscreen mode Exit fullscreen mode

Part 2 - in stages

  1. Understanding the instructions
  2. Writing an adjacent tile checking algorithm
  3. Noticing an edge case
  4. Refactoring the algorithm to use recursion
  5. Fixing a performance issue
  6. Running it and waiting...for the correct answer!
  7. Updating the simulator to run for Part 2

Understanding the instructions

It took several re-reads, but I eventually understood:

Do Part 1
Do 100 times
  Check all six tiles adjacent to every tile - some were identified in Part 1, but not all
  Only if the values of the adjacent tiles match the rule corresponding to the face-up color of the center tile:
    Add the center tile to a list of tiles to be flipped
  Flip all tiles added to the list
  Count the number of tiles that now have their black side face-up
Enter fullscreen mode Exit fullscreen mode

Writing an adjacent tile checking algorithm 

For each of the six directional coordinates
  Find the coordinates of the tile in the corresponding direction from a source tile
  If the adjacent tile's coordinates are not one of the keys in our growing object of tile locations and boolean values
    Return 1, since 1 represents a never-flipped, white-side face-up tile
  Else
    Return the boolean value associated with the key: 0 or 1
Filter the list of six numbers to only include 0s
  Store the count of black-side face-up tiles
If the originating tile is black-side face-up and the count of black-side face-up adjacent tiles is one of 0,3,4,5,6
  Add the tile to the list of ones to be flipped
If the originating tile is white-side face-up and the count of black-side face-up adjacent tiles is 2
  Add the tile to the list of ones to be flipped
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my adjacent tile checking algorithm:
Algorithm visualization

Noticing an edge case

  • It's not enough to only check the adjacent tiles of the ones identified in Part 1 - and later added after each day
  • There are white-side face-up tiles adjacent to 2 black-side face-up tiles that are not in that list
  • Without running the algorithm on every tile within the area bounded by the min/max X/Y coordinates, I only saw one way to account for this: run the algorithm again using each adjacent tile as the center tile - totaling 36 runs of the adjacent tile checking algorithm for each known tile: yikes!

Refactoring the algorithm to use recursion 

Call initially with times = 0
*If times is 2, end here
For each of the six directional coordinates
  Find the coordinates of the tile in the corresponding direction from a source tile
  Go to * with times + 1
  If the adjacent tile's coordinates are not one of the keys in our growing object of tile locations and boolean values
    Return 1, since 1 represents a never-flipped, white-side face-up tile
  Else
    Return the boolean value associated with the key: 0 or 1
Filter the list of six numbers to only include 0s
  Store the count of black-side face-up tiles
If the originating tile is black-side face-up and the count of black-side face-up adjacent tiles is one of 0,3,4,5,6
  Add the tile to the list of ones to be flipped
If the originating tile is white-side face-up and the count of black-side face-up adjacent tiles is 2
  Add the tile to the list of ones to be flipped
Enter fullscreen mode Exit fullscreen mode

What's changed?

  • A new times counter that starts at 0
  • Calling the first time operates on the known tile
  • Calling the second time (times = 1) operates on each adjacent tile
  • Stop at 2 so we don't run it on any further adjacent tiles

Fixing a performance issue

What you don't see in the algorithm descriptions above is the performance bug I had.

  • I was adding a key - with value of 1 - to my processed tiles input object...for each previously unidentified adjacent tile!
  • I fixed this such that only adjacent tiles whose adjacent tile black-side face-up counts passed the test would be added to the object

Running it and waiting...for the correct answer!

  • My algorithm is not fast
  • But it does finish, in a little over a minute
  • I'm convinced it is slow because of the increasing O(n^2) number of loops happening for each tile within each iteration
  • Thankfully, upon terminating, the answer it returns is the correct one for my input

Updating the simulator to run for Part 2

Most of the code from Part 1 carried through:

  • Parsing the input to generate an object of coordinates mapped to their boolean values
  • Generating a 2D array where the values were either empty or <> to represent black-side face-up tiles

What was added or changed:

  • New function to perform the necessary steps each day
  • New function to check adjacent tiles
  • Updated the 2D array generator with padded lengths to ensure each black-side face-up tile would be fully included in the print-out

Try the simulator!

Puzzle algorithm simulator

What a doozy! On to the next puzzle.

Top comments (0)

Read next

aakas profile image

Mastering the Command Design Pattern in Python

aakas -

engrsakib profile image

Harnessing the Power of React: Comprehensive Guide to useState and useEffect

Md Nazmus Sakib -

adaobilynda profile image

useReducer and how it is different from useState

Adaobi Okwuosa -

sanx profile image

Building a CRUD API with NestJS

Sanjay R -