Skip to content

@duncanmortimer /themepark.hs
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.