Euler problems/191 to 200
Jump to navigation
Jump to search
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
award 1 = 3
award 15 = 107236
award k = award (k-1) -- + O
+ hasM_LsAndEndsInN_As 0 2 (k-1) -- + L
+ hasM_LsAndEndsInN_As 0 1 (k-1) -- + L
+ hasM_LsAndEndsInN_As 0 0 (k-1) -- + L
+ hasM_LsAndEndsInN_As 0 1 (k-1) -- + A
+ hasM_LsAndEndsInN_As 1 1 (k-1) -- + A
+ hasM_LsAndEndsInN_As 0 0 (k-1) -- + A
+ hasM_LsAndEndsInN_As 1 0 (k-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
-- Count awards of length k that have "m" L's in them, and end in "n" A's
hasM_LsAndEndsInN_As m n k
| m < 0 || n < 0 = 0
| n == 0 = hasM_LsAndEndsInN_As (m-1) 0 (k-1) -- + L
+ hasM_LsAndEndsInN_As (m-1) 1 (k-1) -- + L
+ hasM_LsAndEndsInN_As (m-1) 2 (k-1) -- + L
+ hasM_LsAndEndsInN_As m 0 (k-1) -- + O
+ hasM_LsAndEndsInN_As m 1 (k-1) -- + O
+ hasM_LsAndEndsInN_As m 2 (k-1) -- + O
| n > 0 = hasM_LsAndEndsInN_As m (n-1) (k-1) -- + A
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]]