This problem involves an arbitrary number of dice with each an arbitrary number of sides. We then find the maximal number of dice that can be put in a straight, see Google's Code Jam explanation. I've been trying to solve the problem in Haskell and I think the following solution works algorithmically. However, it is not fast enough to earn full points on the problem, so can this be optimized?

import Data.List (sort)

getMaxStraight :: [Int] -> Int
getMaxStraight sides =
  foldl
    (\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
    0
    (sort sides)

Aside from this, I've also written a Python solution which did run in time. What is going on?

def solve(sides)
    sides = sorted(sides)
    max_straight = 0
    for side in sides:
        if side > max_straight:
            max_straight  = 1
    return max_straight

Edit: This post has been "reverted" to an older version. A newer version of the post can be found here

CodePudding user response：

What you are here doing is constructing a large expression tree that will look for a list [1, 2, 3, 4, 5, 6] as:

f (f (f (f (f (f 0 1) 2) 3) 4) 5) 6

with f the lambda expression \maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight. You thus will first create a large expression that will likely take considerable memory, and then evaluate that.

As the documentation on foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b says:

If you want an efficient strict left-fold, you probably want to use foldl' instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain