# Commits

committed 72562d7

solve p31

• Participants
• Parent commits 44b3489
• Branches default

# File euler.hs

`         pow5 = (^ 5) :: Int -> Int`
`         isP x = (sum \$ map pow5 (numsOfInteger x)) == x`
` `
`-p31 = p31' [2, 1] [] 4`
`-    where`
`-        p31' :: [Int] -> [Set (Int, Int)] -> Int -> [Set (Int, Int)]`
`-        p31' xs ss 0 = ss`
`-        p31' [] ss remaining = []`
`-        p31' a@(x:xs) [] remaining`
`-            | x > remaining = p31' xs [Set.fromList [(x,0)]] remaining`
`-            | otherwise = concat . concat \$ filter (not . null) [p31' xs [Set.fromList [(x, i)]] (remaining-x*i) | i <- [0..div remaining x]]`
`-        p31' a@(x:xs) ss remaining = concatMap (\y -> concatMap (\z -> Set.insert (x, y) z) (p31' xs [] (remaining-x*y))) [0..div remaining x]`
`+-- simple method, easy to understand, but a bit of ugly`
`+p31' = length \$ [(a1,a2,a5,a10,a20,a50,a100,a200) | a1 <- [0,1..200], a2 <- [0,2..200-a1], a5 <- [0,5..200-a1-a2], a10 <- [0,10..200-a1-a2-a5], a20 <- [0,20..200-a1-a2-a5-a10], a50 <- [0,50..200-a1-a2-a5-a10-a20], a100 <- [0,100..200-a1-a2-a5-a10-a20-a50], a200 <- [0,200..200-a1-a2-a5-a10-a20-a50-a100], a1+a2+a5+a10+a20+a50+a100+a200==200]`
`+`
`+count :: [Int] -> Int-> Int`
`+count _ 0      = 1`
`+count [c] _    = 1`
`+count (c:cs) s = sum \$ map (count cs . (s-)) [0,c..s]`
`+`
`+-- get all combination ways of the coins, slower than count`
`+count' :: [Int] -> Int-> [Set (Int, Int)]`
`+count' [] 0     = []`
`+count' cs 0     = [Set.fromList [(i, 0) | i <- cs]]`
`+count' [1] s    = [Set.fromList [(1, s)]]`
`+count' (c:cs) s = concatMap (\x -> map (\y -> Set.insert (c, div x c) y) (count' cs (s-x))) [0,c..s]`
`+`
`+p31 = count [200, 100, 50, 20, 10, 5, 2, 1] 200`
` `
` -- solutions end`
` `

# File euler.py

`     print('Sum: ', _sum)`
` `
` if __name__ == '__main__':`
`-	print(p28())`
`+	print(p31())`
` 	print("Seconds:", time.clock() - start)`