9 votes

Day 9: Rope Bridge

Automatically posted
Tags: advent of code.2022

Today's problem description: https://adventofcode.com/2022/day/9

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
Your code here.
```

</details>

10 comments

  1. [3]
    tjf
    Link
    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])
            visited.add(knots[-1])

    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])
            visited.add(knots[-1])

    print(len(visited))

if __name__ == '__main__':
    main()
    4 votes
    1. [2]
      nothis
      Link Parent
      Wait... what?

      using complex numbers

      Wait... what?

      1. bhrgunatha
        Link Parent
        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.

        3 votes
  2. primordial-soup
    (edited )
    Link
    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)}
head = np.full(2, 0, dtype=object)
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)):
        head += step[inst]
        if any(abs(diff := head - tail) > 1):
            tail += np.sign(diff)
            visited.add(tuple(tail))
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)}
head = np.full(2, 0, dtype=object)
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)):
        head += step[inst]
        if any(abs((diff := (head - tail))) > 1):
            tail += np.sign(diff)
            visited.add(tuple(tail))
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)
        visited.add(tuple(knots[-1]))
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)
        visited.add(tuple(knots[-1]))
output = len(visited)
if output is not None:
    pypprint(output)
    3 votes
  3. [2]
    jzimbel
    Link
    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.

    2 votes
    1. jzimbel
      (edited )
      Link Parent
      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
  4. asterisk
    Link
    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)

            history.add(knots[-1])

    return len(history)


print(simulation())  # Part One: 6470
print(simulation(9))  # Part Two: 2658
    2 votes
  5. bhrgunatha
    Link
    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
     (hash-set rope (add1 knot) end+)
     (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 (add1 x) (add1 y))]
    ['(-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))
    2 votes
  6. Crestwave
    Link
    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
  7. Gyrfalcon
    Link
    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[0] == tail_pos[0]:
        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[1] == tail_pos[1]:
        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 (
        (head_pos[0] == tail_pos[0] + 2 and head_pos[1] == tail_pos[1] + 1) 
        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 (
        (head_pos[0] == tail_pos[0] - 2 and head_pos[1] == tail_pos[1] + 1) 
        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 (
        (head_pos[0] == tail_pos[0] + 2 and head_pos[1] == tail_pos[1] - 1) 
        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 (
        (head_pos[0] == tail_pos[0] - 2 and head_pos[1] == tail_pos[1] - 1) 
        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])
            visited.add(rope_pos[-1])

    return visited


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

    commands = [line.split() for line in load_file.load_cleaned_lines(filepath)]

    return (len(run_commands(commands, 2)), len(run_commands(commands, 10)))


if __name__ == "__main__":
    part1, part2 = main(INPUT_FILE)

    print(part1)
    print(part2)
    1 vote