The British Informatics
Olympiad isthe computing competition for schools and colleges. We are proud to present BIO'98. |

**The 1998 British Informatics
Olympiad exam**

**Solution to Question 3:
Alphametics (Cryptarithms)**

- Example solution program viewable in a Java-enabled browser
- Question statement
- Index of BIO'98 exam
- Index of BIO'99 sample paper

**3 (a) [24 marks].** *Write a program which
solves addition alphametics. Your program should first accept a
number n, between 3 and 6 inclusive, which will indicate the
number of lines to follow. The following n lines will each
contain a word of no more than 10 characters. The alphametic to
be solved is the sum of the first n-1 words, to total the final
word*.

Alphametics are quite common brainteaser questions. They can usually be solved by hand in a methodical way by building up sets of constraints and using these to narrow down on a solution. The task in this question is to write a program to do the process automatically. We will consider two different approaches.

**Brute force**

A basic approach to the problem would be to try all possible number combinations, checking if a solution had been found for each. In the worst case of 10 unknown characters, this would give 10! = 3,628,800 different permutations to check. This means that an inefficient solution will probably not run fast enough. However, this number is small enough that a carefully coded solution can run quite quickly, and is the approach we will take in solving this problem.

**Logical programming**

It is possible to take the approach a person would use and program it into a computer. The alphametic is broken up into a set of logical rules which must all be satisfied by a valid solution. The number of solutions is small and the search space of this approach is usually related to it, so this would seem to be a way to produce a very fast program. Several 'Artificial Intelligence' languages such as Prolog exist and would be very appropriate for this kind of problem - but they are not commonly available. Writing a solution that draws entirely on logic would be very hard given the time constraints, but it is possible to use aspects of this approach to make brute force rather faster.

**An efficient brute force algorithm**

Assuming that the entire range of possible solutions can be generated quickly - and it can - brute force could be used if an algorithm can be found that allows each possible solution to be checked swiftly. To do this it is necessary to minimise the need to decode or look up values, and preferably keep to simple arithmetic that will run quickly. We can rewrite the alphametic - ignoring the leading zeros constraint - as an element by element sum of two short arrays. This can be evaluated very quickly. The reasoning goes as follows.

Let there be *N* lines and *M* characters. We
write the *n*th line as

W*n1* * X*1* + ... + W*nM* * X*M*

where Xm is the value assigned to character m. The sum can then
be written as

W*11* * X*1* + ... + W*1M* * X*M* +

W*21* * X*1* + ... + W*2M* * X*M* =

W*31* * X*1* + ... + W*3M* * X*M*

The solution must satisfy

W*1* * X*1* + ... + W*M* * X*M* = 0

where W*m* = W*1m* + ... + W*(N-1)m* - W*Nm*,
and X*1*..X*M* can only be distinct digits from 0
to 9. We can check for leading zeros later, as there will be few
and we want to keep this routine fast.

It is necessary to choose a data representation that will
allow us to manage the (potentially large) values that can be
generated - which may be of the order of 10 to the power 11. Long
(32-bit) integers will not do. However, many machines provide a
64-bit integer type (`comp`

in Turbo Pascal, `long`

in Java), a 8 or 6-byte floating point type (`double `

or
`real`

) which is also suitable. Even if only 32-bit
integers are used, the programs will only fail when the words of
the alphametic are 8 characters or more - in fact, only one of
the six test cases used in marking probes this.

The algorithm is therefore:

- identify the different letters in the sum
- compute W
*1*..W*M* - generate all possible combinations of X
*1*..X*M*that are distinct digits from 0 to 9 - for each, check that W
*1** X*1*+ ... + W*M** X*M*= 0 - for each of these, insert the letter values into the original alphametic; if there are no leading zeros, it is a solution.

It is also possible to maintain a 'sum so far' by permuting X*1*..X*M*
in turn and storing

W*1* * X*1* + ... + W*p* * X*p*

where *p* is the latest letter that is being generated.

An example solution that implements this method has been written as bio98q3.java. It can be viewed in a Java-enabled browser or run on a Java-capable computer from the example solution to Q3 page.

**Marking**

The program for part 3(a) is to be marked with six tests.

In tests 1 and 2 the alphametics have multiple solutions. All valid solutions are listed, sorted by total; a program need only give one solution. [4] marks are to be given for any correct solution, but [2] of those marks should be deducted if the program also prints 'Unique'.

Test 1: [4]3 ONE ONE TWO |
Test 2: [4]3 FATHER MOTHER PARENT |

Tests 3 and 4 have unique solutions. For each test [4] marks should be given for printing the correct solution and the word 'Unique'. If the word 'Unique' is absent, only [2] marks should be given for the correct solution.

Test 3: [4]4 SEVEN SEVEN SIX TWENTY |
Test 4: [4]6 THREE THREE TWO TWO ONE ELEVEN |

Tests 5 and 6 have no solutions. For each test [4] marks should be given for printing the word 'Impossible', and [0] marks are available for any other output.

Test 5: [4]3 BIO FIRST ROUND |
Test 6: [4]5 SEVENTEEN SEVENTEEN SEVENTEEN SEVENTEEN SIXTYEIGHT |

(N.B. Test 5 is **not** the same as the example
alphametic given in question 3(b).)

A total of 24 marks are available for a question that solves all of these test cases for 3 (a).

**3 (b) [4 marks].** *Find two solutions to
BIO + ROUND = FIRST.*

This alphametic was chosen to be one that could relatively easily be solved by hand, so that participants who had not solved 3 (a) could pick up marks here. From inspection, F must be R+1, O must be 9 and I must be 0 (zero).

There are 16 different solutions, listed below and sorted by total. Score [2] marks for a single correct solution, and [4] marks for two correct solutions. Additional correct solutions, and any incorrect solutions, should be ignored.

509 + 19638 = 20147 609 + 19538 = 20147 309 + 19847 = 20156 809 + 19347 = 20156 309 + 19865 = 20174 809 + 19365 = 20174 509 + 19674 = 20183 609 + 19574 = 20183 |
509 + 39817 = 40326 809 + 39517 = 40326 509 + 39862 = 40371 809 + 39562 = 40371 709 + 59814 = 60523 809 + 59714 = 60523 709 + 59832 = 60541 809 + 59732 = 60541 |

**3 (c) [3 marks]. ***If you are only allowed
to use a single letter, is it possible to construct an addition
alphametic with a solution? If you believe it is possible give an
example alphametic, and if you believe it is impossible give a
brief explanation why.*

[1] mark is available for making the assertion that yes, it is
possible. A further two marks are available by giving an example
alphametic [1] and a numeric solution to it [1]: for example

A+A+A+A+A+A+A+A+A+A+A = AA has a solution with A equal to
1,2,3,4,5,6,7,8 or 9.

**3 (d) [5 marks]. ***An alphametic is being
created, where ABC and DEA are to be summed, and the total is to
only use the letters A, B, C, D or E. How many possibilities
(i.e. valid letter combinations) are there for the total, so that
the resulting alphametic has a solution? How many different sums
can be represented by such an alphametic?*

This requires us to write a program to generate all possible totals (any combination of three or four of the letters A to E, allowing a letter to be repeated) and, for each, check if it has a valid solution.

Separate counts of the valid combinations and the different sums must be maintained - we can count the different sums if an algorithm goes through the letter/digit permutations in a non-repeating way, but several different sums may be represented by the same letter combinations, so they must be counted at the end.

To speed the search up, the numeric codes (W) corresponding to each solution can be generated in advance, and a search similar to that in 3 (a) is then possible.

This part is also solved as function `try3d()`

in bio98q3.java,
and is called by entering -1 for the number of lines. It can be
viewed in a Java-enabled browser or run on a Java-capable
computer from the example
solution to Q3 page. The code displays every combination and
so runs rather slowly in the browser or in a console. Running it
with a command-line Java interpreter and redirecting the output
to a file makes it much quicker.

**Marking**

[2] There are 163 valid alphametics/letter combinations

[3] 1136 different sums can be represented.

Maximum 5 marks for part 3 (d).

- Java example solution program for 3(a) and 3(d).
- Question statement
- Index of BIO'98 exam
- Index of BIO'99 sample paper

The British Informatics Olympiad