init

1 files changed, 11 insertions, 0 deletions

diff --git a/change.hs b/change.hs
new file mode 100644
index 0000000..ffbbdde
--- /dev/null
+++ b/change.hs
@@ -0,0 +1,11 @@
+change [] n = if n == 0 then 1 else 0
+change (x:xs) n = foldl (+) 0 $ map ((change xs).(n-)) avail
+    where avail = takeWhile (<=n) $ map (x*) [0..]
+
+change' xs n = (foldl (flip $ (+).fst) 0).head.(drop n) $ [(1,0)]:changeIter [[(1,0)]]
+    where changeIter hist = h:(changeIter (h:hist))
+            where h = [ (foldl (+) 0 $ [m |(m,low)<-getH x,low<=x],x) |x<-xs]
+                  getH x = let left=drop (x-1) hist in 
+                    if left/=[] then head left else []
+
+main = putStrLn (show $ change' [25,10,5,1] 100000000)