Advent of Code 2020 Day 24
Try the simulator!
Task: Solve for X where...
X = number of tiles with black side face up
- After flipping each tile in the input
- After flipping 100 times according to a formula
Example input
seswneswswsenwwnwse
wsweesenenewnwwnwsenewsenwwsesesenwne
wseweeenwnesenwwwswnew
...
Each line:
- represents a destination tile
- contains up to 6 directions:
e,se,sw,w,nw,ne
Part 1 - in stages
- Extracting each direction from each line
- Creating a coordinate system
- Performing the
flips - Counting the tiles with black side facing up
- 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
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!
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
Here's a visualization of the pathfinding portion of my 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
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
Here's how that looks:
<>
<><>
<> <> <>
<>
<> <>
<>
-----
Legend:
<> = tiles with black side face up
Part 2 - in stages
- Understanding the instructions
- Writing an adjacent tile checking algorithm
- Noticing an edge case
- Refactoring the algorithm to use recursion
- Fixing a performance issue
- Running it and waiting...for the correct answer!
- 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
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
Here's a visualization of my adjacent tile checking algorithm:
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
What's changed?
- A new
timescounter 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!
What a doozy! On to the next puzzle.
Top comments (0)