Robert Mion

Posted on

# Rope Bridge

## 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 `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
``````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!

DEV Community

## 11 Tips That Make You a Better Typescript Programmer

### 1 Think in {Set}

Type is an everyday concept to programmers, but itβs surprisingly difficult to define it succinctly. I find it helpful to use Set as a conceptual model instead.

### #2 Understand declared type and narrowed type

One extremely powerful typescript feature is automatic type narrowing based on control flow. This means a variable has two types associated with it at any specific point of code location: a declaration type and a narrowed type.

### #3 Use discriminated union instead of optional fields

...

Read the whole post now!