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

[Chung-chieh Shan]

Tom Pledger <tom at pledger.gen.nz> wrote in article <20070716121325.2bx53nnm8c8w0k8g at webmail.pledger.gen.nz> in gmane.comp.lang.haskell.cafe:
> 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]

Here's my solution to the xkcd problem (yay infinite lists):

xkcd_c287' = foldr
        (\cost without ->
            let (poor, rich) = splitAt cost without
                with = poor ++ zipWith (++) rich (map (map (cost:)) with)
            in with)
        ([[]] : repeat [])
        [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]
        !!
        1505 -- 150005

Replacing the two lines with comments by the comments solves your case
quickly.

Thanks!  That was fun!

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
http://www.unaids.org/en/HIV_data/epi2006/
UNAIDS/WHO AIDS Epidemic Update: December 2006