MIT 6.00 Problem Set 6 - Problem 4 Answer

Anhinga, Florida Everglades

This code is roughly twice as fast as the code from Problem 3. Two changes are responsible for the increased speed.

The first change is the switch from itertools.permutations() to itertools.combinations(). In Problem 3 every permutation of n letters is checked against the dictionary. Since order doesn't mater with a sorted dictionary key permutations would be redundant.


Python Code Answer:

def pick_best_word_faster(hand, rearrange_dict):
    score = 0
    high_word = ""
    perms = []
    attempts = 0
    local_hand = []

    # 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.combinations(local_hand, take))
        take -= 1
    
        for letter_list in perms:
            attempts += 1
            sorted_word = ''.join(sorted(letter_list))

            if rearrange_dict.get(sorted_word, 0):         
                word = rearrange_dict[sorted_word]       
                if score < points_dict[word]:
                    score = points_dict[word]
                    high_word = word
                    print "word: %s  score: %d" % (high_word, score)

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



def get_word_rearrangements(word_list):
    d = {}

    for word in word_list:
        d[''.join(sorted(word))] = word

    return d

Output:


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

word: digit  score: 7
word: timid  score: 8
word: ditz  score: 14
------------------------------------------------------------
attempts: 127
0.0350000858307
Score: 400.00  Total Score: 400.00
Turn took 0.04 seconds, 0.31 seconds remaining

g i m
calling with:
        {'d': 0, 'g': 1, 'i': 1, 'z': 0, 'm': 1, 't': 0}
local_hand:
        ['g', 'i', 'm']

word: mig  score: 6
------------------------------------------------------------
attempts: 7
0.0209999084473
Score: 285.72  Total Score: 685.71
Turn took 0.02 seconds, 0.29 seconds remaining

Final Score: 685.71



a c e j m n n
calling with:
        {'a': 1, 'c': 1, 'e': 1, 'j': 1, 'm': 1, 'n': 2}
local_hand:
        ['a', 'c', 'e', 'j', 'm', 'n', 'n']

word: nance  score: 7
word: mace  score: 8
word: jean  score: 11
word: jam  score: 12
------------------------------------------------------------
attempts: 127
0.0339999198914
Time limit exceeded.
Score: 0.00  Total Score: 0.00

c e n n
calling with:
        {'a': 0, 'c': 1, 'e': 1, 'j': 0, 'm': 0, 'n': 2}
local_hand:
        ['c', 'e', 'n', 'n']

word: ne  score: 2
------------------------------------------------------------
attempts: 15
0.0210001468658
Time limit exceeded.
Score: 0.00  Total Score: 0.00

c n
calling with:
        {'a': 0, 'c': 1, 'e': 0, 'j': 0, 'm': 0, 'n': 1}
local_hand:
        ['c', 'n']

------------------------------------------------------------
attempts: 3
0.018000125885
No legal combination possible.