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:

XKCD July 9, 2007 
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.

blog comments powered by Disqus