Rope Bridge

#adventofcode #algorithms #javascript #programming

Advent of Code 2022 Day 9

Part 1

Manhattan Distance for the win?
Replaying the example to outline my algorithm
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.