GCJ B - Cookie Clicker Alpha


Another problem from This year’s Google Code Jam.

The gist of the problem is to work out whether buying additional capacity for cookie production would result is reaching the quota faster than not buying additional capacity.

Haskell is suited to this for a couple of reasons. Firstly, its’ easy to work with infinite lists. so I can create list of the cumulative times for creating factories and reaching the target. And to calculate the cumulative target I’m using the scanl1 function to turn the infinite list of factory times into an infinite list of partial sums. I’m using scanl1 because it starts at 0, which is important as one of the gotcha’s with this is that it may be faster to just generate cookies rather than buying a factory in the first instance.

Secondly, pattern matching. With the infinite list I’m stopping when the time to reach the target starts growing again. Pattern matching makes this very easy to do.

module Main where

import Control.Monad
import Numeric

-- https://code.google.com/codejam/contest/dashboard?c=2974486#s=p1
-- Input and output with standard redirection operators

factoryTimes :: Double -> Double -> [Double]
factoryTimes c f = 0.0 : [ c / (2.0 + k * f) | k <- [0.0, 1.0 ..]]

productionTimes :: Double -> Double -> [Double]
productionTimes x f = [ x / (2.0 + k * f) | k <- [0.0, 1.0 ..]]

times :: Double -> Double -> Double -> [Double]
times c f x = zipWith (+) production factory
  where production = productionTimes x f
        factory = scanl1 (+) $ factoryTimes c f

firstMinimum :: [Double] -> Double
firstMinimum (x:y:ys) = if x < y
                        then x
                        else firstMinimum (y:ys)

solve :: Double -> Double -> Double -> Double
solve c f x = firstMinimum $ times c f x

main :: IO ()
main = do
  t <- getLine
  forM_ [1..read t :: Int] $ \i -> do
    [c, f, x] <- fmap (map read . words) getLine
    let result = solve c f x
    putStrLn $ concat ["Case #", show i, ": ", Numeric.showFFloat (Just 7) result ""]