Rope Bridge

Advent of Code 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:

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

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!