Advent of Code 2022 day 9

Day 9 was back to using some familiar favourites: lenses to look inside records, and the V2 type from Linear for points.

Data and parsing

I defined a few data types for representing the problem: a V2 for positions, a Rope record for the rope, and some Directions for the input format. The rope as the head and a list of all the knots; part 1 had just a single knot.

type Position = V2 Int
type Trace = S.Set Position
type Path = [Position]

data Rope = Rope 
  { _headK :: Position
  , _knots :: [Position]
  , _trace :: Trace
  } deriving (Show, Eq)
makeLenses ''Rope

data Direction = U Int | R Int | D Int | L Int
  deriving (Show, Eq, Ord)
  
newRope :: Int -> Rope
newRope n = Rope { _headK = V2 0 0, _knots = replicate n (V2 0 0), _trace = S.singleton (V2 0 0) }

Parsing the input was simple enough. The instructions were expanded into sequences of individual steps, because knots are updated at each step.

pathP = directionP `sepBy` endOfLine
directionP = upP <|> leftP <|> downP <|> rightP
upP    = U <$> ("U " *> decimal)
leftP  = L <$> ("L " *> decimal)
downP  = D <$> ("D " *> decimal)
rightP = R <$> ("R " *> decimal)

expandPath :: [Direction] -> Path
expandPath = concatMap expandStep
  where expandStep (U n) = replicate n (V2  0  1)
        expandStep (L n) = replicate n (V2 -1  0)
        expandStep (D n) = replicate n (V2  0 -1)
        expandStep (R n) = replicate n (V2  1  0)

Expressing the problem

Next was definition of a couple of functions to encode aspects of the problem. manhattan is the Manhattan distance between two points. Two points are touching if they have a Manhattan distance of 1 or less. Finally is the definition of how to move point 1 towards point 2.

manhattan :: Position -> Position -> Int
manhattan p1 p2 = max dx dy
  where V2 dx dy = abs $ p1 ^-^ p2

touching :: Position -> Position -> Bool
touching p1 p2 =  (manhattan p1 p2) <= 1

towards :: Position -> Position -> Position
towards p1 p2 = signum $ p2 ^-^ p1

Solution

And finally, we can move to the solution. The core is the knotStep function which updates the position of a knot, given its current position and the knot ahead of it.

knotStep :: (Position, [Position]) -> Position -> (Position, [Position])
knotStep (h, ks) kt = (kt', (kt':ks)) 
  where kt' = if kt `touching` h
              then kt
              else kt ^+^ (kt `towards` h)

The slightly odd signature is because this is used in a foldl to update all the knots in sequence (in ropeStep), within another foldl to update the rope head with all the defined steps (in ropeSteps).

ropeSteps :: Rope -> Path -> Rope
ropeSteps rope steps = foldl' ropeStep rope steps

ropeStep :: Rope -> Position -> Rope
ropeStep rope step = rope & headK .~ h
                          & knots .~ (reverse kts)
                          & trace %~ S.insert kt
  where h = (rope ^. headK) ^+^ step
        (kt, kts) = foldl' knotStep (h, []) $ rope ^. knots

All that's needed is to initialise the rope with the required number of knots.

part1, part2 :: Path -> Int
part1 steps = S.size $ rope ^. trace
  where rope = ropeSteps (newRope 1) steps

part2 steps = S.size $ rope ^. trace
  where rope = ropeSteps (newRope 9) steps

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.