From fffef3e49db9f65cae3f0f99703ba01ae0d008bf Mon Sep 17 00:00:00 2001
From: Joe Zhao <ztuowen@gmail.com>
Date: Thu, 28 Jan 2016 09:56:24 -0700
Subject: init

---
 change.hs | 11 +++++++++++
 1 file changed, 11 insertions(+)
 create mode 100644 change.hs

(limited to 'change.hs')

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)
-- 
cgit v1.2.3-70-g09d2