delphi programming forums mysql charset mget recursive synonimos
free ventrilo servers hosting cs javascript delay python find in list
Back Forum New

Rank: 1
1# Jump to »
AKalairPost at 2010-2-14 07:56 | Show This Author's Posts Only
abstract:

Basically you have a hand of letters and need to get the computer to make a word from those letters that score the most points
I have the dictionary mapping the words to their point value but I dont know how I can make the computer pick the best word from my hand ?
Any Ideas ?
Thanks


Hi,
I'm currently going through MIT's open courseware course on programming and I'm stuck on this assignment:
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-00Fall-2008/BA350EF8-DA45-41D6-AEA2-B8555EE77DBE/0/pset6.pdf
(Problem 3)
Basically you have a hand of letters and need to get the computer to make a word from those letters that score the most points
I have the dictionary mapping the words to their point value but I dont know how I can make the computer pick the best word from my hand ?
Any Ideas ?
Thanks

TOP

Rank: 1
2#
mspraybPost at 2010-2-14 07:56 | Show This Author's Posts Only
You will need to assign values to the individual letters. Then the program will be able to calculate the highest possible score or value for the word.
I hope this helps.

TOP

Rank: 1
3#
dwblasPost at 2010-2-14 07:56 | Show This Author's Posts Only

  I have the dictionary mapping the words to their point value
Sort from highest to lowest point value, and then find the first word that has all of it's letters in the list of letters you were given.

TOP

Rank: 1
4#
AKalairPost at 2010-2-14 07:56 | Show This Author's Posts Only
Hi,
Thanks for the replies, so say for example I have the following hand:
{a:1, b:1, t:1}
(The actual hand in the game has 7 letters but this is simpler for an example)
Now for a human its obvious you can make either 'bat' or 'tab' or 'at'
But how can I get the computer to make either of those words?

TOP

Rank: 1
5#
mspraybPost at 2010-2-14 07:56 | Show This Author's Posts Only
abstract:

Basically you have a hand of letters and need to get the computer to make a word from those letters that score the most points
I have the dictionary mapping the words to their point value but I dont know how I can make the computer pick the best word from my hand ?
Any Ideas ?
Thanks



Originally Posted by AKalair
Hi,
Thanks for the replies, so say for example I have the following hand:
{a:1, b:1, t:1}
(The actual hand in the game has 7 letters but this is simpler for an example)
Now for a human its obvious you can make either 'bat' or 'tab' or 'at'
But how can I get the computer to make either of those words?
You will have to create a file with all available words that can be used given the letters. Then you will need to create a function that compares the words to database and available letters in hand.

TOP

Rank: 1
6#
tdennistPost at 2010-2-14 07:56 | Show This Author's Posts Only
Finding all of the different letter permutations (combinations I guess) that form English words is an interesting task.  I did something similar a while ago.  The way I solved it was to use a dictionary file.  Then, in several steps:
- Filter out all of the words that are != to the number of letters you have (length filter)
- Sort the letters in your hand in alphabetical order
- For each word in your filtered dictionary file, sort the letters in alphabetical order and compare.
For your example, you would end up with a dictionary file with a ton of 3-letter words.  Your sorted hand is 'abt'.  Then, when you loop through the dictionary, 'bat' would be sorted into 'abt' so that's a match; 'tab' would be sorted into 'abt' so that's another match; etc.
This is obviously a pretty inefficient algorithm, but it will get you on the right track I think.
As for finding the subwords ('at'), I'll leave that as an exercise for the reader (mostly because I'd have to think about it a while!).
Hope this helps.

TOP

Rank: 1
7#
dwblasPost at 2010-2-14 07:56 | Show This Author's Posts Only
You can use combinations in itertools http://docs.python.org/library/itertools.html to give the letter combinations for 2 lettters, then 3 through 7 letters, and check those against words sorted on letters.  You could use permutations and not sort the words you compare to, but that is many, many more lookups since abc would yield one sorted lookup, but you would have to look up 'abc', 'acb', 'bac', 'bca', 'cab', and 'cba' if you use unsorted.  I don't know the math to calculate this difference for 1 through 7 letters but a guess would be somewhere between 5000-6000 more lookups.  It of course depends on the number of words you are comparing to.  Start with looking up one, known word, time it, and then find a way to pass all possible words to this function and make some guesses as to which way will take an acceptable amount of time.



Basically you have a hand of letters and need to get the computer to make a word from those letters that score the most points
I have the dictionary mapping the words to their point value but I dont know how I can make the computer pick the best word from my hand ?
Any Ideas ?
Thanks

TOP

Back Forum