X = number of tiles with black side face up
- After flipping each tile in the input
- After flipping 100 times according to a formula
seswneswswsenwwnwse wsweesenenewnwwnwsenewsenwwsesesenwne wseweeenwnesenwwwswnew ...
- represents a destination tile
- contains up to 6 directions:
- Extracting each direction from each line
- Creating a coordinate system
- Performing the
- Counting the tiles with black side facing up
- Visualizing the tile floor
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
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!
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
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
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
- 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
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
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
- 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!
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
- 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
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
- 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
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
- 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
What a doozy! On to the next puzzle.