MIT 6.00 Lecture 8 - Stirling's approximation

Approximating large factorials:

import math

def stirling(n):
    return math.sqrt(2*math.pi*n) * (n/math.e)**n

if __name__ == '__main__':
    for i in range(1,20):
        s = stirling(i)
        f = math.factorial(i)
        print "stirling: %21.2f  factorial: %21d  error: %3.2f%%" % (s, f, abs(((f-s)/s)*100.0))

Output:

stirling:                  0.92  factorial:                     1  error: 8.44%
stirling:                  1.92  factorial:                     2  error: 4.22%
stirling:                  5.84  factorial:                     6  error: 2.81%
stirling:                 23.51  factorial:                    24  error: 2.10%
stirling:                118.02  factorial:                   120  error: 1.68%
stirling:                710.08  factorial:                   720  error: 1.40%
stirling:               4980.40  factorial:                  5040  error: 1.20%
stirling:              39902.40  factorial:                 40320  error: 1.05%
stirling:             359536.87  factorial:                362880  error: 0.93%
stirling:            3598695.62  factorial:               3628800  error: 0.84%
stirling:           39615625.05  factorial:              39916800  error: 0.76%
stirling:          475687486.47  factorial:             479001600  error: 0.70%
stirling:         6187239475.19  factorial:            6227020800  error: 0.64%
stirling:        86661001740.60  factorial:           87178291200  error: 0.60%
stirling:      1300430722199.47  factorial:         1307674368000  error: 0.56%
stirling:     20814114415223.14  factorial:        20922789888000  error: 0.52%
stirling:    353948328666101.12  factorial:       355687428096000  error: 0.49%
stirling:   6372804626194313.00  factorial:      6402373705728000  error: 0.46%
stirling: 121112786592294176.00  factorial:    121645100408832000  error: 0.44%

As n increases the error decreases:

n=165 error: 0.0505177446%
n=166 error: 0.0502133452%
n=167 error: 0.0499125922%
n=168 error: 0.0496154204%
n=169 error: 0.0493217663%

MIT 6.00 Lecture 8 Notes on exp()

In Lecture 8 a recursive algorithm for finding a to the b is shown. The algorithm flip-flops between two cases (even, odd) until it reaches the base case of b == 0. For odd cases the problem is reduced by one, for even cases the problem is reduced by half.

I think it can be hard to see where the final result comes from at first. What can exp() return? It can return 1, a or *a. 1 is returned for the edge case b == 0 so returning a or *a are the typical results. Any particular result is going to be of the form:

result = a*a*a .  .  .


For 2**15:

    exp3(2,15)
2*exp3(2,14)
    exp3(4,7)
4*exp3(4,6)
    exp3(16,3)
16*exp3(16,2)
    exp3(256,1)
b == 1
a: 256
result: 32768


result = 2*4*16*256 => 32768

Also notice that in the below code that the even test is (b%2)*2 == 0 not == b.

Python Code:

def exp(a,b,mult):
    print "Call %d*exp3(%d,%d)" % (mult,a,b)
    if b == 0:
        print 'b == 0'
        return 1

    if b == 1:
        print 'b == 1'
        print "a: %d" % (a)
        return a

    if (b%2)*2 == 0:
        print '\tif (b%2)*2 == 0: ',
        print "[b: %d]" % (b)
        return exp(a*a, b/2, 1)
    else:
        print "\telse              [b: %d]" % (b)
        return a*exp(a, b-1, a)

if __name__ == '__main__':
    for i in range(0,16):
        print "===> 2^%d" % (i)
        print "result: %d\n" % exp(2,i,1)

'''
exp(2,4)
  exp(2*2, 4/2)
    exp(4*4, 2/2)
    b == 1
    return 16

==> 16

exp(2,5)
  2*exp(2, 5-1)
    exp(2*2, 4/2)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 2 = 32

exp(2,6)
  exp(2*2, 6/2)
    4*exp(4, 3-1)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 4 = 64          
'''

Output:

===> 2^0
Call 1*exp3(2,0)
b == 0
result: 1

===> 2^1
Call 1*exp3(2,1)
b == 1
a: 2
result: 2

===> 2^2
Call 1*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 4

===> 2^3
Call 1*exp3(2,3)
        else              [b: 3]
Call 2*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 8

===> 2^4
Call 1*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 16

===> 2^5
Call 1*exp3(2,5)
        else              [b: 5]
Call 2*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 32

===> 2^6
Call 1*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 64

===> 2^7
Call 1*exp3(2,7)
        else              [b: 7]
Call 2*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 128

===> 2^8
Call 1*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 256

===> 2^9
Call 1*exp3(2,9)
        else              [b: 9]
Call 2*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 512

===> 2^10
Call 1*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 1024

===> 2^11
Call 1*exp3(2,11)
        else              [b: 11]
Call 2*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 2048

===> 2^12
Call 1*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 4096

===> 2^13
Call 1*exp3(2,13)
        else              [b: 13]
Call 2*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 8192

===> 2^14
Call 1*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 16384

===> 2^15
Call 1*exp3(2,15)
        else              [b: 15]
Call 2*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 32768

MIT 6.00 Problem Set 6 - Problem 5

LPG Delivery, Seoul

Assume worst case. pick_best_word() is going to produce 13699 candidate words to be checked against the dictionary. pick_best_word_faster() is going to produce 127 candidate words to be checked against the dictionary.

The original word list is length 83667 while the rearranged word list is length 69091. The reduction in length is from the collapse of sets of words made from the same letters into single words.

I think the bulk of the performance improvement is from the reduction in candidate words, not dictionary length or access methods.


Python Output:


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

>>> len(list(itertools.combinations('abcdefg', 7)))
1
>>> len(list(itertools.combinations('abcdefg', 6)))
7
>>> len(list(itertools.combinations('abcdefg', 5)))
21
>>> len(list(itertools.combinations('abcdefg', 4)))
35
>>> len(list(itertools.combinations('abcdefg', 3)))
35
>>> len(list(itertools.combinations('abcdefg', 2)))
21
>>> len(list(itertools.combinations('abcdefg', 1)))
7
>>> 1+7+21+35+35+21+7
127

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.

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

MIT 6.00 Problem Set 6 Answer - Problems 1 & 2

Python Code Answer:

def play_hand(hand, word_list):
    total_score = 0.0
    min_elapsed = 0.010
    hand_score = 0.0

    time_limit = raw_input('Enter Time Limit: ')
    
    if time_limit.isdigit():
        time_limit = float(time_limit)
    else:
        print "Enter Valid Time Limit"
        return

    while True:        
        print

        num_letters = 0
        for key in hand.keys():
            for i in range(hand[key]):
                num_letters += 1
                print key,

        if num_letters < 1:
            break

        start = time.time()
        word = raw_input('Word: ')
        stop = time.time()
        
        elapsed = stop - start
        time_limit -= elapsed

        # prevent divide by zero error, force min time
        if elapsed < min_elapsed:
            elapsed = min_elapsed

        if word == '.':
            break

        if is_valid_word(word, hand, word_list):
            update_hand(hand, word)
            if time_limit > 0.0:
                hand_score = get_word_score(word, num_letters) / elapsed
                total_score += hand_score
            else:
                print "Time limit exceeded."
            print "Score: %0.2f  Total Score: %0.2f" % (hand_score, total_score)
        else:
            print "Invalid word. Try again."

        if time_limit >= 0:
            print "Turn took %0.2f seconds, %0.2f seconds remaining" % (elapsed, time_limit)
    
    print "Final Score: %0.2f" % (total_score)

Output:

Loading word list from file...
   83667 words loaded.
Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter Time Limit: 10

q e t h j o n Word: note
Score: 0.44  Total Score: 0.44
Turn took 9.05 seconds, 0.95 seconds remaining

q h j Word: .
Final Score: 0.44

Enter n to deal a new hand, r to replay the last hand, or e to end game:
Invalid command.
Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter Time Limit:
Enter Valid Time Limit

Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter Time Limit: asdf
Enter Valid Time Limit

Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter Time Limit: 10

a q v p j j o Word:
Invalid word. Try again.

a q v p j j o Word: .
Final Score: 0.00

Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter Time Limit: 10

p u t i h z n Word: putz
Score: 3.28  Total Score: 3.28
Turn took 4.57 seconds, 5.43 seconds remaining

i h n Word: hin
Score: 1.51  Total Score: 4.79
Turn took 3.98 seconds, 1.45 seconds remaining

Final Score: 4.79

Enter n to deal a new hand, r to replay the last hand, or e to end game:

MIT 6.00 Problem Set 4 - Problem 5 Answer

Key Largo

I spent a bunch of time thinking about how to do an exhaustive search with a given fragment by appending every letter of the alphabet all the way up to the maximum word length in the dictionary to see if the fragment was the beginning of a dictionary word. I thought there had to be a better way.


This code below is looking for an exact match. If fragment_str is the beginning of a word that is in the wordlist but not a standalone word then this test will return False.

if fragment_str in wordlist:

The fragment of length n should be compared with the first n letters of each dictionary word. If there is a match then there is a word containing that fragment. The search itself is brute force. Words that are too short are checked. Words that don't even begin with the same first letter are checked. So the efficiency can be improved but the game play is correct. 

Python Code Answer:

def fragment_starts_word(fragment_str, wordlist):
    fragment_str_len = len(fragment_str)

    for word in wordlist:
        if word[0:fragment_str_len] == fragment_str:
            if len(word) > len(fragment_str):
                print "Fragment (%s) is start of at least one longer word (%s)" % (fragment_str, word)
                return True


def other(player):
    if player == 1:
        return 2
    else:
        return 1

          
def ghost():
    wordlist = load_words()
    fragment = []
    player = 1
    fragment_str = ""

    while True:
        print "\nFragment: " + fragment_str
        turn = raw_input("Player " + str(player) + " Turn: ")

        if len(turn) == 1 and turn in string.ascii_letters:
            fragment.append(turn.lower())
            fragment_str = "".join(fragment)

            if fragment_str in wordlist:
                print fragment_str + " is a word."
                if len(fragment) > 3:
                    print "Player " + str(player) + " loses."
                    print "Player " + str(other(player)) + " wins!"
                    sys.exit(0)
            elif fragment_starts_word(fragment_str, wordlist) != True:
                    print "Fragment is not beginning of any word."
                    sys.exit(0)
        else:
            print "Input must be a single letter."
            break

        player = other(player)

if __name__ == '__main__':
    ghost()

Output:

Loading word list from file...
   83667 words loaded.

Fragment:
Player 1 Turn: p
Fragment (p) is start of at least one longer word (pa)

Fragment: p
Player 2 Turn: e
pe is a word.

Fragment: pe
Player 1 Turn: a
pea is a word.

Fragment: pea
Player 2 Turn: f
Fragment (peaf) is start of at least one longer word (peafowl)

Fragment: peaf
Player 1 Turn: o
Fragment (peafo) is start of at least one longer word (peafowl)

Fragment: peafo
Player 2 Turn: w
Fragment (peafow) is start of at least one longer word (peafowl)

Fragment: peafow
Player 1 Turn: l
peafowl is a word.
Player 1 loses.
Player 2 wins!

******************************************************

Fragment:
Player 1 Turn: p
Fragment (p) is start of at least one longer word (pa)

Fragment: p
Player 2 Turn: y
Fragment (py) is start of at least one longer word (pya)

Fragment: py
Player 1 Turn: t
Fragment (pyt) is start of at least one longer word (python)

Fragment: pyt
Player 2 Turn: h
Fragment (pyth) is start of at least one longer word (python)

Fragment: pyth
Player 1 Turn: o
Fragment (pytho) is start of at least one longer word (python)

Fragment: pytho
Player 2 Turn: n
python is a word.
Player 2 loses.
Player 1 wins!

******************************************************

Fragment:
Player 1 Turn: q
Fragment (q) is start of at least one longer word (qabala)

Fragment: q
Player 2 Turn: z
Fragment is not beginning of any word.

MIT 6.00 Problem Set 5 - Problems 1 - 4 Answers

Juvenile Gull, Australia

Problem set 5 has a framework of provided code to complete the assignment within. Below is the code that needs to be added to the framework to complete the assignment.

Python Code Answer:

# Problem #1: Scoring a word
def get_word_score(word, n):
    score = 0

    for c in word:
        score += SCRABBLE_LETTER_VALUES[c]

    if len(word) == HAND_SIZE:
        score += 50

    return score



# Problem #2: Update a hand by removing letters

def update_hand(hand, word):
    for c in word:
        hand[c] -= 1

    return hand


# Problem #3: Test word validity
def is_valid_word(word, hand, word_list):
    local_hand = hand.copy()

    for c in word:
        if local_hand.get(c, 0) == 0:
            return False
        else:
            local_hand[c] -= 1
    
    if word.lower() in word_list:
        return True
    else:
        return False
            

# Problem #4: Playing a hand
def play_hand(hand, word_list):
    total_score = 0

    while True:        
        print

        num_letters = 0
        for key in hand.keys():
            for i in range(hand[key]):
                num_letters += 1
                print key,

        if num_letters < 1:
            break

        word = raw_input('Word: ')

        if word == '.':
            break

        if is_valid_word(word, hand, word_list):
            update_hand(hand, word)
            hand_score = get_word_score(word, num_letters)
            total_score += hand_score
            print "Score: %d  Total Score: %d" % (hand_score, total_score)
        else:
            print "Invalid word. Try again."
    
    print "Final Score: %d" % (total_score)

Output:

Loading word list from file...
   83667 words loaded.
Enter n to deal a new hand, r to replay the last hand, or e to end game: n

u y h j o n n Word: joy
Score: 13  Total Score: 13

u h n n Word: hun
Score: 6  Total Score: 19

n Word: .
Final Score: 19

Enter n to deal a new hand, r to replay the last hand, or e to end game: n

r r u v k l o Word: .
Final Score: 0

Enter n to deal a new hand, r to replay the last hand, or e to end game: n

a r u w y h j Word: yaw
Score: 9  Total Score: 9

r u h j Word: .
Final Score: 9

MIT 6.00 Problem Set 4 - Problems 1 - 4 Answers

White-headed Capuchin, Costa Rica

Python Code Answer:

# MIT 6.00 Problem Set 4 - Problems 1-4

def nestEggFixed(salary, save, growthRate, years):
    balance = []
    contrib = salary * save * 0.01
    growth = 1 + 0.01 * growthRate

    for y in range(years):
        if y == 0:
            balance.append(contrib)        
        else:
            balance.append(balance[y-1] * growth + contrib)
        
        print "y: %d balance[y]: $%0.2f " % (y, balance[y])

    return balance

print nestEggFixed(10000, 10, 15, 5)  
print

def nestEggVariable(salary, save, growthRates):
    balance = []
    contrib = salary * save * 0.01

    for y in range(len(growthRates)):
        growth = 1 + 0.01 * growthRates[y]

        if y == 0:
            balance.append(contrib)         
        else:
            balance.append(balance[y-1] * growth + contrib)
        
        print "y: %d balance[y]: $%0.2f (%2.2f%%)" % (y, balance[y], growthRates[y])

    return balance

rates = [15, 15, 15, 15, 15]
print nestEggVariable(10000, 10, rates)
print

rates = [1.34, 2.5, 3.23, 1.2, 0.93]
print nestEggVariable(10000, 10, rates)
print
    

def postRetirement(savings, growthRates, expenses):
    for y in range(len(growthRates)):
        growth = 1 + 0.01 * growthRates[y]
        savings = (savings * growth) - expenses
        
        #print "y: %d savings: $%10.2f (%2.2f%%)" % (y, savings, rates[y])

    return savings

rates = [0, 0, 0, 0, 0]
print postRetirement(100000, rates, 10000)
print

rates = [7, 7, 7, 7, 7]
print postRetirement(100000, rates, 20000)
print

rates = [-25.8, -10.3, 2.1, 1.1, 2.2]
print postRetirement(100000, rates, 25000)
print

rates = [10, 5, 0, 5, 1]
print postRetirement(100000, rates, 30000)
print


def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates, epsilon): 
    nestEgg = nestEggVariable(salary, save, preRetireGrowthRates)
    print "\nnestEgg: %7.2f\n" % (nestEgg[-1])

    finalBalance = 2 * epsilon
    upper = nestEgg[-1]
    lower = 0
    midPoint = ((upper - lower) / 2.0) + lower
    count = 0

    while abs(finalBalance) > epsilon:
        finalBalance = postRetirement(nestEgg[-1], postRetireGrowthRates, midPoint)
        print "finalBalance: %7.2f  expenses: %7.2f" % (finalBalance, midPoint)

        if finalBalance > 0.0:
            lower = midPoint
        else:
            upper = midPoint

        midPoint = ((upper - lower) / 2.0) + lower
            
            
preRates = [3, 4, 5, 0, 3]
postRates = [10, 5, 0, 5, 1]
print
print findMaxExpenses(10000, 10, preRates, postRates, 0.01)

Output:

y: 0 balance[y]: $1000.00
y: 1 balance[y]: $2150.00
y: 2 balance[y]: $3472.50
y: 3 balance[y]: $4993.38
y: 4 balance[y]: $6742.38
[1000.0, 2150.0, 3472.5, 4993.375, 6742.381249999999]

y: 0 balance[y]: $1000.00 (15.00%)
y: 1 balance[y]: $2150.00 (15.00%)
y: 2 balance[y]: $3472.50 (15.00%)
y: 3 balance[y]: $4993.38 (15.00%)
y: 4 balance[y]: $6742.38 (15.00%)
[1000.0, 2150.0, 3472.5, 4993.375, 6742.381249999999]

y: 0 balance[y]: $1000.00 (1.34%)
y: 1 balance[y]: $2025.00 (2.50%)
y: 2 balance[y]: $3090.41 (3.23%)
y: 3 balance[y]: $4127.49 (1.20%)
y: 4 balance[y]: $5165.88 (0.93%)
[1000.0, 2025.0, 3090.4075, 4127.492389999999, 5165.878069227]

50000.0

25240.39287

-56197.5143751

-34848.0


y: 0 balance[y]: $1000.00 (3.00%)
y: 1 balance[y]: $2040.00 (4.00%)
y: 2 balance[y]: $3142.00 (5.00%)
y: 3 balance[y]: $4142.00 (0.00%)
y: 4 balance[y]: $5266.26 (3.00%)

nestEgg: 5266.26

finalBalance: -7358.99  expenses: 2633.13
finalBalance: -454.23  expenses: 1316.57
finalBalance: 2998.14  expenses:  658.28
finalBalance: 1271.95  expenses:  987.42
finalBalance:  408.86  expenses: 1151.99
finalBalance:  -22.69  expenses: 1234.28
finalBalance:  193.09  expenses: 1193.14
finalBalance:   85.20  expenses: 1213.71
finalBalance:   31.26  expenses: 1223.99
finalBalance:    4.28  expenses: 1229.14
finalBalance:   -9.20  expenses: 1231.71
finalBalance:   -2.46  expenses: 1230.42
finalBalance:    0.91  expenses: 1229.78
finalBalance:   -0.77  expenses: 1230.10
finalBalance:    0.07  expenses: 1229.94
finalBalance:   -0.35  expenses: 1230.02
finalBalance:   -0.14  expenses: 1229.98
finalBalance:   -0.04  expenses: 1229.96
finalBalance:    0.02  expenses: 1229.95
finalBalance:   -0.01  expenses: 1229.96

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset4.pdf