Advent of Code 2019 Day 3
Task: Solve for X where...
Part 1
X = the Manhattan distance from the central port to the closest intersection
Part 2
X = the fewest combined steps the wires must take to reach an intersection
Example input
R8,U5,L5,D3
U7,R6,D4,L4
It represents:
- Two sets of directions, one for each wire
- Each step indicates one of four directions
UUpRRightDDownLLeft, and an integer amount toward that direction
Part 1
- I was spot-on: capture all visited coordinates
- A written description of my working algorithm
- A visual depiction of my working algorithm
- I was a bit off: data structure to store all visited coordinates
I was spot-on: capture all visited coordinates
- It is the only way I know works to identify exact spots where both wires intersect
- Thankfully, puzzles from 2020 and 2021 posed similar challenges...so I was familiar with writing this algorithm
A written description of my working algorithm
Split the input at the only newline character to create an array with two strings
Split each string at each comma character to create nested arrays with strings
Create a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinate
For each of the wires
Initialize a coordinate at 0,0
Initialize an array that will store stringified representations of the coordinates
For each instruction in the wire's list of instructions
Extract the first character as the direction
For i from 1 to the integer associated with the direction
Add to the array of coordinates a stringified representation of the current coordinate moved one step in the current direction
Update the current coordinate so it matches the one represented by the last value in the array of coordinates
Return the generated list of visited coordinates
Filter the first list of visited coordinates
Only keep values that also appear in the second list of visited coordinates
Generate a list of numbers using the filtered list
Each number will equal the sum of the absolute value of each visited coordinate's x,y positions
Sort the list in ascending order
Return the first number (the smallest number)
A visual depiction of my working algorithm
I was a bit off: data structure to store all visited coordinates
- The algorithm above takes nearly two minutes to run. Yikes!
Why does it take so long?
- I store the visited coordinates as an array
- I try to filter one wire's visited coordinate list by looking for each coordinate in the other wire's visited coordinate list
- For my puzzle input, the first wire's list is ~150,000 values
- For each of those, my program attempts to search the other list (likely similar quantity) for a match
- 150,000 searches, each one having to inspect 0-150,000 values
- No wonder that part takes nearly 120 seconds
Another JavaScript solver, NullDev, wrote a similar algorithm to mine...with one difference:
- Where my algorithm used an array to store an ordered list of visited coordinates
- Their algorithm used an object with keys as stringified coordinates and values as the length of the path by the time that coordinate was visited
NullDev's algorithm finishes in about a second.
Why is NullDev's algorithm so fast?
- The filtering step looks for a matching key between objects mapping visited coordinates to length of path
- Looking up a key on an object - even one with 100,000+ keys - is near-instant...compared to searching an array with 100,000+ values for a match
I'm so glad this puzzle helped me stumble upon this realization.
Part 2
- A written description of my slightly-modified working algorithm using objects instead of arrays
- A visual depiction of my working algorithm
A written description of my slightly-modified working algorithm using objects instead of arrays
Split the input at the only newline character to create an array with two strings
Split each string at each comma character to create nested arrays with strings
Create a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinate
For each of the wires
Initialize a coordinate at 0,0
Initialize an object, locations, that will map stringified representations of the coordinates to the length of the path by the time that coordinate is reached
Initialize length at 0
For each instruction in the wire's list of instructions
Extract the first character as the direction
For i from 1 to the integer associated with the direction
Increment length by 1
Add to locations a key whose label is a stringified representation of the current coordinate moved one step in the current direction, and whose value is set to length
Update the current coordinate so it matches the most recently added key in locations
Return locations
Create a list containing all the keys from the locations object generated from the first wire's visited coordinates
Filter the list, keeping only values that are also keys in the locations object generated from the second wire's visited coordinates
Generate a list of numbers using the filtered list
Each number will equal the sum of the length of each path at the shared coordinate value of both wires
Sort the list in ascending order
Return the first number (the smallest number)
A visual depiction of my working algorithm
No simulator?
I was tempted to make a simulator.
But I made a simulator for a similar puzzle where I draw the path of a ship.
And by the time I wrote both algorithms twice and made the GIFs, I was ready to move on from this puzzle.
Top comments (0)