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.