Anagram finder

BlitzMax Forums/BlitzMax Beginners Area/Anagram finder

Matt Vinyl(Posted 2007) [#1]
Afternoon all...

I working on a simple word game, whereby you have a set time limit and have to find as many 'real' words as possible within a given number of letters (generally 8-12, depending on difficulty). A word of the total given length will be chosen at the start of each round, and the player presented with the 8-12 letters scrambled.

What I'm struggling with, is how to go about checking how many 'real' words can be formed from the initial word. Here's what I'd have to work with:

SelectedWord$="ALUMINIUM"

Then, I guess I'd need to 'divvy' up the individual letters and park them up in an array, using MID & LEN commands etc.

Now, here's the part I'm stuck on: How do I establish how many 3/4/5/6/7/8/9 words can be made from the word ALUMINIUM (in this example)? I have a text dictionary file that can validate the words, but am unsure of the algorithmn I'd need to initially get the word list.

Has anyone tried and succeeded with anything similar?

Cheers!


GfK(Posted 2007) [#2]
How many words are in your dictionary? Is speed important, i.e. are you checking words 'on the fly', or doing a pre-game search for all valid words?


Yan(Posted 2007) [#3]
Have I already given you this link?


tonyg(Posted 2007) [#4]
Looks for dictionaries which are split in seperate lists depending on word size plus a single HUGE list. They make it so much easier to
check (especially if you're writing something like CountDown).
I can only think of a brute force method of perming every letter to all the others. However, you can leave the check quite early in most cases
i.e. if a word doesn't exist with 'MM' at the beggining then you don't need to check any further with MMa, MMb etc.


semar(Posted 2007) [#5]
Hi,
I think that your question is quite difficult to answer to.

Due of the nature of anagrams, you may find out that with a simple word of 9 letters you can generate lots of letter and word combinations.

What I suggest you, is to solve this problem from another point of view.

An hint I give you, is a simple way to check if the user has typed an anagram of a word; the simplest way is to use a dictionary made of "base anagrams".

I try to explain this concept with an example of what I mean.

Let's take the word: CAR.

An anagram of the word CAR is: ARC.

How we check that ARC is an anagram of CAR ?

Well, let's build the base anagram of the word CAR, which is made in this way: we build a string with all the characters composing the word, and sort them alphabetically:

So:
CAR is composed by C,A, and R, which sorted generates: ACR

and in the same way:
ARC is composed by A,R, and C, which sorted generates: ACR

As you see, ARC and CAR generate the same base anagram: ACR.

In this way we can check if a word is an anagram of another word, by simply checking if the base anagram of a word matches the other ones.

Now, if you have already a word dictionary, would be easy to build up a base anagram dictionary too.

That way, when the player type a sentence, you may simply:
- build a base anagram for each word, and check if it exists in your base anagram dictionary (or check the word in the normal dictionary of course) and then
- build a string with all the base anagrams sorted. Now, if this string has the same base anagram of the initial given word, that means that the player has made a valid anagram.

Example with ALUMINIUM. Let's say that the player writes the sentence:
MAUL IN MUI
and let's think that this sentence is a valid english syntax.

So, the 3 words together generate a base anagram of:
( ALMU + IN + IMU = ALMUINIMU) which sorted gives:
AIILMMNUU

Now, if you take the word ALUMINIUM and build up its base anagram, you will find also:
AIILMMNUU

The two base anagram matches ! That means, the player has typed a valid anagram :)

Hope it helps,
Sergio.


Matt Vinyl(Posted 2007) [#6]
Hi (I did post a similar topic elsewhere, but that was more to do with checking through the dictionary in 'real time' (which I've now solved!).

Thanks for all your advice - I'll sit back and give it a try.

Essentially, in this case, realtime checking is not necessary, as it can be done whilst the level loads.

:)