import Data.Ratio
import qualified Data.Set as S
import qualified Data.Map.Strict as M
--- import Data.Map.Strict ((!))
-import Linear (V2(..), (^+^), (^-^), (*^), (*^))
+import Linear (V2(..), (^+^), (*^))
import Linear.Metric (norm)
import Data.List
import Data.Ord
-
-type Bounds = (Int, Int)
-type Position = V2 Int
-type Delta = V2 (Ratio Int)
+type Bounds = (Integer, Integer)
+type Position = V2 Rational
type Asteroids = S.Set Position
-type TargetInfo = (Float, Float)
+type TargetInfo = (Double, Double)
type Targets = M.Map TargetInfo Position
main :: IO ()
print $ part2 targets
-part2 targets = 100 * x + y
+part2 targets = numerator $ 100 * x + y
where V2 x y = (targetSequence targets)!!199
bestVisible :: Bounds -> Asteroids -> (Position, Int)
-bestVisible bounds asteroids = maximumBy (comparing snd) $ S.toList $ S.map (visibleCount bounds asteroids) asteroids
+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)
| 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)
- startR = V2 (tx % 1) (ty % 1)
- rawScreens = takeWhile (inBounds bounds) [startR ^+^ n *^ delta | n <- [1..]]
- screens = filter isIntegral rawScreens
- screenInteger = map integerVec screens
- fullScreened = S.fromList screenInteger
- screened = S.delete target fullScreened
-
-inBounds :: Bounds -> Delta -> Bool
-inBounds (maxX, maxY) (V2 x y) = (x >= 0) && (x <= (maxX % 1)) && (y >= 0) && (y <= (maxY % 1))
+ delta = V2 ((tx - ox) / maxComponent) ((ty - oy) / maxComponent)
+ rawScreens = takeWhile (inBounds bounds) [target ^+^ n *^ delta | n <- [1..]]
+ screened = S.fromList rawScreens
-integerVec :: Delta -> Position
-integerVec (V2 x y) = V2 (numerator x) (numerator y)
+inBounds :: Bounds -> Position -> Bool
+inBounds (maxX, maxY) (V2 x y) = (x >= 0) && (x <= (maxX % 1)) && (y >= 0) && (y <= (maxY % 1))
-isIntegral :: Delta -> Bool
-isIntegral (V2 x y) = (denominator x == 1) && (denominator y == 1)
makeTargets :: Position -> Asteroids -> Targets
targetInfo :: Position -> Position -> TargetInfo
targetInfo origin target = (angle, range)
where V2 dx dy = target - origin
- angle = atan2 (fromIntegral dy) (fromIntegral dx)
+ angle = atan2 (fromRational dy) (fromRational dx)
-- recipRange = 1 / (norm (V2 (fromIntegral dy) (fromIntegral dx)))
- range = norm (V2 (fromIntegral dy) (fromIntegral dx))
+ range = norm (V2 (fromRational dy) (fromRational dx))
-possibleTargets :: Float -> Targets -> Targets
-possibleTargets angle targets = M.filterWithKey (\(a, _) _ -> a > angle) targets
-
-firstTarget :: Targets -> (TargetInfo, Position)
-firstTarget targets = M.findMin targets
+targetSequence :: Targets -> [Position]
targetSequence targets = targetNext ((- pi / 2) - 0.001) targets
-targetNext :: Float -> Targets -> [Position]
+targetNext :: Double -> Targets -> [Position]
targetNext angle targets
| M.null targets = []
| M.null possibles = targetNext (- pi) targets
targets' = M.delete (targetAngle, targetRange) targets
angle' = targetAngle
+possibleTargets :: Double -> Targets -> Targets
+possibleTargets angle targets = M.filterWithKey (\(a, _) _ -> a > angle) targets
+
+firstTarget :: Targets -> (TargetInfo, Position)
+firstTarget targets = M.findMin targets
+
successfulParse :: String -> (Asteroids, Bounds)
-successfulParse input = ( S.fromList [(V2 x y) | x <- [0..maxX], y <- [0..maxY]
+successfulParse input = ( S.fromList [(V2 (fromIntegral x % 1) (fromIntegral y % 1)) | x <- [0..maxX], y <- [0..maxY]
, isAsteroid x y
]
- , (maxX, maxY)
+ , (fromIntegral maxX, fromIntegral maxY)
)
where grid = lines input
maxX = (length $ head grid) - 1