# xkcd #287 "NP-Complete"

 Classic List Threaded
8 messages
Reply | Threaded
Open this post in threaded view
|

## xkcd #287 "NP-Complete"

 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: xkcd #287 "NP-Complete"

 Tom Pledger <[hidden email]> wrote in article <[hidden email]> 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/sighttp://www.unaids.org/en/HIV_data/epi2006/UNAIDS/WHO AIDS Epidemic Update: December 2006 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: xkcd #287 "NP-Complete"

 In reply to this post by Tom Pledger On 7/16/07, Tom Pledger <[hidden email]> wrote: I'll be a nuisance and bring up this case:     solve 150005 [2, 4, 150001]Argh, that makes my "solution" hang! :-/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: xkcd #287 "NP-Complete"

 In reply to this post by Chung-chieh Shan-2 On 7/16/07, Chung-chieh Shan <[hidden email]> wrote: Here's my solution to the xkcd problem (yay infinite lists):dynamic programming?Cool :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: xkcd #287 "NP-Complete"

 Your solution looks really elegant, and runs insanely fast.  Can you explain how it works? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: xkcd #287 "NP-Complete"

 In reply to this post by Tom Pledger 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: xkcd #287 "NP-Complete"

 In reply to this post by Hugh Perkins Hugh Perkins wrote: > Your solution looks really elegant, and runs insanely fast.  Can you > explain how it works? > > I will jump in and explain, using a more finely named version: xkcd_c287' = foldr          (\cost without ->              let (poor, rich) = splitAt cost without                  with = poor ++ zipWith (++) rich using_cost                  using cost = (map (add_cost) with)                    where add_cost xs = cost:xs              in with)          ([[]] : repeat [])          [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]          !!          1505 -- 150005 At the top level it uses (!!) to pick the 1505th element of the list produced by the use of foldr. foldr                 Here the list of new values is the list of item prices (in pennies) from the menu. The seed result is the answer in the absence of anything on the menu. The seed is ([[]] : repeat []) which is a list of (list of prices).  The "n th" member of the outer list holds the solution for a price of "n pennies". Thus the (!! 1505) selects the answer for a target price of \$15.05. The seed result has an empty list in the 0th position since ordering nothing is a solution to a target price of \$0.00. The function works as follows: >         (\cost without -> The 'cost' is the price of the new item on the menu. The 'without' is the answer taking into account all previously processed items on the menu (before the 'cost' item). The result will be a new answer taking into account 'cost' as well. >             let (poor, rich) = splitAt cost without The items in the old answer 'without' before the index 'cost' are solutions for a target price cheaper than 'cost' and these are in the 'poor' list.  These answers are unchanged by the addition of the 'cost' item. The items in the 'rich' part of the answer may get new solutions that include ordering the new 'cost' item. >                 with = poor ++ zipWith (++) rich using_cost >                 using cost = (map add_cost with) >                   where add_cost xs = cost:xs >             in with) The new answer will be 'with' which is defined recursively. The first elements of 'with' are the 'poor' parts of the old answer 'without' that are obviously unchanged. The 'zipWith (++) rich using_cost' combines the previous 'rich' answers without 'cost' with a new list that uses the 'cost' item.  This is: using cost = (map add_cost with)    where add_cost xs = cost:xs The using_cost list is made from taking the list of answers and prepending the 'cost' item to all the solutions. If this were applied to 'without' instead of 'with'... using cost = (map add_cost without)    where add_cost xs = cost:xs ...then the definition of 'with' would not be recursive and would allow for solutions that only order each menu item 0 or 1 times. Since the definition of using_cost does apply the map to 'with' it can add_cost to answers that already have has add_cost applied to them.  Thus it finds all answers that order the menu items 0,1,2,3.. arbitrarily many times. The "n th" item in 'with' or 'without' has total price of "n", and after add_cost it has a total price of "cost+n", and must be in the "(cost+n)th" position in the answer 'with'.  This is achieve by the using_cost items being after the (poor ++) which means they have been shifted by (length poor) positions which, by the definition of (splitN cost), is equal to 'cost'. Cheers,    Chris _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: xkcd #287 "NP-Complete"

 Thank-you for the explanation :-)  You make it very easy to understand, awesome :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe