AoC 2022 D9: Rope Bridge

Haskell | Problem statement | Source code | Tags: Grid walking

← Previous Back to AoC Index Next →

Part 1

We have a tail that's always following the head, and we need to record the positions of the tail. Naturally we'd like to fold over the list of moves, tracking the current positions of the head and tail as well as the set of tail positions.

type State = ((Int, Int), (Int, Int), Set (Int, Int))

(_, set) = foldl' makeMove ((0, 0), (0, 0), Set.empty) moves

makeMove :: State -> ((Int, Int), Int) -> State
hs

The movement itself is done recursively over the number of steps. If we have no more steps to take, return the state as-is.

makeMove s (_, 0) = s
hs

Otherwise, we move the head one step in the given direction, and then move the tail.

makeMove (chainHead, chainTail, set) (dir, count) =
  makeMove (chainHead', chainTail', Set.insert chainTail' set) (dir, count - 1)
  where
    chainHead' = chainHead |+| dir
    chainTail' = moveTail chainHead' chainTail
hs

(By the way, I defined |+| and |-| for 2D vector arithmetic so I don't have to load Data.Vector.)

In moveTail, we check the distance between the head and tail. If it's more than 1 in either direction, we need to move the tail one step towards the head.

moveTail :: (Int, Int) -> (Int, Int) -> (Int, Int)
moveTail h' t
  | max (abs dx) (abs dy) < 2 = t
  | otherwise = t |+| (clamp (-1, 1) dx, clamp (-1, 1) dy)
  where
    (dx, dy) = h' |-| t
hs

Part 2

Now with 10 knots, we just need to upgrade the state to a collection of 10 positions. Most of the logic is the same, except I now use mapAccumL to move each knot in turn, keeping track of the previous knot's position. Conveniently, this also returns the tail position so we can add it to the set.

type State = ([(Int, Int)], Set (Int, Int))

makeMove (chainHead : rest, set) (dir, count) =
  makeMove (chainHead' : chain', Set.insert chainTail' set) (dir, count - 1)
  where
    chainHead' = chainHead |+| dir
    (chainTail', chain') =
      mapAccumL
        ( \prev cur ->
            let cur' = moveTail prev cur in (cur', cur')
        )
        chainHead'
        rest
hs

← Previous Back to AoC Index Next →