Mainly Tech projects on Python and Electronic Design Automation.

Saturday, June 13, 2009

XKCD Knapsack Solution

A brute force solution to the following comic from href="http://xkcd.com/287/">XKCD:



title="General solutions get you a 50% tip."
src="http://imgs.xkcd.com/comics/np_complete.png">





Assuming the one sandwich represents the end of the menu, I used an
exhaustive search algorithm. Things to note are the use of zip(*table)
to transpose the items and itertools.product instead of nested for
loops.


'''
from: href="http://xkcd.com/287/">http://xkcd.com/287/
'''

color="#a020f0">from itertools color="#a020f0">import product

items = ( (' color="#ff00ff">MIXED FRUIT', 2.15),
(' color="#ff00ff">FRENCH FRIES', 2.75),
(' color="#ff00ff">SIDE SALAD', 3.35),
(' color="#ff00ff">HOT WINGS', 3.55),
(' color="#ff00ff">MOZZ STICKS', 4.20),
(' color="#ff00ff">SAMPLER PLATE', 5.80),
(' color="#ff00ff">BARBEQUE', 6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
rangeofdishes = [tuple(range(1+int( (exactcost+0.005)/price ))) color="#804040">for price color="#804040">in prices]

possibleorders = [tuple(zip(dishes, numbers))
color="#804040">for numbers color="#804040">in product(*rangeofdishes)
color="#804040">if int(exactcost*100)
== int(100* sum(num*price
color="#804040">for num,price color="#804040">in zip(numbers, prices)))
]
color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
color="#804040">for order color="#804040">in possibleorders:
color="#804040">print( ' color="#ff00ff"> ',
' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount color="#804040">for dishcount color="#804040">in order color="#804040">if dishcount[1]))




The answers I get are:

style="font-family: monospace;">ALL POSSIBLE CHOICES OF MENU
ITEMS THAT COST 15.05, ONE PER LINE style="font-family: monospace;">
  
MIXED FRUIT: 1, HOT WINGS: 2, SAMPLER PLATE: 1
style="font-family: monospace;">
  
MIXED FRUIT: 2, MOZZ STICKS: 1, BARBEQUE: 1


  
MIXED FRUIT: 7



(I'd go with the hot wings).

31 comments:

  1. I don't think the BBQ sandwich was supposed to be in there, it's not an appetizer. So #2 isn't valid. :)

    ReplyDelete
  2. If BBQ as an appetizer is wrong, I don't want to be right.

    ReplyDelete
  3. Seeing as I used barbeque as an appetizer I think I need t justify it: Sandwiches are indented w.r.t. the sampler plate so is read as a sub-section of the appetizers ;-)

    (Let the battle commence).

    - Paddy.

    ReplyDelete
  4. Since it is cut off on the menu maybe half a BBQ qualifies.

    ReplyDelete
  5. Yo momma never told you not to use floating-point for currency calculations?

    ReplyDelete
  6. You leave my mother out of this!

    You will note however the gentle sprinkling of 'int' and half cent fairy dust to appease the floating point approximation gods.

    - Paddy.

    ReplyDelete
  7. I don't know, just looking at the cartoon and the menu it took me approx. 15 seconds to realize that I could do it with giving them all Fresh Fruit, since the order did not specify a mix of appetizers that is exactly what I would do.

    ReplyDelete
  8. "Assuming the one sandwich represents the end of the menu" methinks you need to brush up on your reading skills. The $15.05 of food is explicitly stated to come from the list of APPETIZERS, not APPETIZERS AND ONE SANDWICH.

    ReplyDelete
  9. ... Then xkcd shouldn't indent the sandwiches under appetizers!

    ReplyDelete
  10. actually paying the bill is the same problem.

    ReplyDelete
  11. Any chance of an expanded version explaining all that? I'm feeling thick ATM ;)

    ReplyDelete
  12. You could express all the values in cents instead of dollars. That way, all they values would be integers and you wouldn't need to worry about floating-point rounding errors.

    ReplyDelete
  13. If you can show me more than one restaurant that includes a list of sandwiches in the appetizer section, I'll eat my hat.

    ReplyDelete
  14. Go for the dynamic programming solution.

    ReplyDelete
  15. See my next blog entry for a better solution. I use plain recursion and integers, but keep the sandwich. (It makes my solutions stand out from the crowd).

    P.S. @Anon: "More than one restaurant...", So you admit we agree on one :-)

    P.P.S. @ruiaf and others: Dynamic programming is a nice name, but I don't get its applicability after reading the Wikipedia entry? If you do a DP solution then please link to it here.

    - Paddy.

    ReplyDelete
  16. Paddy, you clearly have very little training with algorithms. Do you know what big-O notation is?

    Dynamic programming reduces the solution time from exponential to pseudopolynomial. Why is this important? Neither of your solutions scale well. Many "real-world" applications of the knapsack problem, some of which appear in the world of cryptography. In these cases, you'll have far more than 6 items. You might also run into a case where each item has an associated value, and you want to maximize it while staying under the weight (which, incidentally, is how the original knapsack problem is worded).

    Point being, your solution will not be very useful in any other case other than this.

    ReplyDelete
  17. @Anon: Your post is irrelevant, Paddy already declared his solution as a bruteforce one. Other than that his programme solved the given problem. You might be very clever, but seriously lack the sense for fun.

    ReplyDelete
  18. @Anon, (the one going on about dynamic programming), drone, drone, drone. Show me the code!

    I penned a useful (true) knapsack problem elsewhere on my blog that is also on Rosetta Code.

    Check out the WP entry for dynamic programming and state where the optimal substructure, and overlapping subproblems lay for example.

    As for training and big-O notation and scalability, it is easy to say. Try and apply DP and see how far you get. I doubt you can do better than this, or my second, simpler version in terms of big-O. but I would be enriched if you could, so please try.

    - Paddy.

    ReplyDelete
  19. dynamic programming guyTue Jun 16, 12:06:00 am

    Here's my solution, Paddy:
    http://pastebin.com/m3c71247b

    The execution times for the given problem are almost identical. However, if you bump up the target price to say, $220, the differences are quite notable.

    I probably could wheedle some more optimization out of it: the most obvious one is to divide the weights (meal prices) and the target (knapsack capacity) by their GCD to reduce the size of the arrays and I'm sure there are some more non-obvious ones a smarter person could find. I wasn't positive on the best way to force it to get exactly the price in question, so my method of doing that might have been suboptimal.

    Note that this is about 25 or so minutes of work, so I may have one or two bugs, but it seems to work well.

    I don't do well with commenting on code, but if you have a question, ask and I'll do my best to explain.

    ReplyDelete
  20. dynamic programming guyTue Jun 16, 12:15:00 am

    PS, it doesn't yield all solutions; just any that work. Finding all solutions would certainly complicate the code.

    ReplyDelete
  21. Hi DP Guy,
    I ran your amendment code on the link you gave.

    It returned a list of 7 instances of the string 'FRENCH FRIES' followed by 2426 instances of 'MIXED FRUIT'.

    Your original snippet does the same.

    I didn't understand your last comment. surely any solution that works would be the same as all solutions?

    - Paddy.

    P.S: Python 2.6.1

    ReplyDelete
  22. dynamic programming guyTue Jun 16, 10:29:00 pm

    Oh, I forgot to change the target price back to 1505 (change 523515 to that in the last line).

    The knapsack problem is interested in any solution (that is, it will find any that maximizes value for items that can fit inside the knapsack). In other words, it returns one solution that works.

    ReplyDelete
  23. Half-cent fairy dust. A sprinkle here, a sprinkle there, pretty soon your talkin' real mony.

    ReplyDelete
  24. I think you should have set aside at least 15% for tip. Leaving only $12.79 for food items. Poor waiter.

    ReplyDelete
  25. i love the elegance of brute force... :+)

    far better than getting bogged down
    in unfunny programming discussions.

    -bowerbird

    ReplyDelete
  26. In case you care, it's barbecue, not barbeque.

    ReplyDelete
  27. To that Anon. who knows how to spell barbecue: thank you. It's appreciated, although I probably won't fix the post due to the clunky Blogger HTML editor that seems to have a, (warped), mind of its own.

    ReplyDelete
  28. Appetizers is a heading. Sandwiches is a heading. Sandwiches are not part of Appetizers. A sampler plate is a mixture of the aforementioned appetizers. The indentation argument is irrelevant since it is on an angle and is hand drawn - you might as well argue side salad is indented because the artist drew a lump on the paper at that point.

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us