DEV Community

Cover image for No Time for a Taxicab
Robert Mion
Robert Mion

Posted on

No Time for a Taxicab

#adventofcode #algorithms #javascript #programming

Advent of Code 2016 Day 1

Part 1

  1. More Manhattan Distance
  2. Circular compass data structure
  3. Switching direction based on the rotation type
  4. Going the distance
  5. Calculating the Manhattan Distance
  6. Altogether thru animation

More Manhattan Distance

  • I've written this exact algorithm for prior puzzles
  • So this will be an opportunity to practice re-writing one from scratch

Circular compass data structure

  • I need to know the direction I'm facing
  • That way, I can increment or decrement the proper axis the specified number of steps
  • I'll use a 4-element array where each element is a 2-element array containing the modifier by which to multiply the amount per axis: either a 0, 1 or -1
  • Depending on the direction of rotation, I'll move an element from the beginning to end or vice versa
  • My algorithm will always use the first element in the array 
compass = [ [0,-1], // North [1,0], // East [0,1], // South [-1,0] // West ]
Enter fullscreen mode Exit fullscreen mode

Switching direction based on the rotation type

  • I need to separate the rotation type from the amount
  • Depending on the rotation character, R or L, I need to rotate the elements in the array 
let [turn, amount] = [c[0], +c.slice(1)] switch (turn) { case "R": compass.unshift(compass.pop()) break; case "L": compass.push(compass.shift()) break; }
Enter fullscreen mode Exit fullscreen mode

Starting with NSEW, an R rotation moves N to the end:

N<-S<-E<-W S E W N
Enter fullscreen mode Exit fullscreen mode

Followed by an L rotation, everything moves right:

S->E->W->N N S E W
Enter fullscreen mode Exit fullscreen mode

Going the distance

An instruction like R5 should move me from:

 x y [0,0]
Enter fullscreen mode Exit fullscreen mode

To:

 x y [5,0]
Enter fullscreen mode Exit fullscreen mode

How compass changes with an R rotation:

[[0,-1],[1,0],[0,1],[-1,0]] // R5 [[1,0],[0,1],[-1,0],[0,-1]] // Only reference first item [1,0]
Enter fullscreen mode Exit fullscreen mode

How the multiplication works:

[ 0 , 0 ] +1 +0 *5 *5 [ 5 , 0 ]
Enter fullscreen mode Exit fullscreen mode

Calculating the Manhattan Distance

The sum of the absolute value of each coordinate.

For example:

[10, -2] 10 + 2 12
Enter fullscreen mode Exit fullscreen mode

Altogether thru animation

This animation shows how my algorithm works on the last example unit test:
Animation of my algorithm

My algorithm in JavaScript:

let compass = [[0,-1],[1,0],[0,1],[-1,0]] return input.reduce( (coords, move) => { let [rotation, amount] = [move[0], +move.slice(1)] switch (rotation) { case "R": compass.unshift(compass.pop()) break; case "L": compass.push(compass.shift()) break; } return [ coords[0] + amount * compass[0][0], coords[1] + amount * compass[0][1] ] }, [0,0]) .reduce((a, b) => Math.abs(a) + Math.abs(b))
Enter fullscreen mode Exit fullscreen mode

Part 2

  1. Enter: Set() and a for loop

Enter: Set() and a for loop

  • I now have to track each step along the way
  • With each step, I need to check if that step was already visited

My Set() will start as:

let visited = new Set('0|0')
Enter fullscreen mode Exit fullscreen mode
  • I stringify the coordinate because comparing two arrays always returns false

I also need to collect each repeated step:

let answers = []
Enter fullscreen mode Exit fullscreen mode

Lastly, instead of changing a coordinate by the full amount, I need to:

  • Move it by 1
  • Check if that step's been visited
  • If it has, add the Manhattan Distance to answers
  • Add the step to visited

My for loop in JavaScript:

for (let i = 0; i < amount; i++) { coords = [ coords[0] + compass[0][0], coords[1] + compass[0][1] ] if (visited.has(coords.join('|'))) { answers.push(Math.abs(coords[0]) + Math.abs(coords[1])) } visited.add(coords.join('|')) }
Enter fullscreen mode Exit fullscreen mode

An optimization is to use a while loop that escapes as soon as answer has a value.

But the path is so short that the algorithm still terminates near-instantly with the correct answer stored as the first item in answer!

I did it!!

  • I solved both parts!
  • I used tools like reduce(), Set()s, switch statements, array manipulation methods, Math and array destructuring!
  • I maintained my 2-star streak - except for Day 11 - since Day 22!

Year in review

  • 43 stars earned: 2nd-best year!
  • 21 two-star days
  • 1 one-star day
  • 3 zero-star days
  • 2 simulators built (lowest yet, but sadly very few visually-interactive puzzles)
  • Countless GIFs created

My map mostly lit up:
Calendar upon year finish

My star counts down thru this year:
232/300 possible stars by now: 77% - that's still a passing grade: C+!
Star counts

I'm so glad I've made it to the last - earliest? - year.

But I'm sad I only have 25 puzzles left...

...that is, until this December! I hope!

Top comments (0)