Day 10 involved lots of fiddling around with numbers, me getting very confused, and the odd diagram of which way was up.
Part 1
This involved some different data types. Screened locations were only on exact grid points. To keep the precision of exact points, I could use rational numbers to represent points (and screened points). I used the V2 Rational vector type to represent an asteroid, and a Set of them to represent the whole field.
To find the best site, I have to find the number of visible asteroids at each possible site. This returns both the best site and the number of visible asteroids.
bestVisible :: Bounds -> Asteroids -> (Position, Int)
bestVisible bounds asteroids = maximumBy (comparing snd)
$ S.toList
$ S.map (visibleCount bounds asteroids) asteroids
visibleCount :: Bounds -> Asteroids -> Position -> (Position, Int)
visibleCount bounds asteroids origin = (origin, S.size $ visible bounds origin asteroids)
To find the visible asteroids from a site, I find all the points that are screened by the asteroids, and remove them from the set of all asteroids: what remains is just the set of visible asteroids.
visible :: Bounds -> Position -> Asteroids -> Asteroids
visible bounds origin asteroids = S.delete origin $ S.difference asteroids screened
where screened = allScreenings bounds origin asteroids
The set of all the screened points, is just the union of the sets of points screened by each asteroid.
allScreenings :: Bounds -> Position -> Asteroids -> Asteroids
allScreenings bounds origin asteroids = S.foldl' (screenings bounds origin) S.empty asteroids
screenings does the work. I only have to worry about screened points that line up on grid points. That means that if an asteroid is five units left and two units below the origin, the interesting screened points are 10 left and 4 below, 15 left and 6 below, and so on. But if an asteroid is four units left and two units below, the interesting screened points are 6 left and 3 below, 8 left and 4 below, 10 left and 6 below, and so on.
But rather than thinking about common factors of the steps left and down, I can just take one step left and two fifths of a step down (in the 5, 2 case), or one step left and half a step down (in the 4, 2 case). This will generate more screened points than could possibly line up with asteroids, but as all I'm doing is finding the intersection between these screened points and the asteroids, I'll get the same answer anyway.
That's what screenings does. It finds the difference between the origin and the target, and then finds the largest component of that step. It uses that to scale the delta to be one step in that direction, and whatever fraction of a step in the other direction. It then just applies multiples of that delta beyond the target, until it reaches the edge of the asteroid field.
screenings :: Bounds -> Position -> Asteroids -> Position -> Asteroids
screenings bounds origin@(V2 ox oy) screened0 target@(V2 tx ty)
| origin == target = screened0
| otherwise = S.union screened0 screened
where maxComponent = max (abs (tx - ox)) (abs (ty - oy))
delta = V2 ((tx - ox) / maxComponent) ((ty - oy) / maxComponent)
rawScreens = takeWhile (inBounds bounds) [target ^+^ n *^ delta | n <- [1..]]
screened = S.fromList rawScreens
inBounds :: Bounds -> Position -> Bool
inBounds (maxX, maxY) (V2 x y) = (x >= 0) && (x <= (maxX % 1)) && (y >= 0) && (y <= (maxY % 1))
There is also some faffing around with fromIntegral calls in the datafile reading code, to convert the machine-sized Int values to the arbitrary-sized Integer values needed in the rest of the program.
Part 2
At this point, all the niceties of rational numbers disappeared. I did start by trying that route, having a virtual asteroid tracking around the perimeter of the field and the laser cannon pointing at it. But that missed some asteroids, so I dropped down into dirty Float real numbers.
I created a Map of targetting information, one element per asteroid. The value was the position of asteroid; the key was a pair (2-tuple) of its angular position (relative to the monitor satellite) and its distance. (I somehow managed to have the angle increasing clockwise; not what I was expecting.)
makeTargets :: Position -> Asteroids -> Targets
makeTargets origin asteroids = S.foldl' addTarget M.empty asteroids
where addTarget m t = M.insert (targetInfo origin t) t m
targetInfo :: Position -> Position -> TargetInfo
targetInfo origin target = (angle, range)
where V2 dx dy = target - origin
angle = atan2 (fromRational dy) (fromRational dx)
range = norm (V2 (fromRational dy) (fromRational dx))
The targetting information was used with the current angle of laser. The next target is the asteroid with the smallest angle larger than the laser's angle; if there are several such targets, the laser shoots the nearest asteroid. As tuples order on first term then second term, sorting by the (angle, distance) pair sorts the asteroids in the correct targetting order.
possibleTargets finds all the targets clockwise of the laser's angle. firstTarget finds the first such target. targetNext handles the destruction of an asteroid, and updates the laser's angle to that of the just-destroyed asteroid. It also handles the branch cut situation where there are no more targets between the laser and the angle π radians; in that case, the angle is reset to -π radians and the zapping continues.
targetSequence :: Targets -> [Position]
targetSequence targets = targetNext ((- pi / 2) - 0.001) targets
targetNext :: Float -> Targets -> [Position]
targetNext angle targets
| M.null targets = []
| M.null possibles = targetNext (- pi) targets
| otherwise = (target:(targetNext angle' targets'))
where possibles = possibleTargets angle targets
((targetAngle, targetRange), target) = firstTarget possibles
targets' = M.delete (targetAngle, targetRange) targets
angle' = targetAngle
possibleTargets :: Float -> Targets -> Targets
possibleTargets angle targets = M.filterWithKey (\(a, _) _ -> a > angle) targets
firstTarget :: Targets -> (TargetInfo, Position)
firstTarget targets = M.findMin targets
Debugging
All of that description sounds very simple and straightforward, but I managed to tie myself into several knots along the way. The angular positions weren't doing what I expected, and I once had a situation where an asteroid was shielding asteroids closer than it as well as those further away.
The showPattern function was helpful, generating a little map of interesting points. I used that to compare what my program thought was happening with what the AoC examples were showing.
Code
The code is available here, and on Github. There's also an earlier version, which uses V2 Int to store the asteroid locations, and then does some fiddling around inside screenings to covert the Int to Rational and back again.