xkcd #287 "NP-Complete"

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

xkcd #287 "NP-Complete"

Tom Pledger
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"

Chung-chieh Shan-2
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/sig
http://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"

Hugh Perkins
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"

Hugh Perkins
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"

Hugh Perkins
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"

Heinrich Apfelmus
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"

haskell-2
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 <function to combine new value with previous result>
       <seed result>
       <list of new values>

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"

Hugh Perkins
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