Tuesday, July 19, 2011

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.

No comments:

Post a Comment