## My Hobby: Solving XKCD puzzles on my lunch break

July 09, 2007 at 11:16 AM | categories: python, geek humor | View Comments

I like geek comics. I especially like geek comics that have an embedded NP-Complete problem: ```There are 2 solutions:
Solution #1:
Solution #2:
```

This isn't "as fast as possible" to be sure, but it should be a general solution.

```#!/usr/bin/env python

"""Attempt to solve XKCD from July 9 2007"""

#All monetary values are in pennies to avoid floating point errors
# (Yea, I could use decimal.Decimal but it's SLOW!)

import operator

def __init__(self, name, price):
self.name = name
self.price = price
if hasattr(other,"name") and hasattr(other,"price"):
return self.price + other.price
else:
return self.price + other
def __repr__(self):
return "<MenuItem %s %s>" % (self.name,self.price)

appetizers = ( MenuItem("Mixed Fruit",      215),

target_price = 1505

def find_solutions(stack=[],solutions=set()):
"""Find combinations of appetizers that equal target_price"""
#Find if initial stack equals target_price
stack_price = sum([x.price for x in stack])
if stack_price == target_price:
#print("Found a solution!!! " + str(stack) + " == " + str(target_price))
stack.sort(key=operator.attrgetter('price'))
elif stack_price > target_price:
#No solutions for this stack
return set()
#Recurse for each item
for item in appetizers:
find_solutions(stack + [item])
return solutions

if __name__ == "__main__":
solutions = find_solutions()
print "There are %d solutions:" % (len(solutions))
solution_num = 1
for solution in solutions:
print "Solution #%d:" % (solution_num)
for item in solution:
print "\t%s" % item
solution_num += 1
```

Update July 10: Visitor wac pointed out that my program is pretty inefficient. I agree - I did it really quick on my lunch break yesterday. For order values above \$20 it becomes an intractable solution pretty quick. Here is a much more efficient solution that implements value caching (at the cost of requiring more memory than the previous solution):

```#!/usr/bin/env python

"""Attempt to solve XKCD from July 9 2007

This is a new version that uses a cache for calculations
"""

#All monetary values are in pennies to avoid floating point errors
# (Yea, I could use decimal.Decimal but it's SLOW!)

import operator
import sys

def __init__(self, name, price):
self.name = name
self.price = price
if hasattr(other,"name") and hasattr(other,"price"):
return self.price + other.price
else:
return self.price + other
def __repr__(self):
return "<MenuItem %s %s>" % (self.name,self.price)

appetizers = ( MenuItem("Mixed Fruit",      215),

class OrderCache:
"""a cache of all the possible variations of an order for a given price"""
def __init__(self):
self.cache = {0:set([()])} # price -> set([(item1,item2 ...), ...])
def derrive_order(self, price):
"Return all combinations for a given price"
try:
return self.cache[price]
except KeyError:
orders = set()
for item in appetizers:
if price - item.price >= 0:
for order in self.derrive_order(price - item.price):
new_order = list(order) + [item]
new_order.sort(key=operator.attrgetter('price'))
self.cache[price] = orders
return orders

if __name__ == "__main__":
if len(sys.argv) == 2:
target_price = int(sys.argv)
else:
target_price = 1505
order_cache = OrderCache()
solutions = order_cache.derrive_order(target_price)
print "There are %d solutions:" % (len(solutions))
solution_num = 1
for solution in solutions:
print "Solution #%d:" % (solution_num)
for item in solution:
print "\t%s" % item
solution_num += 1
```

With the improved version I can calculate order values up to \$75 in under a minute. That's interesting in and of itself really, because although the second algorithm is much more efficient it would still be practically impossible to calculate an order value of \$1000. That's the nature of NP problems for you.