## saulnierpr 2 years ago Did anyone else find the computation time for ps3b to be unreasonably long? As in, 20+ seconds on recent hardware/100% cpu?

1. bwCA

how did you implement it? for a seven letter hand, you need to test for valid words using permutations of 1, 2, 3, 4, 5, 6 and 7 of the hand's letters. the number of permutations for each of those is n!/(n-k)!. 7!/6! + 7!/5! + 7!/4! + 7!/3! + 7!/2! +7! +7! = 13699 depending on how you implemented your search through the word list, it could get time consuming. there are ways to optimize. this is for the 2011 SC class? or 2008? http://en.wikipedia.org/wiki/Permutations#In_combinatorics

2. michaelokt

the part where it loads the words might take 2,3 seconds. the rest is pretty quick on my machine (my machine is kind of old and slow).

3. saulnierpr

Spring 2011. Here's my implementation, omitting declarations: for n in reversed(range(0,HAND_SIZE+1)): #print n for w in get_perms(hand,n): if is_valid_word(w,hand,word_list): current = get_word_score(w,HAND_SIZE) if current > highscore: highscore = current bestword = w So, it runs the inner loop 13699 times, via seven trips through the outer loop, then for each execution of the inner loop checks against 83k words, which is in the neighborhood of a billion executions of get_word_score alone. I imagine that there's a much better way to do this.

4. mwiegant

I also ran into this problem saulnierpr, using almost identical logic to yours. I have a solution that might work for me, because of the way I performed my implementation, but it involves only looking at every 1 of X permutations and so results in a smaller amount of permutations for the program to analyze. Currently, once my program has all the valid words, it chooses one at random and plays it. Because I already have this element of randomization, I feel like I could get away with looking at 1 of every X available permutations. However, the flaw with doing this is that there is a chance that the program will skip all the permutations that ARE valid words won't find any permutations that actually work, even if in actuality there are 10 or 20 that would.. On another train of thought, maybe it would be possible to look at each permutation and filter it out of the program if it didn't contain at least 1 vowel and 1 consonant. By the basic logic of the program, you have thousands of permutations to go through, but each one also has to go through thousands of entries in the word list looking for any match to a word. If you could filter out entries from ever even reaching the part of the loop where you compare them to the word list, you might be able to save time. In summary, I think the solution to this problem involves figuring out a way to avoid looking at some of the entries and/or figuring out a way to avoid having to compare every possible permutation to the word list. Try to think back to the logic of the third problem of problem set 1 :) I hope this was helpful!

5. bwCA

if you look at this problem in the 2008 course, it has a couple of more variations. one is to create a points dictionary {word:points} when loading the words - then checking a letter sequence for validity becomes a constant time operation. the second iteration is to create another dictionary with the key being the sorted letters of the word and the value being the word {sortedword : word}. this allows you to check sorted letter combinations of hand instead of permutations - e.g. you only have to check for the sequence abc instead of abc, bac, bca, cba. the number of sequences becomes n! / k!(n-k!) for k = 1 to n which is 127 for a seven letter hand http://en.wikipedia.org/wiki/Combinations