amazon.hs (1504B)
1 import Control.Monad 2 import System.Random.MWC 3 import Test.QuickCheck 4 5 import Data.Map.Strict (empty, insert, deleteMax, findMax, size, toList) 6 7 distanceToNull :: Num a => (a, a) -> a 8 distanceToNull (x, y) = x^2 + y^2 9 10 smallestHundred :: (Num a, Ord a) => [(a, a)] -> [(a, a)] 11 smallestHundred xs = findSmallest xs empty where 12 findSmallest [] m = map fst . toList $ m 13 findSmallest (x:xs) m = case compare (size m) 100 of 14 GT -> error "you done fucked up" 15 LT -> findSmallest xs (insert x (distanceToNull x) m) 16 EQ -> if distanceToNull x >= snd (findMax m) 17 then findSmallest xs m 18 else findSmallest xs (insert x (distanceToNull x) $ deleteMax m) 19 20 -- Tests ----------------------------------------------------------------------- 21 22 prop_smallestHundredAreSmallest :: [(Double, Double)] -> Bool 23 prop_smallestHundredAreSmallest xs = 24 all (\x -> if x `notElem` sh then all (<= x) sh else True) xs 25 where sh = smallestHundred xs 26 27 prop_smallestHundredAreMaxHundred :: [(Double, Double)] -> Bool 28 prop_smallestHundredAreMaxHundred xs = length sh <= 100 29 where sh = smallestHundred xs 30 31 main = do 32 -- QuickCheck stuff 33 quickCheck prop_smallestHundredAreMaxHundred 34 quickCheck prop_smallestHundredAreSmallest 35 36 -- Unit test 37 g <- create 38 z0s <- replicateM 1000000 (uniformR (-1000, 1000) g) :: IO [Int] 39 z1s <- replicateM 1000000 (uniformR (-1000, 1000) g) :: IO [Int] 40 41 print $ smallestHundred (zip z0s z1s) 42