A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
I'm having trouble with pset6, problem 3.
The function get_best_word is baffling to me and I don't understand how to create all the different combinations from the hand dictionary.
anonymous
 5 years ago
I'm having trouble with pset6, problem 3. The function get_best_word is baffling to me and I don't understand how to create all the different combinations from the hand dictionary.

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Perhaps it'd be easier to iterate the word list an find which words are possible given the hand you have?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Even if you iterate the list, how do you compare it vs. an unarranged list? ex: hand = {'d' : 2, 'a' : 1} dictionary = {'dad': 10} Now obviously the hand can form 'dad', but I don't understand the process of rearranging the hand in order to see if it is in the dictionary.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0How did you (just now) determine that you can form 'dad' from 2 d's and 1 a?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I can form it mentally, in terms of Python I can't figure it out. I can turn hand into a list: listexample = [] for letter in hand.keys() for i in range(0, hand[letter]): listexample.append(letter) But even from there I can't figure out how to form the combinations (ie: a, b, c, ab, ac, ba, bc....) in order to test it ( 'dad' in dictionary)

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Here is my study pad by the way: http://openstudy.com/studypads/Problemset6problem34d76ce8c8c8d3a7f96f52a42

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0You don't need to form combinations. What I was trying to hint at was the notion that simply counting the number of letters that occur in a given word, and comparing that to the number of letters you have in your hand will give you sufficient criteria for determining if a word is possible.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0The number of each letter I should say.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0It doesn't seem to be the most efficient method, but here is the solution I got from your suggestion: def get_frequency_dict(sequence): # freqs: dictionary (element_type > int) freq = {} for x in sequence: freq[x] = freq.get(x,0) + 1 return freq key = {'d' : 2, 'a' : 1 } dictionary = {'dad' : 10, 'cat': 20} dictList = dictionary.keys() for i in range(0, len(dictList)): wordDict = get_frequency_dict(dictList[i]) checkWord = True for letter in dictList[i]: if wordDict.get(letter, 0) > key.get(letter, 0): checkWord = False if checkWord == True: print dictList[i], 'is in', key else: print dictList[i], 'is not in', key Thank you for your help. If you notice a more efficient way please let me know.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Couple of things. First, you can skip any words which have a score < the best word you found. Second, rather than iterate each letter in dictList[i] you can just iterate each letter/quantity in the wordDict. (this will skip duplicates as in 'dad' and 'apple') And finally, be sure to stop looking if you bestWord = '.' bestScore =0 for word in dictionary: score = dictionary[word] if score > bestScore: wordFreq = get_frequency_dict(word) isPossible = True for letter in wordFreq: qty = wordFreq[letter] if qty > hand.get(letter,0): isPossible = False break if word_is_possible: bestScore = score bestWord = word print "The best word is", bestWord, "with a score of", bestScore

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0bleh, word_is_possible should be isPossible. I changed variable names, but missed that one.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I had written something similar, but you had a couple nice efficient tweaks in there. Thanks!

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0>"""First, you can skip any words which have a(score <the best) >word you found.""" Thanks for that tip i have implemented in my code and getting good computer scores some time over 200 whereas before it never crossed 100 but now i have to change my solution to problem 4 which is efficent but is not giving good scores

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Sigh, I feel l like an idiot but I'm running into a similar problem in the very next problem. Problem 4: "First, do this preprocessing before the game begins: Let d = {} For every word w in the word list: Let d[(string containing the letters of w in sorted order)] = w After the above preprocessing step, you have a dict where, for any set of letters, you can determine if there is some acceptable word that is a rearrangement of those letters. You should put the preprocessing code into a separate function called get_word_rearrangements, analagous to get_words_to_points. ... Now, given a hand, here's how to use that dict to find a word that can be made from that hand: 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 = (string containing the letters of S in sorted order) If w in d: return d[w] " I can make an rearranged word list by doing this: def get_word_rearrangements(word_list): rearrange = {} for word in word_list: arranged = '' listarrange = [] wordDict = get_frequency_dict(word) for letter in wordDict: for i in range(0, wordDict[letter]): listarrange.append(letter) listarrange.sort() for letter in listarrange: arranged += letter rearrange[arranged] = word return rearrange However it asks for each subset S of the letters of HAND and I have no idea how to do that. Thanks for any help. Again.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I'm surprised this is part of the assignment since they've neither discussed python's builtin sets and combinatorics functions, nor the relavent set theory, but I'll try to explain how to go about this. Essentially, you can enumerate the arrangements of the letters in a string of length N by using multiples of 2 to represent the letter in each particular position. For example, the hand 'dda' has the following combinations: 'd', 'd', 'dd', 'a', 'da', 'da', 'dda' each of these subsets corresponds to the numbers 1, 2, 3, 4, 5, 6, and 7 respectively. The first 'd' corresponds to the bit for 2**0 (1), the second corresponds to the bit for 2**1 (2), and the third corresponds to the bit for 2**2 (4). So to construct all these possibilities we simply iterate from 1 to (2**31) inclusive. where each of these numbers represents an arrangement. To determine which letters are in the arrangement, we iterate each position in our 'hand' and use a bitmask to see if the bit associated to that position is 1 in our arrangement number. For example, when we arrive at the 5th arrangement, we can see that (2**0) & 5 == 1 so it has the first 'd', also (2**1) & 5 == 0, so it does not have the second 'd', and (2**2) & 5 == 1 so it has the 'a'. Therefore the 5th arrangement is 'da'. Once we have all these arrangements collected we can remove the duplicates by putting them into a unique collection called a set.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0you can also enumerate the arrangements using recursion based the idea that each letter will appear in exactly HALF of all the combinations (if you count [] as one of the possible combinations). think about the index of the list when setting up the recursion. so with a list of the possible letters ['a', 'b', 'c'] base case (len = 0) [], then [] + ['c'], then [] + ['c'] + ['b'] + ['bc'], then [] + ['c'] + ['b'] + ['bc'] + ['a'] + ['ac'] + ['ab'] + ['abc'] etc... someone else explained this recently but i didnt' understand the way they wrote it :P

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Honestly polpak, I tried my best to understand your solution, but I think it is just a bit out of my skill/knowledge range right now. I ended up using a recursive function which the complexity was 2^n, where n is the length of the hand. I'm assuming your method is more efficient, I just can't grasp it yet. Thanks for the help.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.