[Haskell-cafe] Re: xkcd #287 "NP-Complete"

[apfelmus]

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