## Conundrometer Game

6th June 2014

This article describes a pocket anagram game I designed recently to help my son improve his anagram-solving skills. It is based on the conundrum game, which forms the final challenge in the Channel 4 TV series Countdown, in which the contestants have to solve a nine-letter anagram within 30 seconds.

My Conundrometer contains a complete list of nine-letter words, and displays an anagram of a random word on the display. A timer then gives you 30 seconds to solve the anagram. When you've solved it you press a button and the answer is displayed. If you answered it within 30 seconds you score a point.

### How it works

The Conundrometer works as follows. When you press the red button it displays an anagram, and a bar showing how much of the 30 seconds you've got left:

If you've worked out the answer you press the red button, and a cursor is displayed to allow you to enter your guess:

The red button moves the cursor and the green button copies letters down into the second row.

If your answer is correct you score a point, and your percentage score so far is displayed:

If you fail to guess the anagram in time, or guess wrong, the program displays the answer. Pressing the red button then displays the next anagram.

### Programming the Conundrometer

I developed the program on an Arduino Uno before building the circuit on a small breadboard using an ATmega328. My starting point was a word list of 8680 nine letter words. For example, the first eight words are:

"aardvarks" "abandoned" "abasement" "abatement" "abattoirs" "abdicated" "abdicates" "abdominal"

A quick calculation shows that storing these as standard C strings would require at least 8680×9 bytes, or about 78Kbytes, well over the 32Kbytes available in the ATmega328. It was clear that some sort of compression method was needed to fit them in.

Since the words only require the letters A-Z there is no need to use a full byte to store each letter; you can specify 26 letters with a 5-bit number. You can therefore pack a nine-letter word into 5×9 or 45 bits, which is 6 bytes. This reduces the requirements to 8680×6 bytes, or about 52Kbytes, unfortunately still too much.

### Storing differences

The breakthrough came from the idea of storing the differences between successive words. To illustrate how this works consider the first two words in the wordlist, "aardvarks" and "abandoned". Coding each of these as five bits per character we end up with the decimal numbers:

18376312146 and 34799563907.

The difference between these is 16423251761 which can be fitted in 34 bits.

One problem of this approach is that to find any word we have to start at the beginning of the list, and sum successive differences until we get to the word we want. In practice this took less than half a second in the worst case, an acceptable delay.

I came up with a storage method that used a variable number of bytes to store the differences. Each difference was divided into 7-bit chunks; this was output as a sequence of bytes, where the top bit was 0 to indicate that there were more chunks, or a 1 to indicate that this was the last chunk. This reduces the wordlist to within the 32Kbyte limit, but with very little room to spare for the program.

Finally, on a hunch I tried the same technique with each word reversed, so for example, the first eight words in the wordlist are now:

These are the words "harmonica", "enchilada", etc. This reduced the memory requirement by about 2Kbytes! Presumably this is because the differences are more evenly distributed.

I wrote an external program to encode the wordlist as the appropriate series of differences, and output the bytes in a form that could be cut and pasted into the Arduino IDE. Here are the first few lines:

```PROGMEM prog_uchar diffs[] = {
2, 33, 87, 25,  8,135, 95, 92,117, 11,157, 50, 84, 78, 77,232, 63,107, 72,133,
27, 87, 90, 94,240, 73, 47,127, 22,134,  4, 72, 58, 77,191, 26, 96,  5, 22,189,
3, 84, 89, 60, 97,191, 11, 94,  4, 61,203,  3,114,192,  5, 11,125,119,248, 13,
77, 43, 93,193,  3,119,111, 39,134, 62, 85, 16,255,  3, 70,  7,109,132,  1, 75,
121, 75,253, 20, 17, 73,163, 14, 34, 52, 72,152,115,124,203, 63,119, 63,240,  1,
```

The complete set of data is included in the full listing at the end of this post.

### Unpacking the wordlist

There are three key routines used in this application. First FindWord() finds the nth word in the wordlist:

```// Find word n in wordlist, 0 <= n <= 8680
void FindWord(int n) {
unsigned int p = 0;
unsigned char diff;
unsigned long GapH, GapL;
WordL = 0;
WordH = 0;
for (int i=0; i<n; i++) {
GapH = 0;
GapL = 0;
do {
GapL = GapL<<7 | (diff & 0x7f);
GapH = GapH<<7 | (GapL>>24 & 0xFF);
GapL = GapL & 0x00FFFFFF;
} while (diff < 0x80);
WordL = WordL + GapL;
WordH = WordH + GapH + (WordL>>24);
WordL = WordL & 0x00FFFFFF;
}
}
```
It sets up the word, encoded as 5 bits per character (0 = a, 1= b, etc) in the bottom three bytes of WordH and WordL. FindWord(1) is "HARMONICA" and FindWord(8680) is "KILOHERTZ".
DecodeWord() unpacks the characters from WordH and WordL, and puts them into Conundrum[0] to Conundrum[8]:
```void DecodeWord() {
unsigned char Nibble;
unsigned long TempH, TempL;
for (int c=0;c<9;c++) Conundrum[c] = 'A';
TempH = WordH;
TempL = WordL;
for (int i=0;i<9;i++) {
Nibble = TempL & 0x1F;
Conundrum[i] = Conundrum[i] + Nibble;
TempL = TempL>>5 | (TempH & 0x1F)<<19;
TempH = TempH>>5;
}
} ```

Finally MakeScramble() is used to create an anagram of the word in Conundrum[0] to Conundrum[8] and put it in Scramble[0] to Scramble[8], by performing 9 random swaps of pairs of letters:

```void MakeScramble () {
int i=0;
int j;
unsigned char temp;
for (int c=0;c<9;c++) Scramble[c] = Conundrum[c];
for (int c=0;c<9;c++) {
j = (1 + i + random(8)) % 9; // 1 to 8
temp = Scramble[i];
Scramble[i] = Scramble[j];
Scramble[j] = temp;
i = j;
}
}```

### Hardware

The Conundrometer is built on a small breadboard using an ATmega328. The push buttons were stuck to the edge of the breadboard using Sticky Fixers:

The Conundrometer uses a 16x2 LCD display [1] which fits on top of the components, and it uses the LiquidCrystal library to drive it. The outputs chosen to drive the display were mainly selected to make the wiring easier on the breadboard.

I used an ATmega328 chip with the default fuse settings, which gives an internal 1MHz clock and avoids the need for a crystal. I uploaded the program to the ATmega328 using Sparkfun's Tiny AVR Programmer [2] (available in the UK from Proto-PIC [3]).

The whole circuit is powered by a 50mAH rechargeable lithium battery; I use the HobbyTronics LiPo charger  [4] to charge it. There's no on/off switch; instead the program puts the ATmega328 to sleep if no button is pressed for 15 seconds. The display is powered from one of the ATmega328 outputs, so the display can be turned off by the program. This reduces the current consumption from about 40mA to a standby current of just 120nA.

Here's the whole program for the Conundrometer: Conundrometer Program.

1. ^ 16x2 LCD Display White/Blue LED Backlight from HobbyTronics
2. ^ Tiny AVR Programmer on Sparkfun
3. ^ Tiny AVR Programmer on Proto-PIC
4. ^ USB LiPo Battery Charger from HobbyTronics