The problem is to count all possible sub-sequences of "welcome to code jam" in a given input string (and only return the last 4 digits of the count). Here is the link to the problem for reference.
I've implemented a solution in Haskell that worked fine on the examples and small datasets but failed on the large data set. Here is the code:
I'm interested in correctness first. (Am I missing some corner case?) I guess performance can be improved by memoization; and I'd be happy get any other tips on that front too.
w_s is short for welcome_solve: This calculates the total number of sub-sequences.
w_s x  = 0 w_s (x: ) str_xs = length ( filter (\z -> z==x) str_xs ) w_s (x:xs) (str_x:str_xs) = if x==str_x then (w_s xs str_xs) + (w_s (x:xs) str_xs) else w_s (x:xs) str_xs
And here is the code to get the last 4 digits:
getLast4 (w:x:y:z: ) = [w,x,y,z] getLast4 (x:xs) = getLast4 xs format_solve problem | solution < 1000 = getLast4 $ show $ 10000 + solution | otherwise = getLast4 $ show solution where solution = w_s "welcome to code jam" problem
λ> format_solve "format_solve welcome to codejam" "0000" λ> format_solve "wweellccoommee to code qps jam" "0256" λ> format_solve "elcomew elcome to code jam" "0001"