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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

Perhaps it'd be easier to iterate the word list an find which words are possible given the hand you have?

- 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

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

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

Here is my study pad by the way: http://openstudy.com/studypads/Problem-set-6-problem-3-4d76ce8c8c8d3a7f96f52a42

- 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

The number of each letter I should say.

- 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

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

bleh, word_is_possible should be isPossible. I changed variable names, but missed that one.

- anonymous

I had written something similar, but you had a couple nice efficient tweaks in there. Thanks!

- 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

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

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

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

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.