An Interest In:
Web News this Week
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
- April 11, 2024
April 21, 2022 07:03 pm GMT
Original Link: https://dev.to/rmion/crossed-wires-53ej
Crossed Wires
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,D3U7,R6,D4,L4
It represents:
- Two sets of directions, one for each wire
- Each step indicates one of four directions
U
UpR
RightD
DownL
Left, 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 stringsCreate a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinateFor 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 coordinatesFilter the first list of visited coordinates Only keep values that also appear in the second list of visited coordinatesGenerate 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 positionsSort the list in ascending orderReturn 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 stringsCreate a legend mapping each of the four directions with an amount between -1 and 1 to adjust a current x,y coordinateFor 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 locationsCreate 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 coordinatesGenerate 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 wiresSort the list in ascending orderReturn 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.
Original Link: https://dev.to/rmion/crossed-wires-53ej
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To