## DEV Community # No Time for a Taxicab

## 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, +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, +move.slice(1)]
switch (rotation) {
case "R":
compass.unshift(compass.pop())
break;
case "L":
compass.push(compass.shift())
break;
}
return [
coords + amount * compass,
coords + amount * compass
]
}, [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 + compass,
coords + compass
]
if (visited.has(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 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!