Difference between revisions of "Google Code Jam/The Price is Wrong"

From HaskellWiki
Jump to navigation Jump to search
 
m (Formatting corrected)
 
Line 1: Line 1:
<hask>
+
<haskell>
 
import Data.List
 
import Data.List
 
import Data.Function
 
import Data.Function
Line 34: Line 34:
 
putStrLn . unwords . map fst . head . sort . map (sort . map r) . sol $ n
 
putStrLn . unwords . map fst . head . sort . map (sort . map r) . sol $ n
 
 
</hask>
+
</haskell>

Latest revision as of 22:56, 5 April 2021

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