# 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
, _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.