Using just rationals for part 1.

[advent-of-code-19.git] / advent10 / src / advent10.hs

diff --git a/advent10/src/advent10.hs b/advent10/src/advent10.hs
index 95c02870fec114a547d37631cdd4c154f14a0fb8..ba90ba1429788b160e2b4aaaa95eeb7b03075b7f 100644 (file)
--- a/advent10/src/advent10.hs
+++ b/advent10/src/advent10.hs
@@ -1,17 +1,14 @@
 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
 
@@ -30,12 +27,14 @@ main = do
         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)
@@ -53,22 +52,13 @@ 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)
-          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
@@ -78,16 +68,12 @@ makeTargets origin asteroids = S.foldl' addTarget M.empty asteroids
 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]
@@ -100,12 +86,18 @@ targetNext angle targets
           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
+
 
 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