About this page....

I would like to present a programming challenge. I would like you to suggest how best to go about programming a words and letters game. I don't expect you to send me your program code, but rather suggest a programming approach to a situation - how you would go about doing something which I will present below.

Countdown

There is, here in the UK, a daily game show on television called Countdown. It's on in the early afternoon five days a week, is enormously popular, and has been running since 1982. It's a words and numbers game, featuring two contestants. It features two games: in the numbers game the contestant asks for a combination of 6 numbers, large or small. Large numbers are 25, 50, 75 or 100, and small numbers are single digits excluding zero. I think the most common choice is probably two large and four small. The contestants then get 30 seconds to combine the six numbers, using plus, minus, divide and multiply in order to reach a random 3 digit number which they will be given. No natural logarithms please!

But it's the other game which concerns us here, the word game. Contestants ask for 9 letters chosen at random from piles of cards, asking, each time, for a vowel or a consonant. They then get 30 seconds to come up with their best word using any or all of the letters. Clearly, a 9 letter word is the ultimate goal, but most players seem to manage 6 or 7 letters.

My challenge

Can you suggest a programming strategy to play the word game? The foundation is that you have a plain text file containing about 180,000 7, 8, and 9 letter words. They are not necessarily in alphabetical order. The program will ask the user to input 9 random letters and then list all the 9, 8 and 7 letter words it can find in the text file.

These are the issues to think about:

• How to make a possibly randomly-sequenced list of words into a searchable object
• How to search the list for all 9, 8 and 7 letter words contained within it. We won't bother with 6 letter words - there's usually just far too many of them to be of any interest
• The whole process must finish before the game show's thirty second clock ends

And two rules:

1. No duplicates in the result. Let's say the user input is, for the sake of argument, abcdeefff. Two e's, three f's. Logically, a program won't differentiate between e1 and e2, or f1, f2, f3, so it might find the (pretend) word 'beffced' six times! We want to see beffced just once please!
2. The results must be shown in alphabetical order, 9s first, then 8s, then 7s.

For your information

I have written a solution to this, using Python, though I'm not confining you to this language. Use anything you like; I'm only interested in the how, not the code. Pseudocode, if you like. Some screenshots of my Python program running:

The opening screen. I've just input 'regesnate'
which I know will result in some decent hits


I hit enter, and here is the result.
And yes, as you can see, there are some proper nouns there - a
nono in the real Countdown, but that's unimportant in this
exercise. It's the logic we care about.


But, most importantly of all, I'm very proud
to show you what appears last on the screen. That's just over a second.

This was run on my iMac with Intel Core i5. The same program
on my Linux Core i7 laptop runs about one third quicker. The timing
is quite closely consistent regardless of the nine letters and the hit count