Well, drat... *spoiler alert*

I didn't do well in the qualifying round of Code Jam this year, alas. Part of it I can thank the IRS for, in a way, because we paid our annual last-minute visit to H&R Block today. But really it's my fault; I didn't arrange to have the interval during which one could enter solutions clear to devote to it.

I didn't get my improved version of Cookie Clicker Alpha done in time to count, but it did check out, so I have a moral victory at least. I probably should have devoted the time needed to do the simplest of the qualifying problems, Magic Trick, rather than just sketching out the solution.

A quick summary of the problem: in the problem's version of the game "Cookie Clicker" (inspired by a real game of that name) is parametrized by three values:

• X, a goal number of cookies to accumulate
• C, the cost in cookies of a "cookie farm"
• F, the rate at which one can "harvest" cookies from a cookie farm once bought

OK, actually, there's a fourth value: if you click on a giant cookie, you can gain two cookies/second. (You have to have a way to get started accumulating cookies, or you couldn't buy a cookie farm.)

One thing to note: in real life, cookies are discrete entities; a whole cookie is either there or not. In this problem, though, you should think of cookies as being produced continuously; for example, with no farms, you can lay claim to two thirds of a cookie in a third of a second.

So, the problem as posed: given X, C, and F, figure out the soonest you can accumulate the goal of X cookies. Of course, cookies you spend on farms don't count towards X, though of course it will usually pay off to buy farms. (Not necessarily, though! If X < C, best to just click away.)

As usual for Code Jam, the input is a line with the number of cases of the problem to solve, followed by lines with the data for the cases. For this one, it's one line per case, with C, F, and X (which are "real" numbers) on the line in that order, separated by spaces. The output format? You should know by now:

Case #<number>: <time>

where <time> is the minimum time to get X cookies with the given cost and rate per cookie farm.

Magic Trick is simple enough that you don't have to worry about optimization the way you do for problems like Fair and Square last year... but Cookie Clicker has two inputs to try, and my initial solution was far too slow to handle the larger input within the time limit.

Spoilers behind the break...

So here's the first solution. Apologies for not using X, C, and F to match the problem description the way I did for Fair and Square, but I like clarity. 

localMin :: Ord a => [a] -> a

localMin (x1:rest@(x2:xs)) = if x1 < x2 then x1 else localMin rest

cookieTime :: [Double] -> Double

cookieTime [farmCost, farmRate, goal] = localMin $ map (timeToGoal goal) [0..]

  where 

        clickRate              = 2.0

        cookieRate nFarms      = fromIntegral nFarms * farmRate + clickRate

        timeToGetFarm n        = farmCost / (cookieRate (n - 1))

        timeToAccumulate       = scanl (+) 0 $ map timeToGetFarm [1..]

        timeToGoal goal nFarms = goal / (cookieRate nFarms) + (timeToAccumulate !! nFarms)

        

-- The canonical Google Code Jam output prefix...

caseHeaders = map (\n -> "Case #" ++ show n ++ ": ") [1..]

        

parseLine :: String -> [Double]

parseLine s = map read (words s)

                

main = do

         s <- getContents

         let cases = map parseLine (tail (lines s))

         let output = zipWith (++) caseHeaders $ map (show . cookieTime) cases

         putStr $ unlines output

Pretty well straight from the definition, and fine for the first input--but too slow for the second.

To speed it up, the thing to look at is the difference between cookieRate nFarms and cookieRate (nFarms + 1). You add the time to get the (nFarms + 1)^th farm, but then you can produce the cookies with one more farm, so that time decreases. When the difference becomes non-negative, you have your answer. The I/O scaffolding remains the same, so we'll just show the new cookieTime function, which doesn't need the support of localMin.

cookieTime [farmCost, farmRate, goal] = noFarmTime + sum (takeWhile (< 0) deltas)
  where
     clickRate         = 2.0
     noFarmTime        = goal / clickRate
     cookieRate nFarms = fromIntegral nFarms * farmRate + clickRate
     deltas            = map delta [1..]
     delta n           = farmCost / cookieRate (nFarms - 1)
                           + goal / cookieRate nFarms
                           - goal / cookieRate (nFarms - 1)

With that change, it handles the larger input without breaking a sweat. One caveat: if you compare the outputs of the two versions, you will see some differences down in the least significant digits. The Code Jam checker is happy with a value good to "within an absolute or relative error of 10^-6", so we are safe for the inputs provided, at least.

UPDATE: One should point out why the above does find the best time.

• If you're going to buy any farms, clearly you should spend all your cookie accumulating time, as opposed to getting cookies to buy farms, at the end--any cookie accumulating time with fewer farms is a loss compared with accumulating with all the farms you're going to have.
• If we could prove that the deltas are monotonically increasing, that would be sufficient, but I doubt that's true. OTOH, it isn't necessary. The important thing is that the total eventually become monotonically increasing--but I'm not sure I can prove that. The two terms contributing to delta, i.e. the cost of buying another farm and the difference in the time to achieve the goal, individually tend to zero as the number of farms increases without bound.

What we have works at least for the sample inputs, but it will take some more investigation to convince ourselves that it will always work (barring overflow, of course).

UPDATE: there is a bit more optimization one could do, because we evaluate cookieRate 0 twice, cookieRate n twice for n one greater than the optimal number of farms, and three times for the values in between. OTOH, as is it chugged through the larger input so quickly that one would only do it for practice.

UPDATE: Even better, check out the analysis on Mathematics Stack Exchange.