My Hobby: Solving XKCD puzzles on my lunch break
July 09, 2007 at 11:16 AM | categories: python, geek humor | View CommentsI like geek comics. I especially like geek comics that have an embedded NP-Complete problem:
There are 2 solutions: Solution #1: <MenuItem Mixed Fruit 215> <MenuItem Hot Wings 355> <MenuItem Hot Wings 355> <MenuItem Sampler Plate 580> Solution #2: <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215> <MenuItem Mixed Fruit 215>
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 class MenuItem: def __init__(self, name, price): self.name = name self.price = price def __add__(self, other): if hasattr(other,"name") and hasattr(other,"price"): #This is a MenuItem 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), MenuItem("French Fries", 275), MenuItem("Side Salad", 335), MenuItem("Hot Wings", 355), MenuItem("Mozarella Sticks", 420), MenuItem("Sampler Plate", 580)) 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')) solutions.add(tuple(stack)) 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 class MenuItem: def __init__(self, name, price): self.name = name self.price = price def __add__(self, other): if hasattr(other,"name") and hasattr(other,"price"): #This is a MenuItem 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), MenuItem("French Fries", 275), MenuItem("Side Salad", 335), MenuItem("Hot Wings", 355), MenuItem("Mozarella Sticks", 420), MenuItem("Sampler Plate", 580)) 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')) orders.add(tuple(new_order)) self.cache[price] = orders return orders if __name__ == "__main__": if len(sys.argv) == 2: target_price = int(sys.argv[1]) 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.