Instantly share code, notes, and snippets.

# duncanmortimer/themepark.hs Created Jan 22, 2011

What would you like to do?
This version memoizes the calculation by determining the sequences of "ride sizes" (i.e. number of people on the rollercoaster in subsequent rides) obtained starting at different positions in the queue. This speeds things up in two ways: (a) we only need
 module Main where import Text.Printf -- Processing profit :: Integer -> Integer -> [Integer] -> Integer profit r cap gs | sum gs <= cap = r * (sum gs) | otherwise = sum \$ take (fromIntegral r) \$ rideSizes 0 where rideSizes :: Int -> [Integer] rideSizes = (map calcRideSequence [0..] !!) numGroups :: Int numGroups = length gs calcRideSequence :: Int -> [Integer] calcRideSequence n = let (peopleOnRide, groupsOnRide) = nextLoad (drop n \$ cycle gs) in peopleOnRide : rideSizes ((n + groupsOnRide) `mod` numGroups) nextLoad :: [Integer] -> (Integer, Int) nextLoad q = nl q 0 0 where nl :: [Integer] -> Integer -> Int -> (Integer, Int) nl [] s n = (s, n) nl (x:xs) m n | m+x <= cap = nl xs (m+x) (n+1) | otherwise = (m, n) -- Parsing and output processInput :: String -> [String] processInput s = zipWith (printf "Case #%d: %d") ([1..] :: [Integer]) profits where cases = map (map read . words) . drop 1 . lines \$ s profits = chop processCase cases processCase :: [[Integer]] -> (Integer, [[Integer]]) processCase ([numRuns, coasterSize, _] : groups : rest) = (profit numRuns coasterSize groups, rest) processCase _ = error "invalid input" chop :: ([a] -> (b, [a])) -> [a] -> [b] chop _ [] = [] chop f as = b : chop f as' where (b, as') = f as main :: IO () main = interact (unlines . processInput)