Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

saulnierpr Group Title

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

  • one year ago
  • one year ago

  • This Question is Closed
  1. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • one year ago
  2. michaelokt Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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).

    • one year ago
  3. saulnierpr Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • one year ago
  4. mwiegant Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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!

    • one year ago
  5. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • one year ago
    • Attachments:

See more questions >>>

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.