MIT 6.00 Problem Set 6 Answers - Problem 3

I don't think the intent of this exercise was to write a permutation routine or to use itertools but I used itertools.  pick_best_word() is pretty much the whole assignment.

Python Code Answer:

def pick_best_word(hand, points_dict):
    score = 0
    length = 0
    high_word = ""
    perms = []
    local_hand = []
    attempts = 0

    # itertools.permutations is iterating for letters
    # that are zero count in the hash, dump the zeros
    # convert dict to list
    for k in hand.keys():
        if hand[k] > 0:
            for i in range(hand[k]):
                local_hand.append(k)
        
    print "local_hand: "
    print "\t",
    print local_hand
    print

    take = len(local_hand)
    
    # try for a bingo, then one less than a bingo, etc.
    while take != 0:
        perms = list(itertools.permutations(local_hand, take))
        take -= 1
    
        for letter_list in perms:
            attempts += 1
            word = ""
            for c in letter_list:
                word += c

            if points_dict.has_key(word):
                if score < points_dict[word]:
                    score = points_dict[word]
                    high_word = word
                    print "word: %s  score: %d" % (word, score)

    print "------------------------------------------------------------"
             
    print "attempts: %d" % (attempts)
       
    if score < 1:
        return '.'
    else:
        return high_word

For each seven letter hand 13699 permutations are checked
in the first pass:

>>> import itertools
>>> perms = list(itertools.permutations('1234567', 7))
>>> len(perms)
5040
>>> perms = list(itertools.permutations('1234567', 6))
>>> len(perms)
5040
>>> perms = list(itertools.permutations('1234567', 5))
>>> len(perms)
2520
>>> perms = list(itertools.permutations('1234567', 4))
>>> len(perms)
840
>>> perms = list(itertools.permutations('1234567', 3))
>>> len(perms)
210
>>> perms = list(itertools.permutations('1234567', 2))
>>> len(perms)
42
>>> perms = list(itertools.permutations('1234567', 1))
>>> len(perms)
7
>>> 5040+5040+2520+840+210+42+7
13699

Output:


s u u f y j m
calling with:
        {'s': 1, 'u': 2, 'f': 1, 'y': 1, 'j': 1, 'm': 1}
local_hand:
        ['s', 'u', 'u', 'f', 'y', 'j', 'm']

word: fumy  score: 12
------------------------------------------------------------
attempts: 13699
Score: 184.62  Total Score: 184.62
Turn took 0.06 seconds, 1.75 seconds remaining

s u j
calling with:
        {'s': 1, 'u': 1, 'f': 0, 'y': 0, 'j': 1, 'm': 0}
local_hand:
        ['s', 'u', 'j']

word: jus  score: 10
------------------------------------------------------------
attempts: 15
Score: 400.00  Total Score: 584.61
Turn took 0.03 seconds, 1.73 seconds remaining

Final Score: 584.61


p s t z m o o
calling with:
        {'p': 1, 's': 1, 't': 1, 'z': 1, 'm': 1, 'o': 2}
local_hand:
        ['p', 's', 't', 'z', 'm', 'o', 'o']

word: pomos  score: 9
word: zooms  score: 16
------------------------------------------------------------
attempts: 13699
Score: 275.86  Total Score: 275.86
Turn took 0.06 seconds, 1.59 seconds remaining

p t
calling with:
        {'p': 1, 's': 0, 't': 1, 'z': 0, 'm': 0, 'o': 0}
local_hand:
        ['p', 't']

------------------------------------------------------------
attempts: 4
No legal combination possible.



s s u d g i t
calling with:
        {'s': 2, 'u': 1, 'd': 1, 'g': 1, 'i': 1, 't': 1}
local_hand:
        ['s', 's', 'u', 'd', 'g', 'i', 't']

word: disgust  score: 9
------------------------------------------------------------
attempts: 13699
Score: 1053.57  Total Score: 1053.57
Turn took 0.06 seconds, 1.36 seconds remaining

Final Score: 1053.57