Google Code Jam/The Price is Wrong

From HaskellWiki
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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