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: <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.
LOLPython
June 06, 2007 at 01:17 PM | categories: python, geek humor | View Comments
IN MAI time GIMME localtime LIKE TIMEZOR IZ __name__ KINDA LIKE "__main__"? VISIBLE "YOUZ GOT CHEEZBURGERS?" CATURDAY CAN HAS FIV TODAYZ CAN HAS TIMEZOR THING LOOK AT SIKS! YOUGOTZ CAN HAS raw_input THING IZ YOUGOTZ OWN lower THING KINDA LIKE "yes"? IZ TODAYZ KINDA LIKE CATURDAY? MYLOOPZ CAN HAS THR33 WHILE I CUTE? VISIBLE "TODAYZ CATURDAY! I GETZ ALL YOUS CHEEZBURGERS!" MYLOOPZ THROWZ AWAY ONCE IZ MYLOOPZ SMALL LIKE EASTERBUNNY? KTHXBYE NOPE? VISIBLE "O RLY? CAN I HAS YOUS CHEEZBURGER?" NOPE? VISIBLE "I SAW WHAT YOU DID, YOU ATE MY CHEEZBURGERS!"
Yea, you're probably saying to yourself, "WTF IS THAT?"
It's LOLPython, the geekiest, funniest thing I've seen all week!
The LOLPython interpreter translates a variation of LOLCode into standard python. LOLCode itself is pretty neat, but because LOLPython is based on Python, it automatically inherits all of the Python library too. Here's the above code after translation:
from time import localtime as TIMEZOR if __name__ == '__main__' : print 'YOUZ GOT CHEEZBURGERS?' CATURDAY = 5 TODAYZ = TIMEZOR ()[ 6 ] YOUGOTZ = raw_input () if YOUGOTZ . lower ()== 'yes' : if TODAYZ == CATURDAY : MYLOOPZ = 3 while 1: print 'TODAYZ CATURDAY! I GETZ ALL YOUS CHEEZBURGERS!' MYLOOPZ -= 1 if MYLOOPZ <= 0 : break else : print 'O RLY? CAN I HAS YOUS CHEEZBURGER?' else : print 'I SAW WHAT YOU DID, YOU ATE MY CHEEZBURGERS!'
Yep, I'm a nerd
January 11, 2006 at 12:36 PM | categories: python, geek humor | View Comments
I was just reading today's Foxtrot.
Check this out:
bin = ['01011001','01001111','01010101', '01001110','01000101','01010010','01000100'] for b in bin: print chr(int(b,2)),
I Love comics that are made just for me. :)