View source for Euler problems/191 to 200

== [http://projecteuler.net/index.php?section=problems&id=191 Problem 191] ==
Prize Strings

A couple of notes.  I was too lazy to memoize this, so I just
ran it twice, once with 15 and then again with 30.  I pasted the
output of the 15 run into the code.  The way to get a handle on
this is to just case it out.  Ask yourself what can I add to
award (n-1) to generate award (n).  You can add an O to the end
of all of award (n-1).  You can add an L to any award (n-1) that
doesn't contain an L, and you can add an A to award (n-1)
provided it doesn't end with two A's.  So the function
hasM_LsAndEndsInN_As is just what is needed to cover all of the
cases.  Henry Laxen April 29, 2008

<haskell>
award 1 = 3
award 15 = 107236
award k = award (k-1) -- + O
    + sum [ hasM_LsAndEndsInN_As 0 i (k-1) | i<-[0..2] ] -- +L
    + sum [ hasM_LsAndEndsInN_As i j (k-1) | i<-[0,1], j<-[0,1] ] -- +A


hasM_LsAndEndsInN_As 0 0 1 = 1  -- O
hasM_LsAndEndsInN_As 1 0 1 = 1  -- L
hasM_LsAndEndsInN_As 0 1 1 = 1  -- A
hasM_LsAndEndsInN_As _ _ 1 = 0

hasM_LsAndEndsInN_As 0 0 15 = 5768
hasM_LsAndEndsInN_As 0 1 15 = 3136
hasM_LsAndEndsInN_As 0 2 15 = 1705
hasM_LsAndEndsInN_As 1 0 15 = 54736
hasM_LsAndEndsInN_As 1 1 15 = 27820
hasM_LsAndEndsInN_As 1 2 15 = 14071

hasM_LsAndEndsInN_As m n k 
  | m < 0 || n < 0 = 0
  | n == 0 = sum [ hasM_LsAndEndsInN_As (m-1) i (k-1) | i<-[0..2]] -- +L
           + sum [ hasM_LsAndEndsInN_As m     i (k-1) | i<-[0..2]] -- +O
  | n 0 = hasM_LsAndEndsInN_As m (n-1) (k-1) -- + A
-- Count awards of length k that have "m" L's in them, and end in "n" A's

problem191 n = do
  let p a b c d  = "hasM_LsAndEndsInN_As " ++
                    foldl (\x y -> x ++ (show y) ++ " ") "" [a,b,c] ++
                    "= " ++ (show d)
  putStrLn $ "award " ++ (show n) ++ " = " ++ show (award n)
  mapM_ (\(i,j) -> putStrLn $ p i j n (hasM_LsAndEndsInN_As i j n))
        [ (i,j) | i<-[0..1], j<-[0..2]]
    
</haskell>
A brief tutorial on solving this problem is available [http://maztravel.com/haskell/euler_problem_191.html here]