2

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? – Robert Harvey Feb 4 '16 at 23:21
  • Each level has to form a word. – Robbie Dee Feb 4 '16 at 23:31
  • How about H? ... – Robert Harvey Feb 4 '16 at 23:36
  • 1
    Slightly contentious but is oft used in poetry and rhyme... – Robbie Dee Feb 4 '16 at 23:47
  • 1
    If it greases the wheels, just consider A and I... – Robbie Dee Feb 4 '16 at 23:48
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.

| improve this answer | |
  • 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. – biziclop Feb 5 '16 at 10:56
  • More space-efficient, for sure (you're trading an M-character string for a single character and a small-ish integer) – Vatine Feb 5 '16 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.