### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,124 hits

Programming Enigma Puzzles

25 March 2019

Posted by on **From New Scientist #1644, 24th December 1988** [link]

On the faraway Pacific island of Boxingday (not far from Christmas Island), the one letter words A, B, C, …, R, S, T are names of animals. However, an animal can have more than one name, for example, the letters A, B, C, D, E, F, G, H, I, J, K, L, M actually name only 7 different animals. The animal with the most different names is the donkey.

Just before Christmas, Miss Swayingpalms asked each child in her class to write down which animals they wanted to be in their nativity play. In their excitement the children sometimes wrote down the same animal more than once, but using different names. Thus:

Joseph write down A, B, C, D, E which name only 4 animals

Mary wrote down A, G, E, S which name 3 animals

Elizabeth B, E, A, R; 4 animals

John B, I, G; 2 animals

Anna B, I, N; 2 animals

David C, A, T, S; 2 animalsand so on:

D, O, G; 2

D, R, A, G; 2

F, I, B; 2

F, I, T; 2

G, O, A, T; 2

H, A, T; 2

M, I, C, E; 4

N, I, L; 2

N, O, P, Q; 2

Q, R, S, T; 4

R, A, C, E; 3

R, A, T, S; 3

R, I, P, E; 4

R, O, B, E; 4

S, H, A, C, K; 2

S, P, A, R, E; 3

T, A, C, K; 2

T, R, A, I, L, S; 5Eventually the nativity play was ready. As Miss Swayingpalms brought in the baby Jesus in his manger, she explained to the children that it did not matter about the repeated names, “It’s not what you are called that matters, but what you are!”

How many children did

notwant a donkey in the Nativity play?

[enigma493a] [enigma493]

%d bloggers like this:

My first thought was to let the [[

`SubstitutedExpression()`

]] solver (from theenigma.pylibrary) assign values to the symbols, such that all the numbers of different symbols are satisfied.Each expression can be expressed using a condition like this:

We are told that there are 7 different animals, and there are another 7 symbols, so there must be between 7 and 14 animals.

The program constructs alphametic expressions, which it considers in bases from 7 to 14 until it finds an answer.

Run:[ @repl.it ]Solution:3 children did not ask for a donkey in the Nativity play.However, there is an issue in approaching the problem this way. The alphametic solver writes a program to solve the expressions it is given, and in this case it falls foul of a limitation on the standard Python interpreter, that you aren’t allowed more than 20 nested blocks in a program. However

PyPydoes not have such a limitation, and the program runs fine usingPyPyin 347ms.Here are the groups it finds:

From which we see group 3 represents the donkey, so we need to find the children who didn’t write down any of the letters involved in this group.

They are:

Fortunately there is a solution when considering 7 different animals, so we only need to consider the alphametic as a base 7 problem.

If we stop the program exiting after it finds the first solution, we find that there are 5040 =

factorial(7)solutions corresponding to the number of ways of permuting the digits among the groups. So all the solutions are essentially the same as that given above.To come up with a program that will run under the standard Python interpreter I wrote a recursive solver for the puzzle. It’s a bit more work, but it does run a bit faster than the version above.

We can start with one of the collections that doesn’t includes duplicates (MICE, QRST, RIPE, ROBE) and assign each symbol to a different value. Then we can go through the remainder of the list, looking for collections with the fewest unassigned symbols, assign one of them and see if we can assign values to all of the symbols.

Once we have an assignment of symbols to values, we can proceed as above to check the solution.

This Python 3 program runs in 133ms.

Run:[ @repl.it ]