# Enigmatic Code

Programming Enigma Puzzles

## Enigma 493a: Little donkey

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 animals

and 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; 5

Eventually 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 not want a donkey in the Nativity play?

[enigma493a] [enigma493]

### One response to “Enigma 493a: Little donkey”

1. Jim Randell 25 March 2019 at 8:11 am

My first thought was to let the [[ `SubstitutedExpression()` ]] solver (from the enigma.py library) 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:

```len(set((A, B, C, D, E))) = 4
```

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 ]

```from collections import defaultdict
from enigma import irange, SubstitutedExpression, join, sprintf, printf

# we can identify the children by the letters they wrote down
kids = dict(
ABCDE=4, AGES=3, BEAR=4, BIG=2, BIN=2, CATS=2, DOG=2, DRAG=2,
FIB=2, FIT=2, GOAT=2, HAT=2, MICE=4, NIL=2, NOPQ=2, QRST=4,
RACE=3, RATS=3, RIPE=4, ROBE=4, SHACK=2, SPARE=3, TACK=2, TRAILS=5
)

# make the expressions for the alphametic puzzle
fn = lambda k: sprintf("len(set(({k})))", k=join(k, sep=", "))
exprs = list((fn(k), v) for (k, v) in kids.items())

# add in the extra expression
exprs.append((fn("ABCDEFGHIJKLM"), 7))

# attempt a solution with n different animals
def solve(n):

# create an alphametic puzzle in the appropriate base
p = SubstitutedExpression(exprs, distinct="", base=n, template="", verbose=0)

# solve the puzzle
for s in p.solve():

# group the solution symbols together
d = defaultdict(set)
for (k, v) in s.items():
printf("[{n} different animals]", n=len(d.keys()))

# order the keys by the most symbols
ks = sorted(d.keys(), key=lambda k: len(d[k]), reverse=1)

# the donkey has the most names
donkey = d[ks]
if not(len(donkey) > len(d[ks])): continue
printf("[donkey = {donkey}]", donkey=join(sorted(donkey)))

# find the children who didn't ask for a donkey
ks = list(k for (k, v) in kids.items() if not donkey.intersection(k))
printf("{n} did not ask for donkey: {ks}", n=len(ks), ks=join(sorted(ks), sep=", "))
return 1

# consider the number of different animals
for n in irange(7, 14):
if solve(n): break
```

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 PyPy does not have such a limitation, and the program runs fine using PyPy in 347ms.

Here are the groups it finds:

0: B I
1: D G R
2: L N Q
3: A C F O P T
4: E H K S
5: M
6: J

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:

B I G
B I N
N I L

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 ]

```from collections import defaultdict
from enigma import filter2, update, irange, join, printf

# we can identify the children by the letters they wrote down
kids = dict(
ABCDE=4, AGES=3, BEAR=4, BIG=2, BIN=2, CATS=2, DOG=2, DRAG=2,
FIB=2, FIT=2, GOAT=2, HAT=2, MICE=4, NIL=2, NOPQ=2, QRST=4,
RACE=3, RATS=3, RIPE=4, ROBE=4, SHACK=2, SPARE=3, TACK=2, TRAILS=5
)

# solve for a given map
# d = map of symbols -> count of different values
# m = map of symbol -> value
# j = next value to use
def solve(d, m, j):
# examine each element
d1 = dict()
for (k, v) in d.items():
# split symbols into assigned and unassigned
(a, u) = filter2((lambda x: x in m), k)
if not u:
# all values are assigned
vs = set(m[x] for x in a)
if len(vs) != v: return
else:
d1[k] = (v, a, u)
# are we done?
if not d1:
yield m
else:
# choose the item with the fewest unassigned symbols
k = min(d1, key=(lambda x: len(d1[x])))
(v, a, u) = d1[k]
# assigned values
vs = set(m[x] for x in a)
# number of values left to assign
n = v - len(vs)
if n < 0 or n > len(u): return
# choose the symbol to assign
s = u
d2 = dict((k, d[k]) for k in d1)
# consider possible values
for x in irange(1, j):
if x in vs:
if n != len(u):
# try using a value already in the collection
yield from solve(d2, update(m, [(s, x)]), j)
else:
if n != 0:
# try using a new value
yield from solve(d2, update(m, [(s, x)]), max(x + 1, j))

# additional requirement that A-M identifies 7 different animals
d = update(kids, [('ABCDEFGHIJKLM', 7)])

# start with one of the completely distinct sets (MICE, QRST, RIPE, ROBE)
m = dict((k, v) for (v, k) in enumerate('RIPE', start=1))

# find solutions for the remaining sets
for s in solve(d, m, 5):

# group the solution symbols together
d = defaultdict(set)
for (k, v) in s.items():
printf("[{n} different animals]", n=len(d.keys()))

# order the keys by the most symbols
ks = sorted(d.keys(), key=lambda k: len(d[k]), reverse=1)

# the donkey has the most names
donkey = d[ks]
if not(len(donkey) > len(d[ks])): continue
printf("[donkey = {donkey}]", donkey=join(sorted(donkey)))

# find the children who didn't ask for a donkey
ks = list(k for (k, v) in kids.items() if not donkey.intersection(k))
printf("{n} did not ask for donkey: {ks}", n=len(ks), ks=join(sorted(ks), sep=", "))

# we only need one solution
break
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.