Day 9: Rope Bridge

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python` with any of the "short names" listed in this page of supported languages):

``````<details>
<summary>Part 1</summary>

```python
```

</details>
``````

1. [3]
tjf
My Python solution, using complex numbers (which are helpfully one of the language's basic numeric types). Another great problem from Eric! Part 1 #!/usr/bin/env pypy3 import sys NUMKNOTS = 2...

My Python solution, using complex numbers (which are helpfully one of the language's basic numeric types). Another great problem from Eric!

Part 1
``````#!/usr/bin/env pypy3

import sys

NUMKNOTS = 2
DIRECTIONS = {
'R': 1,
'L': -1,
'U': 1j,
'D': -1j,
}

def update(z1, z2):
dz = z1 - z2
if abs(dz) < 2: # ceil(sqrt(2))
return 0
return complex(*(part / abs(part) if part else 0
for part in (dz.real, dz.imag)))

def main():
knots = [0 + 0j] * NUMKNOTS
visited = {knots[-1]}
for line in sys.stdin:
direction, magnitude = line.split()
for _ in range(int(magnitude)):
knots[0] += DIRECTIONS[direction]
for i in range(1, NUMKNOTS):
knots[i] += update(knots[i - 1], knots[i])

print(len(visited))

if __name__ == '__main__':
main()
``````
Because I refactored my solution to a general n-knot case, the only change in the code for Part 2 is the `NUMKNOTS` constant.
Part 2
``````#!/usr/bin/env pypy3

import sys

NUMKNOTS = 10
DIRECTIONS = {
'R': 1,
'L': -1,
'U': 1j,
'D': -1j,
}

def update(z1, z2):
dz = z1 - z2
if abs(dz) < 2: # ceil(sqrt(2))
return 0
return complex(*(part / abs(part) if part else 0
for part in (dz.real, dz.imag)))

def main():
knots = [0 + 0j] * NUMKNOTS
visited = {knots[-1]}
for line in sys.stdin:
direction, magnitude = line.split()
for _ in range(int(magnitude)):
knots[0] += DIRECTIONS[direction]
for i in range(1, NUMKNOTS):
knots[i] += update(knots[i - 1], knots[i])

print(len(visited))

if __name__ == '__main__':
main()
``````
1. [2]
nothis
Wait... what?

using complex numbers

Wait... what?

1. bhrgunatha
Complex numbers have both real and imaginary parts, so they can treated as Cartesian co-ordinates, x being the real and y the imaginary. e.g. In python if your point P is 1+2j Cardinal directions...

Complex numbers have both real and imaginary parts, so they can treated as Cartesian co-ordinates, x being the real and y the imaginary.

e.g. In python if your point P is `1+2j `
Cardinal directions can also be complex numbers:
N: `0+1j` S: `0-1j` `E: 1+0j` `W: -1+0j`

You can move just by addition

• up/north: `P+N = 1+3j`
• down/south: `P+S = 1+1j`
• left/east: `P+W = 0+2j` - displayed just as `2j`
• right/west: `P+E = 2+2j`

You can also change direction by turning left, L=N: `0+1j` or right, R=S: `0-1j` using multiplication.

• left:
• N*L = W
• E*L = N
• S*L = E
• W*L = S
• right:
• N*R = E
• E*R = S
• S*R = W
• W*R = N

I'm doing this from memory so I might have got the exact details wrong, but the idea is correct.

2. primordial-soup
(edited )
Part 1, in Python-ish step = {"R": (1, 0), "L": (-1, 0), "D": (0, 1), "U": (0, -1)} head = np.full(2, 0, dtype=object) tail = np.full(2, 0, dtype=object) visited = {tuple(tail)} for l in ls: inst,...
Part 1, in Python-ish
``````step = {"R": (1, 0), "L": (-1, 0), "D": (0, 1), "U": (0, -1)}
tail = np.full(2, 0, dtype=object)
visited = {tuple(tail)}
for l in ls:
inst, n_str = l.split()
for _ in range(int(n_str)):
if any(abs(diff := head - tail) > 1):
tail += np.sign(diff)
len(visited)
``````
Python code generated from the above
``````import sys
from pyp import pypprint
import numpy as np
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
step = {'R': (1, 0), 'L': (-1, 0), 'D': (0, 1), 'U': (0, -1)}
tail = np.full(2, 0, dtype=object)
visited = {tuple(tail)}
for l in ls:
(inst, n_str) = l.split()
for _ in range(int(n_str)):
if any(abs((diff := (head - tail))) > 1):
tail += np.sign(diff)
output = len(visited)
if output is not None:
pypprint(output)
``````
Part 2, in Python-ish
``````step = {"R": (1, 0), "L": (-1, 0), "D": (0, 1), "U": (0, -1)}
knots = np.full((10, 2), 0, dtype=object)
visited = {tuple(knots[-1])}
for l in ls:
inst, n_str = l.split()
for _ in range(int(n_str)):
knots[0] += step[inst]
for i in range(1, len(knots)):
if any(abs(diff := knots[i - 1] - knots[i]) > 1):
knots[i] += np.sign(diff)
len(visited)
``````
Python code generated from the above
``````import sys
from pyp import pypprint
import numpy as np
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
step = {'R': (1, 0), 'L': (-1, 0), 'D': (0, 1), 'U': (0, -1)}
knots = np.full((10, 2), 0, dtype=object)
visited = {tuple(knots[-1])}
for l in ls:
(inst, n_str) = l.split()
for _ in range(int(n_str)):
knots[0] += step[inst]
for i in range(1, len(knots)):
if any(abs((diff := (knots[i - 1] - knots[i]))) > 1):
knots[i] += np.sign(diff)
output = len(visited)
if output is not None:
pypprint(output)
``````
3. spit-evil-olive-tips
part 1 I started out with a big ugly complicated if statement for determining which direction to move the tail. that got me through part 1, then I ended up converting it to a lookup table which...
part 1

I started out with a big ugly complicated if statement for determining which direction to move the tail. that got me through part 1, then I ended up converting it to a lookup table which worked much better, because I needed to expand it for the `(2, 2)` cases. I backported that to my part 1 solution because it was so much cleaner.

``````# map of (diff_x, diff_y) (the difference between head and tail)
# to (delta_x, delta_y) (the amount to move the tail)
TAIL_MOVES = {
(0, 0):  (0, 0),

# cardinal directions
(0, 1):   (0, 0),
(0, -1):  (0, 0),
(1, 0):   (0, 0),
(-1, 0):  (0, 0),

(2, 0):   (1, 0),
(0, 2):   (0, 1),
(-2, 0):  (-1, 0),
(0, -2):  (0, -1),

# one step diagonal
(1, 1):   (0, 0),
(-1, 1):  (0, 0),
(1, -1):  (0, 0),
(-1, -1): (0, 0),

# knight's move
(1, 2): (1, 1),
(-1, 2): (-1, 1),
(1, -2): (1, -1),
(-1, -2): (-1, -1),

(2, 1): (1, 1),
(-2, 1): (-1, 1),
(2, -1): (1, -1),
(-2, -1): (-1, -1),
}

tail_x, tail_y = tail

delta_x, delta_y = TAIL_MOVES[(diff_x, diff_y)]

return tail_x + delta_x, tail_y + delta_y

MOVES = {
'R': (1, 0),
'L': (-1, 0),
'U': (0, 1),
'D': (0, -1),
}

with open('09.txt') as input_file:

tail = 0, 0

tail_positions = set()

for line in lines:
parts = line.strip().split(' ')
direction, length = parts[0], int(parts[1])

delta_x, delta_y = MOVES[direction]
for _ in range(length):

print(len(tail_positions))
``````
part 2
``````--- aoc09a.py   2022-12-08 22:20:16.292632216 -0800
+++ aoc09b.py   2022-12-08 22:15:52.521454415 -0800
@@ -20,6 +20,12 @@
(1, -1):  (0, 0),
(-1, -1): (0, 0),

+    # two steps diagonal
+    (2, 2):   (1, 1),
+    (-2, 2):  (-1, 1),
+    (2, -2):  (1, -1),
+    (-2, -2): (-1, -1),
+
# knight's move
(1, 2): (1, 1),
(-1, 2): (-1, 1),
@@ -45,6 +51,26 @@
return tail_x + delta_x, tail_y + delta_y

+class Rope:
+    def __init__(self, length):
+        self.length = length
+        self.segments = [(0, 0)] * length
+
+    def move(self, delta_x, delta_y):
+
+        for i in range(1, self.length):
+            tail = self.segments[i]
+            self.segments[i] = new_tail
+
+    @property
+    def tail(self):
+        return self.segments[-1]
+
+
MOVES = {
'R': (1, 0),
'L': (-1, 0),
@@ -55,11 +81,10 @@
with open('09.txt') as input_file:

-tail = 0, 0
+rope = Rope(10)

tail_positions = set()

for line in lines:
parts = line.strip().split(' ')
@@ -67,10 +92,7 @@

delta_x, delta_y = MOVES[direction]
for _ in range(length):
-
+        rope.move(delta_x, delta_y)

print(len(tail_positions))
``````
4. [2]
jzimbel
Elixir I tried to "speedrun" this one but tripped myself up for a while on part 1 by referencing the previous value of the head when determining whether the tail was adjacent to it! Overall my...

Elixir

I tried to "speedrun" this one but tripped myself up for a while on part 1 by referencing the previous value of the head when determining whether the tail was adjacent to it!

Overall my code is pretty messy, but I'm happy with how easy it was to adapt it to part 2. I'll probably come back later and clean it up.

Both parts
``````defmodule AdventOfCode.Solution.Year2022.Day09 do
defstruct [:knots, visited: MapSet.new([{0, 0}])]

@deltas %{
?U => {0, -1},
?R => {1, 0},
?D => {0, 1},
?L => {-1, 0}
}

def part1(input) do
input
|> String.split("\n", trim: true)
|> Enum.reduce(%__MODULE__{knots: List.duplicate({0, 0}, 2)}, &process_command/2)
|> then(fn state -> MapSet.size(state.visited) end)
end

def part2(input) do
input
|> String.split("\n", trim: true)
|> Enum.reduce(%__MODULE__{knots: List.duplicate({0, 0}, 10)}, &process_command/2)
|> then(fn state -> MapSet.size(state.visited) end)
end

defp process_command(<<dir, ?\s, n::binary>>, state) do
delta = @deltas[dir]

Enum.reduce(1..String.to_integer(n), state, fn _, state_acc -> move(state_acc, delta) end)
end

defp move(%{knots: [h | ts], visited: visited}, delta) do
h = sum_coords(h, delta)

ts = propagate(ts, h)
visited = MapSet.put(visited, List.last(ts))

%{knots: [h | ts], visited: visited}
end

defp propagate([], _), do: []

defp propagate([t | ts], h) do
t = if adjacent?(h, t), do: t, else: move_toward(t, h)
[t | propagate(ts, t)]
end

defp sum_coords({x, y}, {x2, y2}), do: {x + x2, y + y2}

defp adjacent?({x, y}, {x2, y2}) do
abs(x2 - x) <= 1 and abs(y2 - y) <= 1
end

defp move_toward({tx, ty}, {hx, hy}) do
x_move =
case hx - tx do
0 -> 0
n when n > 0 -> 1
n when n < 0 -> -1
end

y_move =
case hy - ty do
0 -> 0
n when n > 0 -> 1
n when n < 0 -> -1
end

{tx + x_move, ty + y_move}
end
end
``````

Part 1 runs in about 7 ms, part 2 in about 15 ms.

1. jzimbel
(edited )
Shortened with excessive weird one-line functions!! Also, I realized that Enum.scan/2 was perfect for propagating movements down the length of the rope. Both parts but shorter defmodule...

Shortened with excessive weird one-line functions!! Also, I realized that `Enum.scan/2` was perfect for propagating movements down the length of the rope.

Both parts but shorter
``````defmodule AdventOfCode.Solution.Year2022.Day09 do
defstruct [:knots, visited: MapSet.new([{0, 0}])]

def part1(input), do: solve(input, 2)
def part2(input), do: solve(input, 10)

defp solve(input, knot_count) do
initial_state = %__MODULE__{knots: List.duplicate({0, 0}, knot_count)}

final_state =
input
|> String.split("\n", trim: true)
|> Enum.reduce(initial_state, &process_command/2)

MapSet.size(final_state.visited)
end

for {dir, delta} <- [{?U, {0, -1}}, {?R, {1, 0}}, {?D, {0, 1}}, {?L, {-1, 0}}] do
defp process_command(<<unquote(dir), " ", steps::binary>>, state) do
for _ <- 1..String.to_integer(steps), reduce: state, do: (acc -> move(acc, unquote(delta)))
end
end

defp move(%__MODULE__{knots: [h | t], visited: visited}, delta) do
knots = Enum.scan([add(h, delta) | t], &propagate/2)
visited = MapSet.put(visited, List.last(knots))

%__MODULE__{knots: knots, visited: visited}
end

defp propagate(t, h), do: if(adjacent?(h, t), do: t, else: move_toward(t, h))

defp adjacent?({x, y}, {x2, y2}), do: abs(x2 - x) <= 1 and abs(y2 - y) <= 1

defp move_toward({tx, ty}, {hx, hy}), do: add({tx, ty}, {get_move(hx - tx), get_move(hy - ty)})

defp get_move(0), do: 0
defp get_move(diff), do: div(diff, abs(diff))

defp add({x, y}, {x2, y2}), do: {x + x2, y + y2}
end
``````
1 vote
5. asterisk
Python motions = open("input.txt").read().split("\n") routes = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)} def touching(knots, i): if not knots[i]: return (0, 0) px, py = knots[i - 1]...
Python
``````motions = open("input.txt").read().split("\n")
routes = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}

def touching(knots, i):
if not knots[i]:
return (0, 0)

px, py = knots[i - 1]
mx, my = knots[i]
kx, ky = knots[i]

for x in (mx - 1, mx, mx + 1):
for y in (my - 1, my, my + 1):
if x == px and y == py:
return knots[i]

if kx == px:
ky += 1 if py - ky > 0 else -1

if ky == py:
kx += 1 if px - kx > 0 else -1

if kx == mx and ky == my:
kx += 1 if px - kx > 0 else -1
ky += 1 if py - ky > 0 else -1

return (kx, ky)

def simulation(knots: int = 1) -> int:
knots = [(0, 0)] + [None for _ in range(knots)]
history = set()

for motion in motions:
route, steps = motion.split(" ")

for _ in range(int(steps)):
knots[0] = list(map(lambda a, b: a + b, knots[0], routes[route]))

for i in range(1, len(knots), 1):
knots[i] = touching(knots, i)

return len(history)

print(simulation())  # Part One: 6470
print(simulation(9))  # Part Two: 2658
``````
6. bhrgunatha
Today reminded me of this Utilities (define ORIGIN (list 0 0)) (define MAX-KNOT (make-parameter #f)) (match-define (list UP DOWN LEFT RIGHT) '((0 -1) (0 1) (-1 0) (1 0))) (define (point+ p1 p2)...

Today reminded me of this

A mystery investigating teenager or dog dog!! who beyond the age of 26 finds himself still using a jungle canyon rope-bridge can count himself a failure in life.

Utilities
``````(define ORIGIN (list 0 0))
(define MAX-KNOT (make-parameter #f))
(match-define (list UP DOWN LEFT RIGHT)
'((0 -1) (0 1) (-1 0) (1 0)))

(define (point+ p1 p2) (map + p1 p2))
(define (vec p1 p2) (map - p1 p2))
(define (vec-abs p1 p2) (map abs (vec p1 p2)))
``````
Part 1
``````(define (part-01 input)
(cross-river 1 input))

(define (cross-river knots input)
(MAX-KNOT knots)
(for/fold ([rope (for/hash ([i (in-inclusive-range 0 knots)])
(values i ORIGIN))]
[ts (set ORIGIN)]
#:result (set-count ts))
([ins (in-list input)])
(define-values (rope+ ts+)
(match (string-split ins)
[`("U" ,n) (move-head UP    (string->number n) rope ts)]
[`("D" ,n) (move-head DOWN  (string->number n) rope ts)]
[`("L" ,n) (move-head LEFT  (string->number n) rope ts)]
[`("R" ,n) (move-head RIGHT (string->number n) rope ts)]
[else (error 'cross-river "unknown instruction" ins)]))
(values rope+ ts+)))

(define (move-head dir n rope ts)
(for/fold ([rope rope] [ts ts])
([i (in-range n)])
(define head (point+ (hash-ref rope 0) dir))
(define rope+ (move-knots (hash-set rope 0 head)))
(define ts+ (set-add ts (hash-ref rope+ (MAX-KNOT))))
(values rope+ ts+)))

(define (move-knots rope)
(for/fold ([rope rope]
[done? #f] #:result rope)
([knot (in-range 0 (MAX-KNOT))] #:break done?)
(define start (hash-ref rope knot))
(define end (hash-ref rope (add1 knot)))
(define end+ (move-knot start end))
(values
(equal? end end+))))

(define (move-knot h t)
(match-define (list x y) h)
(cond
[(stay?  h t) t]
[(diag?  h t) (diagonal h t)]
[(above? h t) (list x (sub1 y))]
[(below? h t) (list x (add1 y))]
[(left?  h t) (list (sub1 x) y)]
[(right? h t) (list (add1 x) y)]
[else (error 'move-knot "head: ~a tail: ~a" h t)]))

(define (diagonal h t)
(match-define (list x y) t)
(match (vec h t)
['(-2  2) (list (sub1 x) (add1 y))]
['( 2 -2) (list (add1 x) (sub1 y))]
['(-2 -2) (list (sub1 x) (sub1 y))]
[_ (error 'diagonal "not diagonal ~a ~a" h t)]))

(define (stay? h t)
(match-define (list dx dy) (vec-abs h t))
(and (< dx 2) (< dy 2)))

(define (diag? h t)
(match-define (list dx dy) (vec-abs h t))
(= dx dy 2))

(define (above? h t)
(match-define (list dx dy) (vec h t))
(= dy 2))

(define (below? h t)
(match-define (list dx dy) (vec h t))
(= dy -2))

(define (left? h t)
(match-define (list dx dy) (vec h t))
(= dx 2))

(define (right? h t)
(match-define (list dx dy) (vec h t))
(= dx -2))
``````
Part 2

Converted `cross-river` from using just head and tail of the rope to a hash of knots.
It makes part 2 very simple.

``````(define (part-02 input)
(cross-river 9 input))
``````
7. Crestwave
Well my attempts at shortcuts certainly didn't do me any favors in part 2. Part 1 The idea was basically to move to the previous position of the head if there are more than two spaces between...

Well my attempts at shortcuts certainly didn't do me any favors in part 2.

Part 1 The idea was basically to move to the previous position of the head if there are more than two spaces between them.
``````#!/usr/bin/awk -f
{
for (i = 1; i <= \$2; ++i) {
_x = x
_y = y

if (/U/)
y -= 1
else if (/D/)
y += 1
else if (/L/)
x -= 1
else if (/R/)
x += 1

__x = X > x ? X-x : x-X
__y = Y > y ? Y-y : y-Y

if (__x > 1 || __y > 1) {
X = _x
Y = _y
}

grid[X, Y] = 1
}
}

END {
for (i in grid)
if (grid[i])
sum += 1

print(sum)
}
``````
Part 2 I had to rewrite the logic for this part due to the more complex movements possible.
``````#!/usr/bin/awk -f
BEGIN {
for (i = 0; i <= 9; ++i) {
X[i] = 0
Y[i] = 0
}
}

{
for (i = 1; i <= \$2; ++i) {
if (/U/)
Y[0] -= 1
else if (/D/)
Y[0] += 1
else if (/L/)
X[0] -= 1
else if (/R/)
X[0] += 1

for (j = 1; j <= 9; ++j) {
x = X[j-1] - X[j]
y = Y[j-1] - Y[j]

if (x == 2)
X[j] = X[j-1] - 1
else if (x == -2)
X[j] = X[j-1] + 1
else if (y == 2 || y == -2)
X[j] = X[j-1]

if (y == 2)
Y[j] = Y[j-1] - 1
else if (y == -2)
Y[j] = Y[j-1] + 1
else if (x == 2 || x == -2)
Y[j] = Y[j-1]

if (j == 9)
grid[X[j], Y[j]] = 1
}
}

}

END {
for (i in grid)
if (grid[i])
sum += 1

print(sum)
}
``````
1 vote
8. Gyrfalcon
Late, long, and clunky, but correct solution! Ended up refactoring for part 2 to make things configurable which helped marginally, but not as much as one might hope, since that wasn't really the...

Late, long, and clunky, but correct solution! Ended up refactoring for part 2 to make things configurable which helped marginally, but not as much as one might hope, since that wasn't really the part I'm not proud of anyway lol.

Part 1 and 2, Python
``````current_dir = os.path.realpath(os.path.dirname(__file__))
INPUT_FILE = "/".join([current_dir, "input.txt"])
TEST_FILE_1 = "/".join([current_dir, "test1.txt"])
TEST_RESULTS_1 = (13, 1)
TEST_FILE_2 = "/".join([current_dir, "test2.txt"])
TEST_RESULTS_2 = (88, 36)

def tail_move(head_pos, tail_pos: Tuple[int, int]) -> Tuple[int, int]:
if head_pos[1] == tail_pos[1] + 2:
return (tail_pos[0], tail_pos[1] + 1)
if head_pos[1] == tail_pos[1] - 2:
return (tail_pos[0], tail_pos[1] - 1)
return tail_pos

if head_pos[0] == tail_pos[0] + 2:
return (tail_pos[0] + 1, tail_pos[1])
if head_pos[0] == tail_pos[0] - 2:
return (tail_pos[0] - 1, tail_pos[1])
return tail_pos

if (
or (head_pos[0] == tail_pos[0] + 1 and head_pos[1] == tail_pos[1] + 2)
or (head_pos[0] == tail_pos[0] + 2 and head_pos[1] == tail_pos[1] + 2)
):
return (tail_pos[0] + 1, tail_pos[1] + 1)

if (
or (head_pos[0] == tail_pos[0] - 1 and head_pos[1] == tail_pos[1] + 2)
or (head_pos[0] == tail_pos[0] - 2 and head_pos[1] == tail_pos[1] + 2)
):
return (tail_pos[0] - 1, tail_pos[1] + 1)

if (
or (head_pos[0] == tail_pos[0] + 1 and head_pos[1] == tail_pos[1] - 2)
or (head_pos[0] == tail_pos[0] + 2 and head_pos[1] == tail_pos[1] - 2)
):
return (tail_pos[0] + 1, tail_pos[1] - 1)

if (
or (head_pos[0] == tail_pos[0] - 1 and head_pos[1] == tail_pos[1] - 2)
or (head_pos[0] == tail_pos[0] - 2 and head_pos[1] == tail_pos[1] - 2)
):
return (tail_pos[0] - 1, tail_pos[1] - 1)

return tail_pos

def run_commands(commands: List[List[str]], rope_length: int) -> Set[Tuple[int, int]]:

rope_pos = [(0, 0) for _ in range(rope_length)]
visited = {rope_pos[-1]}

moves = {
"R": lambda pos: (pos[0] + 1, pos[1]),
"L": lambda pos: (pos[0] - 1, pos[1]),
"U": lambda pos: (pos[0], pos[1] + 1),
"D": lambda pos: (pos[0], pos[1] - 1),
}

for command in commands:
for _ in range(int(command[1])):
rope_pos[0] = moves[command[0]](rope_pos[0])
for idx in range(1, rope_length):
rope_pos[idx] = tail_move(rope_pos[idx - 1], rope_pos[idx])

return visited

def main(filepath: str) -> Tuple[int, int]: