public
Last active

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

  • Download Gist
themepark.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.