## Countdown

On British TV in the afternoon on weekdays there is a show that has been running for many years. Countdown is a word and numbers game played between two people. The game is a mental challenge that viewers at home can also participate in. I enjoy doing this from time to time, but I also decided that I was going to write a computer program to solve the puzzles. This article provides the C source code for my countdown solving programs.

## Letters Game

There are 2 distinct games that are played on the Countdown show. The first is the Letters game. In this game one of the contestants chooses 9 letters. For each letter they can specify whether it should be a vowel or a consonant, and then they are given a random letter of that type (taken from the top of a pile of cards). Players usually choose 3 or 4 vowels and the rest consonants.

Once the letters are selected both players have 30 seconds (the Countdown timer) to find the longest word they can that uses the letters from the selection chosen. Each letter can only be used once to do this, so the maximum is a 9 letter word.

My program to solve this problem is shown below. You will need a file of words for the program to access. Although it is very tempting to include my word database of 174785 words in this article to earn myself a nice stash of devcoins, I think the most reasonable thing is to advise you that a list of words is easily obtainable in the internet. I found the following link http://www-01.sil.org/linguistics/wordlists/english/ for example. If you are running on a UNIX system you may find there is already a dictionary of words installed which you could configure the program to use.

The mechanism the program uses is quite simple. Using qsort, the letters which constitute every single word in the dictionary is sorted into alphabetical order. So for example

``` Bad => abd
Bed => bde
Amazing => aagimnz```

The set of letters we are looking to find a long word from are also sorted in this way. Then we need to check that the letters from our sorted dictionary word appear in the same order as the letters of our sorted input.

The program is as follows. Please note that to satisfy the formatting requirements of the wiki I have had to use &lt; in place of < and &gt; instead of > in various places. If you edit the page to take a copy of the code you will need to do a global replace to revert this in the resulting source code. I am also unable to replicate the line of code which opens the file of dictionary words inside the code block. I cannot tell what it is about this line, but it breaks the wiki which then just hangs when it is submitted.

So where you see

`fp = fopen ...   // trouble with wiki syntax here`

you will need to create the correct fopen declaration referencing your dictionary file of words. You need to open the file read only.

```#include <stdio.h>

#define MAXSTRING 1024

int sortItOut(char *a, char *b)
{
if (*a < *b)
return -1 ;
if (*a > *b)
return 1 ;

return 0 ;
}

// returns 0 if they dont match, or the length if they do
compare (char *a, char *b, int len)
{
int i, j, pos ;
char    *ptr ;

int (*sortfn)() = sortItOut ;

ptr = (char *) strchr (a, (int)'\n') ;
if (ptr)
*ptr = '\0' ;

if (strlen(a) > len)
return (0) ;

qsort (a, strlen(a), sizeof(char), sortfn) ;

pos = 0 ;
for (i=0;i < strlen(a);i++)
{
for (j=pos; j < len; j++)
{
pos++ ;
if (a[i] == b[j])
break ;
}
if (j == len)
return (0) ;
}

return (strlen(a)) ;
}

main (int argc, char **argv)
{
int     i ;
FILE    *fp ;
int     len ;
int     all = 0 ;
int     maxlen = -1 ;
int     minlen = 3 ;
char letters [MAXSTRING ] ;
char dict [MAXSTRING ] ;
char dictcpy [MAXSTRING ] ;
char reqletters [ MAXSTRING ] ;
int (*sortfn)() = sortItOut ;

if (argc < 2)
{
printf ("Usage: letters <list of letters> <printAll>\n");
exit (0) ;
}

strcpy (letters, argv) ;

if (argc > 2)
{
all = 1;
minlen = atoi (argv) ;
}

reqletters = '\0' ;
if (argc > 3)
{
strcpy (reqletters, argv) ;
}

qsort (letters, strlen(letters), sizeof(char), sortfn)  ;

fp = fopen ...   // trouble with wiki syntax here
if (!fp)
exit  (-1)  ;

while (fgets (dict, MAXSTRING, fp))
{
strcpy (dictcpy, dict) ;
len = compare (dictcpy, letters, strlen(letters)) ;
if (len && (len >= minlen || len >= 7))
{
if (all)
printf ("%s", dict) ;

if (len >= maxlen)
{
maxlen = len ;
if (!all)
printf ("%s", dict) ;
}
}
}

fclose (fp) ;
}```

## Letters example

Here is an example of the program at work

```% ./letters urciennas
ace
aces
acinus
ancien
anciens
aneurin
arcsine
arsenic
canines
canners
cannier
carnies
crannies
insurance
./letters urciennas  0.07s user 0.00s system 96% cpu 0.078 total```

Computers are amazing aren’t they? The program had to trawl through 175000 words in my dictionary, doing the sorting and comparison operations, and in this case the total execution time on my 12 year old laptop running Centos 5 was 0.078 seconds.

Please note that although in the Countdown game there are only ever 9 letters, there is no such restriction on this program. This means you can use it to solve any anagram.

```% ./letters ssnoitarntttainabu
aaa
aaas
abasia
abatis
abator
abattoir
abattoirs
abrasions
anabiosis
annuitant
annuitants
arabisation
instauration
substantiation
transubstantiation```

## Numbers Game

In the numbers game, one of the contestants is asked to choose 6 numbers. These can be up to 4 “large” numbers and the remainder are small numbers. Large numbers are either 25, 50, 75 or 100 and small numbers are in the range 1 to 9.

A random 3 digit number is then generated and the objective is to combine the chosen set of numbers using the operations of addition, subtraction, multiplication and division in such a way as to end up with the random target. You do not need to use all the numbers, but you can use each number only once.

I was unable to think of a good procedural way of solving this problem, so I decided to write a program that would come up with the answer by brute force. Basically the program just tries, at random, the various operations that are allowed, and usually will come up with an answer within about 100,000 iterations (that is if a solution is available, which is not the case every time).

Here is the code of the program.

``` #include <stdio.h>
#include <sys/time.h>

#define NUMNUMS 6

#define SUB 1
#define MULT 2
#define DIV 3

#define MAXSTRING   1024

int num[NUMNUMS] ;
int copy[NUMNUMS] ;
int sort[NUMNUMS] ;
int target;
char desc[MAXSTRING+1] ;

shuffleSort(int level)
{
int i,pos,tmp ;

for (i=0;i<level; i++)
{
sort[i] = i ;
}

for (i=0;i<level; i++)
{
pos = random() % level ;
tmp = sort[i] ;
sort[i] = sort[pos] ;
sort[pos] = tmp ;
}
}

setupCopy (int aloop, int pos1, int pos2, int val)
{
int curpos = 0 ;
int i ;

for (i=0;i<aloop;i++)
{
if (i == pos1 || i == pos2)
continue ;
copy[curpos] = copy[i] ;
curpos++ ;
}
copy[curpos] = val ;
}

int main (int argc, char **argv)
{
int i, aloop, val ;
int total, totsav, oldTotal;
int diff ;
int nearest;
int numtries;
struct timeval  tv ;
struct timezone tz ;
char descsav[MAXSTRING+1] ;

if (argc < 8)
{
printf ("Usage: numbers <num1> <num2> <num3> <num4> <num5> <num6> <target>\n") ;
exit (0) ;
}

gettimeofday (&tv, &tz) ;
srandom(tv.tv_usec) ;

for (i=0;i<NUMNUMS;i++)
{
num[i] = atoi (argv[i+1]) ;
}
target = atoi (argv[NUMNUMS + 1]);

nearest = 10000 ;
numtries = 0 ;

while (1)
{
for (i=0;i<NUMNUMS;i++)
{
copy[i] = num[i] ;
}

desc = '\0' ;
for (aloop=NUMNUMS; aloop > 1; aloop--)
{
shuffleSort (aloop) ;
val = operation (sort, sort) ;
diff = abs (val - target) ;
if ((val > 0) && diff < nearest)
{
nearest = diff ;
strcpy (descsav, desc) ;
totsav = val ;
if (!diff)
{
printf ("GOT IT!!(%d tries)     %s \n", numtries, desc) ;
exit(0)  ;
}

}
setupCopy (aloop, sort, sort, val) ;
}

numtries++ ;

if (numtries > 1000000)
{
printf ("NEAREST %d - %d away       %s  \n", totsav, abs(totsav - target), descsav) ;
exit(0) ;
}
}
}

int operation (int pos1, int pos2)
{
int icalc ;
int op ;

while (1)
{
op = random() % 31;
if (op < 10)
{
icalc = copy[pos1] + copy[pos2] ;
sprintf (desc, "%s\n %d + %d = %d", desc, copy[pos1], copy[pos2], icalc) ;
return (icalc) ;
}
else if (op < 20)
{
if (copy[pos1] > copy[pos2])
{
icalc = copy[pos1] - copy[pos2] ;
sprintf (desc, "%s\n %d - %d = %d", desc, copy[pos1], copy[pos2], icalc) ;
return (icalc) ;
}
else
{
icalc = copy[pos2] - copy[pos1] ;
sprintf (desc, "%s\n %d - %d = %d", desc, copy[pos2], copy[pos1], icalc) ;
return (icalc) ;
}
}
else if (op < 30)
{
// multiplying by 1 is pointless
if (copy[pos1] == 1 || copy[pos2] == 1)
continue ;
icalc = copy[pos1] * copy[pos2] ;
sprintf (desc, "%s\n %d * %d = %d", desc, copy[pos1], copy[pos2], icalc) ;
return (icalc) ;
}
else
{
double dtot ;
double dnum ;
double dcalc ;

// dividing  by 1 is pointless
if (copy[pos1] == 1 || copy[pos2] == 1)
continue ;

dtot = (double) copy[pos1] ;
dnum = (double) copy[pos2] ;

dcalc = dtot / dnum ;
icalc = (int) dcalc ;
if (dcalc == (double) icalc)
{
sprintf (desc, "%s\n %d / %d = %d", desc, copy[pos1], copy[pos2], icalc) ;
return (icalc) ;
}
}
}
}```

## Numbers Results

Here are some examples of the program being used. The 6 chosen numbers are the first 6 arguments to the program and the final argument is the required total. In this first example it took 2908 iterations to come up with a solution.

``` % ./numbers 25 3 3 5 7 8 624
GOT IT!!(2908 tries)
25 + 3 = 28
8 * 3 = 24
5 + 7 = 12
28 + 24 = 52
52 * 12 = 624```

Because of the random nature of the program, if you try it again you may well get a different result. The result here was found very quickly.

``` % ./numbers 25 3 3 5 7 8 624
GOT IT!!(144 tries)
3 * 25 = 75
3 + 75 = 78
8 * 78 = 624```

But the answer is not always so easy to find. The example below took over 70000 iterations before an answer was found.

``` % time ./numbers 25 3 3 5 7 8 687
GOT IT!!(70949 tries)
25 + 8 = 33
5 - 3 = 2
33 * 7 = 231
231 - 2 = 229
3 * 229 = 687
./numbers 25 3 3 5 7 8 687  0.19s user 0.00s system 98% cpu 0.195 total```

Notice, however, that even though it took a large number of iterations to get tot he solution, it still only took 0.195 seconds, so the countdown 30 second timer is not a threat!

## Target

Although it is not part of the Countdown program, there is a game with some similarities to the Letters game that can be played in the Daily Express newspaper – called the Target. 9 letters are provided, and the idea is to form as many words of letters or more as you can out of the letters provided. Each letter can only be used once and there is 1 particular letter which has to appear in every word. There is always a nine letter word.

We only need a small modification to the letters game program to handle this. Here is the code

```#include <stdio.h>

#define MAXSTRING 1024

int sortItOut(char *a, char *b)
{
if (*a < *b)
return -1 ;
if (*a > *b)
return 1 ;

return 0 ;
}

// returns 0 if they dont match, or the length if they do
compare (char *a, char *b, int len, char compulsary, int minlen)
{
int i, j, pos ;
char    *ptr ;

int (*sortfn)() = sortItOut ;

ptr = (char *) strchr (a, compulsary) ;
if (!ptr)
return (0) ;

ptr = (char *) strchr (a, (int)'\n') ;
if (ptr)
*ptr = '\0' ;

if (strlen(a) > len)
return (0) ;

qsort (a, strlen(a), sizeof(char), sortfn) ;

pos = 0 ;
for (i=0;i < strlen(a); i++)
{
for (j=pos;j < len;j++)
{
pos++ ;
if (a[i] == b[j])
break ;
}
if (j == len)
return (0) ;
}

if (strlen(a) < minlen)
return (0) ;

return (strlen(a)) ;
}

main (int argc, char **argv)
{
int     total = 0 ;
FILE    *fp ;
int             len ;
int             minlen = 4 ;
char letters[MAXSTRING] ;
char dict[MAXSTRING] ;
char dictcpy[MAXSTRING] ;
char reqletters[MAXSTRING] ;
int (*sortfn)() = sortItOut ;

if (argc < 3)
{
printf ("Usage: target   \n");
exit(0) ;
}

strcpy (letters, argv) ;
char mandatory = *argv ;

if (argc == 4)
minlen = atoi (argv) ;

qsort (letters, strlen(letters), sizeof(char), sortfn) ;

fp = fopen // trouble with wiki syntax here
if (!fp)
exit (-1) ;

while (fgets (dict, MAXSTRING, fp))
{
strcpy (dictcpy, dict) ;
len = compare (dictcpy, letters, strlen(letters), mandatory, minlen) ;
if (len)
{
total++;
printf ("%s", dict) ;
}
}

printf ("Total words: %d\n", total) ;

fclose (fp) ;
}```

## Target Results

Here is an example of using the Target program. You specify the 9 letters as the first argument to the program and the compulsory letter as the second argument.

```% ./target reiedovvr o
dero
devoir
doer
dover
drove
drover
erode
ideo
order
oreide
over
overdrive
overed
override
redo
reord
revivor
revoir
rode
roed
rove
roved
rover
video
vireo
vivo
void
voider
voir
Total words: 29
./target reiedovvr o  0.04s user 0.00s system 92% cpu 0.050 total```

Again, as you can see, the runtime for this utility is tiny.  