anonymous
  • anonymous
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.
MIT 6.00 Intro Computer Science (OCW)
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
Perhaps it'd be easier to iterate the word list an find which words are possible given the hand you have?
anonymous
  • anonymous
Even 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
  • anonymous
How did you (just now) determine that you can form 'dad' from 2 d's and 1 a?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
I 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
  • anonymous
anonymous
  • anonymous
You 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
  • anonymous
The number of each letter I should say.
anonymous
  • anonymous
It 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
  • anonymous
Couple 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
  • anonymous
bleh, word_is_possible should be isPossible. I changed variable names, but missed that one.
anonymous
  • anonymous
I had written something similar, but you had a couple nice efficient tweaks in there. Thanks!
anonymous
  • anonymous
------>"""First, you can skip any words which have a(score 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
  • anonymous
Sigh, I feel l like an idiot but I'm running into a similar problem in the very next problem. Problem 4: "First, do this pre-processing 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 pre-processing 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 pre-processing 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
  • anonymous
I'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**3-1) 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
  • anonymous
you 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
  • anonymous
Honestly 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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.