# euler 31 coin combinations and over engineering

Feb 22, 2015

I had this one all wrong, and made it way more complex than it really was. I’m embarassed to post the final code … but it is what it is.

``````import Data.Maybe

-- Basic idea is something like this:
-- [*] given amount and some coins, pick the largest coin
-- [*] there are (floor (total/coin)) ways of using this coin value
-- [*] but ... NOT ALL of these count! Only the ones that leave a total that can be used with the remaining coins!

coins = [1, 2, 5, 10, 20, 50, 100, 200]

sortedCoins :: [Int]
sortedCoins = L.reverse \$ L.sort \$ coins

combinations :: Int -> [Int] -> Maybe Int
combinations total coins =
--  T.trace ("total = " ++ show total ++ ", coins = " ++ show coins) \$
if total == 0
then Just 1
else case coins of
[] -> Nothing
[c] -> if mod total c == 0 then Just 1 else Nothing
c:cs -> if total == 0
then Just 1
else let newTotal total coin num = total - (coin * num)
combs = [combinations (newTotal total c num) cs | num <- [0 .. div total c]]
counts = sum \$ catMaybes combs
in
if counts == 0 then Nothing else Just counts

euler31 :: Int
euler31 = fromJust \$ combinations 200 sortedCoins
``````

It turns out, I was being overly cautious and could have just used lists in a different way (left in a commented out debug line to show that I needed it).