Tom Pledger wrote: > We've seen some nice concise solutions that can deal with the original > problem: > > solve 1505 [215, 275, 335, 355, 420, 580] > > I'll be a nuisance and bring up this case: > > solve 150005 [2, 4, 150001] > > A more scalable solution is to use an explicit heap that brings together > all the ways to get to each partial sum. I coded one using Data.Map, > but it's a bit long-winded and ugly.
How about import Data.Map as Map xkcd purse xs = foldl' (flip add) (Map.fromList [(0,[])]) xs ! purse where add price = Map.unionsWith (++) . take (purse `div` price + 1) . iterate (additem price) additem price = Map.map (map (price:)) . Map.mapMaybeWithKey clip . Map.mapKeysMonotonic (price +) clip cost x = if cost <= purse then Just x else Nothing Regards, apfelmus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe