# Word game algorithm

Back in the days of 8-bit machines there existed an educational word game. I have no idea what it was actually called but for the sake of this question (since it involves pyramids) let's call it Stones of Giza.

The game was simple. Starting at the top level, a letter was added to a single letter word and another word was formed. A letter was then added to that word and so on down, each time making a word. The levels went from 3 to 7.

An example of level 3 might be.

``````  A
A T
B A T

Letters: AAABTT
``````

Like the 80s game mastermind, you scored for guessing a letter at a level correctly but more for guessing the position correctly.

It isn't hard to see that the only candidates for the top stone are A, I and O - since these are the only single letter words in the English language.

My question is around algorithms for sourcing game boards. My brute force algorithm currently searches for length N words with one of the 3 letters above and then checks the N-1 length word on the left/right hand side containing the pinnacle letter (A, I or O).

This strikes me as slightly inefficient since there are going to be many false searches.

How can I improve on this raw algorithm? Higher levels are taking quite a long time on a good sized dictionary.

I do of course realise that the 8-bit game probably wasn't parsing the data each time and had a set number of boards but I'm just trying to optimise creating the source data out of curiosity.

EDIT #1:

I have already filtered out words in the source dictionary that don't contain A, I or O.

• `It isn't hard to see that the only candidates for the top stone are A, I and O` -- It is for me. Why are the only candidates for the top stone A, I and O? Commented Feb 4, 2016 at 23:21
• Each level has to form a word. Commented Feb 4, 2016 at 23:31
• How about H? ... Commented Feb 4, 2016 at 23:36
• Slightly contentious but is oft used in poetry and rhyme... Commented Feb 4, 2016 at 23:47
• If it greases the wheels, just consider A and I... Commented Feb 4, 2016 at 23:48

One possibility is to (ab)use maps and sets (or lists).

You have a map with "current word" as key and "list or set of successor words" as value.

You can then populate your map using something like the following:

``````for word in dictionary:
for 0 <= position < length(word):
key = drop_letter(word, position) ## drop_letter("bath", 3) -> bat
successors[key].append(word)
``````

Of course, this would possibly require a bit more coding to take it from pseudo-code to working code.

Then you have your possible starting positions in `successors[""]` and can continue to simply pick a successor from there. If the game allows arbitrary re-arrangement of letters from one row to the next (so that "bath" is a valid successor to "tab") sort the key before using it (so the keys from "bath" would be "aht", "bht", "abh" and "abt").

Generating the initial list is amortised O(n*m) for "n words, of length max m", look-up during the game should be relatively fast.

If you do this off-line and store it in a data file, you may also be able to filter out "non-word" keys, lessening the amount of data needed in RAM.

• If letters can't be rearranged, it's probably more efficient to only store the new letter and its position rather than the entire successor word. Commented Feb 5, 2016 at 10:56
• More space-efficient, for sure (you're trading an M-character string for a single character and a small-ish integer) Commented Feb 5, 2016 at 11:12