Project Euler Problem 158 - Solved

You can find the statement of this problem here.

As in many of the posts you can find here, the solution for this problem is using DP.

I used a top-down approach with memoization. The DP dictionary will be indexed by three things: length, number of numbers which are greater than the previous and the number of times that the a[i] < a[i+1].

The base cases are:

• (0, 0, 0) = 0: Meaning we finished choosing the strings but no a[i] < a[i+1] so its not valid.
• (0, 0, 1) = 1: Meaning we finished choosing the strings and there's only one occurrence where a[i] < a[i+1] so its valid and there's only one possibility.
• (,,2) = 0: Any case where there is more than one occurrence where a[i] > a[i+1] is not valid so 0 is returned.

In my python code I implemented a method get_num that receives the 3 indexes.
It first checks if the result is in the dp dictionary, in that case returns the saved value; if the 3rd index is greater than 1 it returns 0. If none applies it calls recursively for each case that we could pick from, adds them all up and stores the value for not recalculating it.

It is important to notice that we don't need to take the 26 possible characters to calculate the different number of ways of generating different strings of length x. We just calculate from the base that we have x characters and then multiply the result by the number of combinations we can take x from 26.

The Python code can be downloaded problem158.py:

factorial = {0:1}
for i in range(1, 27):
    factorial[i] = factorial[i-1] * i

dp = {
    (0, 0, 0) : 0,
    (0, 0, 1) : 1
}
def get_num(*args):
    if args in dp:
        return dp[args]

    length, num_greater, count = args
    if count > 1:
        return 0
    result = sum(get_num(length-1, i, count + ((i < num_greater) and 1 or 0)) for i in range(length))
    dp[args] = result
    return result

p = lambda n: sum(get_num(n-1, i, 0) for i in range(n)) * (factorial[26] // (factorial[n] * factorial[26 - n]))

if __name__ == '__main__':
    max_pn, max_n = max((p(n), n) for n in range(2, 27))
    print("The result is:", max_pn, "found at n:", max_n)

And the equivalent in Haskell problem158.hs:

import Data.Map
import Data.Maybe

factorial n = factorial' n 1
    where
        factorial' n res
            | n < 2 = res
            | n >= 2 = factorial' (n-1) (res * n)

comb x y = ((factorial x) `div` ((factorial y) * (factorial (x-y))))

getValue :: (Integer, Integer, Integer) -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer )
getValue (length, greater, count) dp
    | count > 1 = (0, dp)
    | member (length, greater, count) dp = (fromJust (Data.Map.lookup (length, greater, count) dp), dp)
    | notMember (length, greater, count) dp = getValue' (length, greater, count) dp 0 0
        where
            getValue' (length, greater, count) dp i res
                | i == length = (res, insert (length, greater, count) res dp)
                | i < length = getValue' (length, greater, count) nDp (i+1) (res + nRes)
                where
                    nCount = if i < greater then count+1 else count
                    (nRes, upDp) = getValue ((length -1), i, nCount) dp
                    nDp = insert ((length -1), i, nCount) nRes dp

p :: Integer -> Map (Integer, Integer, Integer) Integer -> (Integer, Map (Integer, Integer, Integer) Integer)
p n dp = p' 0 dp 0
    where
        p' x dp res 
            | x == n = (res * (comb 26 n), dp)         
            | x < n  = p' (x + 1) nDp (res + nRes)
            where
                (nRes, nDp) = getValue ((n-1), x, 0) dp

initialDp = fromList [((0,0,0), 0), ((0,0,1), 1)]

main = print ("The result is: " ++ (show (first (foldl f (0, initialDp) [1..26]))))
    where
        first (x, y) = x
        f (r, dp) n = 
            let
                (nRes, nDp) = p n dp
                maxR = max r nRes
            in
                (maxR, nDp)