No Time for a Taxicab
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-09-02 14:52:32

## [Advent of Code 2016 Day 1](https://adventofcode.com/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

```js
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

```js
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:
```js
[[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:
![Animation of my algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/io22kpv9pv6axqveeaat.gif)

My algorithm in JavaScript:
```js
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:
```js
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:
```js
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:
```js
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](https://aocsimulators.rmion.repl.co/) (lowest yet, but sadly very few visually-interactive puzzles)
- Countless GIFs created

My map mostly lit up:
![Calendar upon year finish](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9uglq1oq7botukk6qfd6.gif)

My star counts down thru this year:
232/300 possible stars by now: `77%` - that's still a passing grade: C+!
![Star counts](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qzw6gy6r4e23m0v0tzcj.png)

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!