No Time for a Taxicab

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
]

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;
}

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

N<-S<-E<-W
S  E  W  N

Followed by an L rotation, everything moves right:

S->E->W->N
N  S  E  W

Going the distance

An instruction like R5 should move me from:

 x y
[0,0]

To:

 x y
[5,0]

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]

How the multiplication works:

[ 0 , 0 ]
 +1  +0
 *5  *5

[ 5 , 0 ]

Calculating the Manhattan Distance

The sum of the absolute value of each coordinate.

For example:

[10, -2]

 10 + 2

 12

Altogether thru animation

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

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))

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')

• I stringify the coordinate because comparing two arrays always returns false

I also need to collect each repeated step:

let answers = []

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('|'))
}

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:

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

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!