# 6.00 Problem Set 5 solutions # # The Word Game II # import random import time VOWELS = 'aeiou' CONSONANTS = 'bcdfghjklmnpqrstvwxyz' HAND_SIZE = 7 # ----------------------------------- # Helper code # (you don't need to understand this helper code) import string WORDLIST_FILENAME = "words.txt" def load_words(): """ Returns a list of valid words. Words are strings of lowercase letters. Depending on the size of the word list, this function may take a while to finish. """ print "Loading word list from file..." # inFile: file inFile = open(WORDLIST_FILENAME, 'r', 0) # line: string line = inFile.readline() # wordlist: list of strings wordlist = string.split(line) print " ", len(wordlist), "words loaded." return wordlist def get_frequency_dict(sequence): """ Returns a dictionary where the keys are elements of the sequence and the values are integer counts, for the number of times that an element is repeated in the sequence. sequence: string or list return: dictionary """ # freqs: dictionary (element_type -> int) freq = {} for x in sequence: freq[x] = freq.get(x,0) + 1 return freq # (end of helper code) # ----------------------------------- def get_word_score(word): """ Returns the score for a word. Assumes the word is a valid word. The score for a word is the sum of the scores of the individual letters, multiplied by the length of the word. Letters that are VOWELS get a score of 1. Letters that are CONSONANTS get a score of 2. word: string (lowercase letters) returns: int >= 0 """ score = 0 for ch in word: if ch in VOWELS: score += 1 else: score += 2 return score * len(word) def display_hand(hand): """ Displays the letters currently in the hand. For example: display_hand({'a':1, 'x':2, 'l':3, 'e':1}) Should print out something like: a x x l l l e The order of the letters is unimportant. hand: dictionary (string -> int) """ for letter in hand.keys(): for j in range(hand[letter]): print letter, # print all on the same line print # print an empty line def deal_hand(n): """ Returns a random hand containing n lowercase letters. At least n/3 the letters in the hand should be VOWELS. Hands are represented as dictionaries. The keys are letters and the values are the number of times the particular letter is repeated in that hand. n: int >= 0 returns: dictionary (string -> int) """ hand={} num_vowels = n / 3 for i in range(num_vowels): x = VOWELS[random.randrange(0,len(VOWELS))] hand[x] = hand.get(x, 0) + 1 for i in range(num_vowels, n): x = CONSONANTS[random.randrange(0,len(CONSONANTS))] hand[x] = hand.get(x, 0) + 1 return hand def update_hand(hand, word): """ Assumes that 'hand' has all the letters in word. In other words, this assumes that however many times a letter appears in 'word', 'hand' has at least as many of that letter in it. Updates the hand: uses up the letters in the given word and returns the new hand, without those letters in it. word: string hand: dictionary (string -> int) returns: dictionary (string -> int) """ hand = hand.copy() for ch in word: hand[ch] -= 1 return hand def is_valid_word(word, hand, points_dict): """ Returns True if word is in the word_list and is entirely composed of letters in the hand. Otherwise, returns False. word: string hand: dictionary (string -> int) #word_list: list of lowercase strings points_dict: dictionary of lowercase strings """ #if word in word_list: if word in points_dict: freq = get_frequency_dict(word) for letter in freq: count = freq[letter] if count > hand.get(letter, 0): return False return True else: return False def hand_has_letters(hand): """ return true if the hand still has letters in it """ for letter in hand: if hand[letter] > 0: return True return False def play_hand(hand, word_list): """ Allows the user to play the given hand, as follows: * The hand is displayed. * The user may input a word. * An invalid word is rejected, and a message is displayed asking the user to choose another word. * When a valid word is entered, it uses up letters from the hand. * After every valid word: the score for that word is displayed, the remaining letters in the hand are displayed, and the user is asked to input another word. * The sum of the word scores is displayed when the hand finishes. * The hand finishes when there are no more unused letters. The user can also finish playing the hand by inputing a single period (the string '.') instead of a word. hand: dictionary (string -> int) word_list: list of lowercase strings """ k = 1 #arbitrary k, to be determined by experimenting. n = sum(hand.values()) total = 0 total_time = 0 #solution to prob2 (1 line below) #time_limit = input('Enter time limit, in seconds, for players: ') #note that it would be better to place the below line inside play_game instead. #this sets the time limit for the computer. time_limit = get_time_limit(points_dict,k) while hand_has_letters(hand): print 'Current Hand: ', display_hand(hand) start_time = time.time() # solution for probs 1 and 2 (1 line below) #word = raw_input('Enter word, or a . to indicate that you are finished: ') #for prob 3 #word = pick_best_word(hand,points_dict) #for prob 4 word = pick_best_word_faster(hand,rearrange_dict) end_time = time.time() total_time += end_time-start_time if total_time > time_limit: print 'Total time exceeds %0.3f seconds.' % time_limit,'You scored %0.2f points.' % total break if word == '.': break print 'It took %0.2f seconds to provide an answer' % total_time if is_valid_word(word, hand, points_dict): hand = update_hand(hand, word) # Adding .001 to total time to avoid zero division error # (time.time() function has limited precision) score = get_word_score(word)/(total_time + .001) total += score print word, 'earned %0.2f' % score, 'points. Total: %0.2f' % total, 'points' else: print 'Invalid word, please try again.' print 'Total score: %0.2f points.' % total def play_game(word_list): """ Allow the user to play an arbitrary number of hands. * Asks the user to input 'n' or 'r' or 'e'. * If the user inputs 'n', let the user play a new (random) hand. When done playing the hand, ask the 'n' or 'e' question again. * If the user inputs 'r', let the user play the last hand again. * If the user inputs 'e', exit the game. * If the user inputs anything else, ask them again. """ ## uncomment the following block of code once you've completed Problem #4 hand = deal_hand(HAND_SIZE) # random init while True: cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ') if cmd == 'n': hand = deal_hand(HAND_SIZE) play_hand(hand.copy(), word_list) print elif cmd == 'r': play_hand(hand.copy(), word_list) print elif cmd == 'e': break else: print "Invalid command." ###################### ## Prob 3 functions ## ###################### def get_words_to_points(word_list): """ Return a dict that maps every word in word_list to its point value. """ global points_dict points_dict = {} for word in word_list: points_dict[word] = get_word_score(word) return points_dict def pick_best_word(hand, points_dict): """ Return the highest scoring word from points_dict that can be made with the given hand. Return '.' if no words can be made with the given hand. """ highest_score = 0 best_word = '.' for word in points_dict: valid = is_valid_word(word, hand, points_dict) word_score = points_dict[word] if valid and word_score > highest_score: highest_score = word_score best_word = word return best_word def get_time_limit(points_dict, k): """ Return the time limit for the computer player as a function of the multiplier k. points_dict should be the same dictionary that is created by get_words_to_points. """ start_time = time.time() for word in points_dict: # Use the dict representation (instead of list) get_frequency_dict(word) get_word_score(word) end_time = time.time() return (end_time - start_time) * k ###################### ## Prob 4 functions ## ###################### #This should initialize the better dictionary from word_list #the returned dictionary is mapped as follows: #sorted_seq_of_letters -> word def get_word_rearrangements(word_list): """ Return a dict that maps each word alphabetically sorted to itself """ new_dict = {} for word in points_dict: sorted_str = sort_letters(word) new_dict[sorted_str] = word return new_dict #sorts a string. input_word -> string where letetrs are sorted in alpha order def sort_letters(input_word): #use merge sort (or not) output_str = list(input_word) output_str.sort() return ''.join(output_str); #This converts a hand into a string def hand2str(hand): out_str = '' for letter in hand.keys(): for j in range(hand[letter]): out_str += letter return out_str def generate_all_subsets(s): "Return a sequence containing all the substrings of the string s." if len(s) == 0: return [""] # Include every subset of the elements that doesn't contain s[0]... subsets = generate_all_subsets(s[1:]) ans = subsets[:] # ...and every subset that does (these are generated by adding s[0] to # every subset of the previously generated sequence). for subset in subsets: ans.append(s[0] + subset) return ans ## PSEUDOCODE ## ##To find some word that can be made out of the letters in HAND: ## For each subset S of the letters of HAND: ## Let w = (the string containing the letters of S in sorted order) ## If w in d: return d[w] ## using standard dictionary, but calling get_word_rearrangements from within ## to get sorted-letter-key dictionary def pick_best_word_faster(hand, rearrange_dict): word = hand2str(hand) combo_list = generate_all_subsets(word) best_score = 0 best_word = '.' for s in combo_list: sortedletters = sort_letters(s) if sortedletters in rearrange_dict: curr_word = rearrange_dict[sortedletters] curr_score = points_dict[curr_word] if curr_score > best_score: best_score = curr_score best_word = curr_word return best_word #### Problem 5 (for our implementation only) #### ## (prob3) pick_best_word: ## O(len(points_dict)*sum(hand.values())) ## ## (prob4) pick_best_word_faster: ## 2^HAND_SIZE + 2^HAND_SIZE * HAND_SIZE*log(HAND_SIZE) ## O(2^HAND_SIZE * HAND_SIZE*log(HAND_SIZE)) ## Notice that pick_best_word depends only on HAND_SIZE and not on size of ## dictionary, therefore the time improves. ## This is why calling get_word_rearrangements from pick_best_word_faster will ## not do justice. This will make pick_best_word_faster (from prob4) no better ## than pick_best_word (from prob3). # # Build data structures used for entire session and play game # if __name__ == '__main__': word_list = load_words() global points_dict points_dict = get_words_to_points(word_list) global rearrange_dict rearrange_dict = get_word_rearrangements(word_list) play_game(word_list)