Sweater Project

I was chatting with Lilith on Saturday while I was at work.
She sent me this:
http://xkcd.com/287/

It was slow on Saturday. I sent her this:

#!/usr/bin/python

# try to find 15.05 in appetizers: http://xkcd.com/287/

from random import randrange

appetizers = {
    'fruit' : 2.15,
    'fries' : 2.75,
    'salad' : 3.35,
    'wings' : 3.55,
    'chees' : 4.20,
    'plate' : 5.80,
}

def appsum(appetizers):
    total = 0
    for app in appetizers.values():
        total += app
    return total

target = 15.05

def getUniqueKeys(dict, num):
    "return num distinct keys of dict"
    result = []
    keys = dict.keys()
    while len(result) < num:
        i = randrange( len(keys) )
        result.append( keys[ i ] )
        del(keys[i])
    return result

def getRandomItem(dict):
    "return a random key of dict"
    keys = dict.keys()
    i = randrange( len(keys) )
    return keys[ i ] 

def getRemainingKeys(startKeys, dict):
    "get the keys we don't already have"
    return [ k for k in dict.keys() if k not in startKeys ]

def getKeySum(keys, dict):
    "return the sum of the values for the given keys"
    total = 0
    for key in keys:
        total += dict[key]
    return total

if __name__ == "__main__":

    # get a random item
    # keep selecting other random items
    # until the total meets or exceeds the target
    # if we hit the target, print the items
    done = False
    while not done:       

        total = 0
        items = []
        while total <= target:
            k = getRandomItem(appetizers)
            items.append( k )
            total = getKeySum( items, appetizers )

        #items.sort()
        #print items, total

        if total == target:
            print "SUCCESS"
            print items
            done = True

# it's obvious that there can't just be two items in the order,
# because the two most expensive appetizers only equal $10.
# So, pick two appetizers at random, then add one to the list
# to see if we've got the right amount.

# select an appetizer at random
# compare it with each other appetizer

"""
#The following code doesn't work, because it turns out that you can't
#get $15.05 worth of appetizers when each one is ordered a maximum of
#one time.  No combo of the list meets the target, so you need multiple
#selections.

done = False
numStartItems = 0

while not done:
    numStartItems += 1
    startKeys = getUniqueKeys(appetizers, numStartItems)
    otherKeys = getRemainingKeys(startKeys, appetizers)
    startKeysTotal = getKeySum( startKeys, appetizers )
    print startKeys
    for k in otherKeys:
        print k
        total = startKeysTotal + appetizers[ k ]
        if total == target:
            print "Got it!:"
            print startKeys
            print k
            print total
"""

Then I laughed like a maniac.

The code doesn’t actually work, but it was fun to try.

This entry was posted on Monday, July 30th, 2007 at 12:42 pm and is filed under Personal. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.