[Haskell-cafe] xkcd #287 "NP-Complete"
Tom Pledger
tom at pledger.gen.nz
Sun Jul 15 20:13:25 EDT 2007
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. Perhaps a
purpose-built heap monad would make it more elegant... as long as it
could be reused elsewhere. Just musing. :-)
- Tom
More information about the Haskell-Cafe
mailing list