Word game algorithm

Question

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.

• Robert Harvey: 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?
• Robbie Dee: Each level has to form a word.
• Robert Harvey: How about H? ...
• Robbie Dee: Slightly contentious but is oft used in poetry and rhyme...
• Robbie Dee: If it greases the wheels, just consider A and I...

Answer 1

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.

• biziclop: 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.
• Vatine: More space-efficient, for sure (you're trading an M-character string for a single character and a small-ish integer)