Advent of Code 2021 day 17

Day 17 was a much cleaner and neater solution than the previous few days. I based this around the inRange function from Data.Ix and the Ix class, and using the fact that V2 is a member of that class.

The probe simulation was direct translation of the problem description (and using lenses again). step does one step of the simulation.

type Coord = V2 Int
type Bounds = (Coord, Coord)

data Probe = Probe {_pos :: Coord, _vel :: Coord}
  deriving (Show, Eq)
makeLenses ''Probe

step :: Probe -> Probe
step probe = probe & pos .~ (probe ^. pos ^+^ probe ^. vel) & vel .~ vel'
  where V2 vx vy = probe ^. vel
        vel' = V2 (max 0 (vx - 1)) (vy - 1)

A bit of thinking about the problem gave some bounds on the problem. The probe had to stay within the region bounded by x = 0 and the far edge of the target, and the maximum height and the bottom edge of the target. As soon as the probe went outside this area, I could tell whether it hit the target or not.

Therefore, a probe's trajectory is the iteration of steps so long as they're within the viable region. A trajetory hits the target if any position is within the target's bounds.

simulate :: Bounds -> Probe -> [Probe]
simulate viable = takeWhile (within viable) . iterate step

within :: Bounds -> Probe -> Bool
within limits probe = inRange limits (probe ^. pos)

hits :: Bounds -> [Probe] -> Bool
hits target = any (within target)

To count the number of trajectories that hit, I need to find all the sensible starting speeds, simulate them, and see which hit. All that's left is to find the starting trajectories.

The maximum x speed was the distance to the far edge of the target (any faster and the probe overshoots in one step). The maximum y speed is given by the bottom edge of the target. The probe reaches the same speed when it returns to y = 0, and any faster and the probe overshoots the target. I have to account for the probe starting by going up or down.

part2 :: Bounds -> Int
part2 target@(V2 _minXT minYT, V2 maxXT _maxYT) = 
  length $ filter (hits target) trajectories
  where yMax = findYMax target
        viable = (V2 0 minYT, V2 maxXT yMax)
        launches = [Probe {_pos = V2 0 0, _vel = V2 x y} 
                   | x <- [1..maxXT], y <- [minYT..(abs minYT)]
                   ]
        trajectories = map (simulate viable) launches

findYMax :: Bounds -> Int
findYMax (V2 _ y, _) = y' * (y' - 1) `div` 2
  where y' = abs y

Code

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

Advent of Code 2021 day 17

Code

Neil Smith