Rope Bridge
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-09 20:55:06

## [Advent of Code 2022 Day 9](https://adventofcode.com/2022/day/9)

## Part 1
1. Manhattan Distance for the win?
2. Replaying the example to outline my algorithm
3. My algorithm in JavaScript

### Manhattan Distance for the win?
- I closely studied each diagram
- I noticed that `T` only moves diagonally when `H` is a Manhattan Distance of 3 away from `T`
- At that time, `T` moves such that the Manhattan Distance becomes 1, occupying the last spot `H` was in
- In other cases, `T` either doesn't move, or moves into the last spot occupied by `H` to maintain a Manhattan Distance of 0 or 1 (same row or column) or 2 (diagonal)

How might I account for these movement rules, without letting any conditionals get way out of control?

It seems that is my first challenge, given how I anticipate writing an algorithm

### Replaying the example to outline my algorithm
Initial State:
```
......
......
......
......
H.....  (H covers T, s)
```

My initial variables:
```js
H = [ '0,0' ]
T = [ '0,0' ]

directions = {
  'U': [-1,0],
  'R': [0,1],
  'D': [1,0],
  'L': [0,-1]
}
```

`R 4` means execute four movements to the right.
```
Do 4 times
  Move H to the right
  Determine Manhattan Distance between H and T
  If it is < 2
    Do nothing
  Else if == 2
    If same row or column
      Move T to the last spot occupied by H
    Else - diagonally adjacent
      Do nothing
  Else
    Move T to the last spot occupied by H
```

I can abstract that for any direction and movement amounts.

`DIR AMT`
```
Do AMT times
  Move H to the DIR
  Determine Manhattan Distance between H and T
  If it is < 2
    Do nothing
  Else if == 2
    If same row or column
      Move T to the last spot occupied by H
    Else - diagonally adjacent
      Do nothing
  Else
    Move T to the last spot occupied by H
```

Sub-routines:
- Move H to the DIR
- Determine Manhattan Distance
- Move T to the last spot occupied by H

#### Move H to the DIR
- I made `H` an array containing stringified coordinates
- Each movement adds an item at the end of the array
- The item is the result of adding each amount in the `directions` object to the corresponding coordinate of the last value in `H`

#### Determine Manhattan Distance
- Calculate the absolute values of the difference of each  of `H` and `T`s coordinates
- Calculate the sum of both values

#### Move T to the last spot occupied by H
- `T` is also an array and works like `H`
- Each movement of `T` adds an item at the end of the array
- That item is a string copy of the the last item in `H`

Back to the example.

`R 4` looks like this:
```
TH...

sTH..

s.TH.

s..TH
```

My `H` and `T` arrays would look like this:
```
H    T    MD
0,0  0,0  0
0,1  0,0  1
0,2  0,0  2   Same row: Move T to 0,1
0,3  0,1  2   Same row: Move T to 0,2
0,4  0,2  2   Same row: Move T to 0,3
```

`U 4` looks like this for my arrays:
```
 H     T    MD
 0,4   0,3  1
-1,4   0,3  2   Diagonal: Don't move
-2,4   0,3  3   Move T to -1,4
-3,4  -1,4  2   Same column: Move T to -2,4
-4,4  -2,4  2   Same column: Move T to -3,4
```

I feel confident enough that I have identified enough cases in my planned algorithm to now attempt writing it.

This should be a doozy!

### My algorithm in JavaScript
- Writing the pseudocode really helped!
- It works exactly as I designed it!
- With the exception of storing nested arrays, then stringifying all of `T`'s coordinates at the very end to generate the list of unique spots visited

```js
let H = [[0,0]]
let T = [[0,0]]
let moves = {
  'U': [-1,0],
  'R': [0,1],
  'D': [1,0],
  'L': [0,-1]
}
let cmds = input.split('\n').map(el => {
  let [dir, amt] = el.split(' ')
  return [dir, +amt]
})
cmds.forEach(([dir, amt] = cmd) => {
  for (let i = 0; i < amt; i++) {
    H.push([
      H[H.length - 1][0] + moves[dir][0],
      H[H.length - 1][1] + moves[dir][1]
    ])
    let MD = (
      Math.abs(H[H.length - 1][0] - T[T.length - 1][0]) +
      Math.abs(H[H.length - 1][1] - T[T.length - 1][1])
    )
    switch (MD) {
      case 0:
      case 1:
        break;
      case 2:
        if (
          H[H.length - 1][0] == T[T.length - 1][0] ||
          H[H.length - 1][1] == T[T.length - 1][1]
        ) {
          T.push(H[H.length - 2])
        }
        break;
      default:
        T.push(H[H.length - 2])
        break;
    }
  }
})
return new Set(T.map(el => el.join('|'))).size
```

## Part 2

### Not crossing this bridge
Why not?

In the updated example diagram, there is this before-and-after:
```
......
......
......
....H.
4321..

......
......
....H.
.4321.
5.....
```

- I know how to programmatically describe what makes 1 move too its new spot
- I understand why 2, 3 and 4 end up where they do
- But I fail to think of a way to programmatically ensure they would move like that

As the diagrams continue to depict how all 10 knots move in the original example, I feel further *puzzled* about each knots movement...especially in how I would recreate such movements algorithmically.

Thus, sadly, Part 2 will go unsolved for me.

## I did it!
- I solved Part 1!
- Using Manhattan Distance and arrays in lieu of a litany of nested conditionals!

I'm bummed about this being my second time that I only earned one star on a Day 9 - in all other years I earned two stars.

But, as with any Day, I'm glad I solved Part 1!