3
\$\begingroup\$

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

Example usage:

λ> format_solve "format_solve welcome to codejam"
"0000"
λ> format_solve "wweellccoommee to code qps jam"
"0256"
λ> format_solve "elcomew elcome to code jam"
"0001"
\$\endgroup\$
3
  • 1
    \$\begingroup\$ LCS should be adaptable to this problem, if you enumerate all LCS's (see this section of the Wikipedia page) and only consider LCS's where the length of the match is equal to the length of `"welcome to code jam". \$\endgroup\$ – Cactus Jan 20 '15 at 12:36
  • \$\begingroup\$ Can you be any more specific about what the failure is? Wrong answer? Takes too long? Some kind of exception? \$\endgroup\$ – Snowbody Apr 7 '15 at 7:58
  • \$\begingroup\$ My bad; It fails with wrong answer. \$\endgroup\$ – GeneralBecos Apr 7 '15 at 16:27
3
\$\begingroup\$

w_s, short for "welcome_solve", is, frankly, a poor name. You're writing a function that counts the number of subsequences. It's not even restricted to operating on strings. Why not call it countSubsequences?

countSubsequences :: Eq a => [a] -> [a] -> Int

Your base cases should be simpler.

countSubsequences [] _ = 1
countSubsequences _ [] = 0

The recursive case is correct, but could be written more clearly with a more idiomatic convention for parameter names, and using guard clauses.

countSubsequences needle@(n:ns) haystack@(h:hs)
  | n == h    = countSubsequences needle hs + countSubsequences ns hs
  | otherwise = countSubsequences needle hs
\$\endgroup\$
1
  • \$\begingroup\$ Hmm.. but it fails on the large dataset. Is there any bug with the logic to get the last 4 digits? \$\endgroup\$ – GeneralBecos Jan 14 '15 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.