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.

    Neil Smith

    Read more posts by this author.