How to Create a Word Unscrambling Program?

[Hybr!d]

Hello Guys.

I was wondering how would you go around making an application that unjumbles words. It uses a wordlist and extracts the unjumbled word like.

jumbled: ial
unjumbled:ali

I hope someone got an idea. Thanx

 

[jim mcnamara]

Here is a start in C:

word list:

char wordlist[4][8]={"all", "some", "small", "sine"};
char alpha[4][10]={0x0};

wordlist has four elements: each word we know how to unscramble
alpha is an alphabetically arranged set of characters from wordlist:
wordlist alpha
all all
some emos
small allms
sine eins

The algorithm is:

input a scrambled word
lowercase all the letters in the word
alphabetize the letters in the scrambled (just like we did for "alpha" above)
search thru each element of alpha to find an exact match
print the corresponding element in wordlist -
  i.e., if you find an exact match with "emos" print "some"
  else printf "not found in list"

 

[chroot]

mcnamara's onto a good start, but don't try to store all those words in memory!

First, sort the letters in the target word. Read the words from the word list (a text file) one at a time, sort the characters, and compare with the sorted target word.

- Warren

 

[berkeman]

An even faster way would be to count the letters in the word and add up the ordinal of all the letters (1=a, 2=b, etc.). Then match the number of letters and total ordinal sum against your word list (where you've already computed these two numbers for each word, and sorted numerically), and then try permutations of your test word against the matched words from your word list. Should take the search from order(N) down to order(log[N]) or less, I would think...

 

[chroot]

berkeman,

There are a ton of different ways one could optimize this for run-time performance, particularly by storing pre-computations like the one you described.

- Warren

 

[Hybr!d]

Thanx guys. I got a start