Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
April 21, 2022 07:03 pm GMT

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 Up R Right D Down L Left, and an integer amount toward that direction

Part 1

  1. I was spot-on: capture all visited coordinates
  2. A written description of my working algorithm
  3. A visual depiction of my working algorithm
  4. 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

Algorithm for Part 1 using arrays

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

  1. A written description of my slightly-modified working algorithm using objects instead of arrays
  2. 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

Algorithm for Part 2 using objects

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:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To