DEV Community

Cover image for Crossed Wires
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Part 2

X = the fewest combined steps the wires must take to reach an intersection
Enter fullscreen mode Exit fullscreen mode

Example input

R8,U5,L5,D3
U7,R6,D4,L4
Enter fullscreen mode Exit fullscreen mode

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 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)
Enter fullscreen mode Exit fullscreen mode

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 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)
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)