wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> CHORNICLE GAME ...
        
(Message started by: coolnfundu on Nov 10^th, 2004, 9:42pm)

Title: CHORNICLE GAME ...
Post by coolnfundu on Nov 10^th, 2004, 9:42pm

The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is.

Imagine that a scrambled word is 5 characters long:

How many possible solutions are there?
What if we know which 5 letters are being used?
Develop an algorithm to solve the word.

Title: Re: CHORNICLE GAME ...
Post by towr on Nov 11^th, 2004, 12:56am

on 11/10/04 at 21:42:30, coolnfundu wrote:

How many possible solutions are there?

::[hide]Much less than 26⁵, because most letter combinations are disallowed, and even of those that could be words most won't be. At most a few thousand will be actual words.[/hide]::

Quote:

What if we know which 5 letters are being used?

::[hide]less than 120, probably only a few dozen.[/hide]::

Quote:

Develop an algorithm to solve the word.

::[hide]Preprocessing: Take a dictionary with all 5 letter words, for every word make a key existing of the sorted letters of the word. Sort (lexically) dictionary by key
Lookup: Sort the given letters, do binary search to find all anagrams[/hide]::

Title: Re: CHORNICLE GAME ...
Post by jgoemat on Apr 26^th, 2005, 8:30pm

Quote:

How many possible combinations? What if we know which 5 letters are being used?

If you are using all five letters, then there are 5 possible choices for the first letter, 4 for the second, 3 for the third, and 2 for the fourth, so that would be 120. It ends up being n!. If any letters are duplicates, then there are fewer. I think it would go down by d! for each duplicate. For instance, if you have AABCD, that would be 5!/2!. If you have AAAAD, that would be 5!/4! (or 5). If you have AABBB, that would be 5!/2!/3! (or 12).

I don't know of a formula to figure out all possible combinations of any letters, but for x letters, the possible combinations for words of length y is x!/(x-y+1)! I don't know how to account for duplicate letters in that...

Quote:

Develop an algorithm to solve the word.

I've written a web page to do word searches at http://www.jasongoemaat.com/WordSearch. If anyone is interested, I can send the code. It uses the enable word list from http://www.puzzlers.org/wordlists/.

What I did was sort the characters of each word by letter, then sort the results. Then when checking for a certain letter combination I sort those letters and do a binary search to find the letters and get the actual words from the list.

To find multiple words given multiple letters, I just try every possible combination. I sort the letters, then put them in arrays with letters and counts. Then I step through for each letter and add each possible count of that letter to a string (including 0) to a string and move to the next letter. For each combination after the last letter, I add it to a list. When done with that I to a search for each letter combination I created.

Title: Re: CHORNICLE GAME ...
Post by madhuri on Mar 28^th, 2012, 10:44am

can u xplain me clearly abt d pgm

Title: Re: CHORNICLE GAME ...
Post by Grimbal on Mar 29^th, 2012, 9:14am

Probably not. Jgoemat made 3 posts 7 years ago...

Title: Keith Gilabert, "CHORNICLE GAME ...&quo
Post by keithgilabert on May 13^th, 2012, 8:18pm

Can you send me info on the word?

Keith Gilabert

Title: Re: CHORNICLE GAME ...
Post by jordan6 on May 29^th, 2012, 5:02am

Are you serious? developing an algorithm to guess a word from scramble letters sounds like an assignment for the military...

Title: Re: CHORNICLE GAME ...
Post by Grimbal on Sep 12^th, 2012, 12:48am

There are plenty of anagram generators.

You enter a sentence or a set of letters and it returns sets of words that contain the same letters. If you set it to 1 word only, it should return the possible words for the letters.