[Haskell-beginners] Recursion/dynamic programming optimization

[Magnus Therning]

On 19/03/10 20:41, ivovnenko wrote:
> Hi.
> I tried to solve one of the google code jam's problems using haskel
> http://code.google.com/codejam/contest/dashboard?c=90101#s=p2:
> 
> w :: Eq a => [a] -> [a] -> Int
> w text str = w' (reverse text) (reverse str)
> w' :: Eq a => [a] -> [a] -> Int
> -- Init
> w' _ [] = 0
> w' [] _ = 0
> -- For one symbol string
> w' text [a] =
>         if head text == a then
>                 w' (tail text) [a] +1
>         else
>                 w' (tail text) [a]
> -- General case
> w' text str =
>         if head str == head text then
>                 w' (tail text) (tail str) + w' (tail text) str
>         else
>                 w' (tail text) str
> 
> and it worked great on small inputs, not on large:

I suspect that a change of type for w' would improve things a bit.  The base
cases:

w' n [] _ = n
w' n _ [] = n
w' n (t:ts) [a] =
    if t == a
        then w' (succ n) ts [a]
        else w' n ts [a]

After reading the problem description though I think that thinking hard about
the problem might reveal that there's a more clever way to solve it instead of
the rather brute-force route you've taken so far.

/M

-- 
Magnus Therning                        (OpenPGP: 0xAB4DFBA4)
magnus＠therning．org          Jabber: magnus＠therning．org
http://therning.org/magnus         identi.ca|twitter: magthe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/beginners/attachments/20100320/d980c083/signature.bin