DEV Community

Cover image for Rope Bridge
Robert Mion
Robert Mion

Posted on

1 1

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)
Enter fullscreen mode Exit fullscreen mode

My initial variables:

H = [ '0,0' ]
T = [ '0,0' ]

directions = {
  'U': [-1,0],
  'R': [0,1],
  'D': [1,0],
  'L': [0,-1]
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Part 2

Not crossing this bridge

Why not?

In the updated example diagram, there is this before-and-after:

......
......
......
....H.
4321..

......
......
....H.
.4321.
5.....
Enter fullscreen mode Exit fullscreen mode
  • 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!

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay