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!