Google Code Jam/The Price is Wrong

From HaskellWiki
< Google Code Jam
Revision as of 07:58, 29 June 2008 by Paolino (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

import Data.List import Data.Function import Data.Ord import Data.Maybe type Price = (String,Int) type Prices = [(String,Int)] -- | finding the longest strings bests :: [[a]] -> [[a]] bests = head . groupBy ((==) `on` length) . sortBy (flip . comparing $ length) -- | longest sequences of possibly nonconsecutive elements (from IRC help) longest xs = bests . foldr (\x bs -> bSW x bs ++ bs) [] $ xs where bSW x bs = bests $ [x] : (map (x:) . filter ((x <=). head) $ bs) -- solutions are the complements of the longest sequences sol xs = map (xs \\) . longest $ xs where parsePrices :: [String] -> Prices parsePrices [x,y] = zip (words x) (map read. words $ y) parseCases :: String -> [Prices] parseCases x = let (n:ts) = lines x in take (read n) . unfoldr (\x -> if null x then Nothing else Just (parsePrices. take 2 $ x, drop 2 x)) $ ts main = do ts <- parseCases `fmap` getContents flip mapM_ (zip [1..] ts) $ \(i,t) -> do putStr $ "Case #" ++ show i ++ ": " let (_,n) = unzip t r x = fromJust . find ((== x) . snd) $ t putStrLn . unwords . map fst . head . sort . map (sort . map r) . sol $ n