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

[haskell at list.mightyreason.com]

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