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():
          d[v].add(k)
        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[0]]
        if not(len(donkey) > len(d[ks[1]])): 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][2])))
        (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[0]
        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():
        d[v].add(k)
      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[0]]
      if not(len(donkey) > len(d[ks[1]])): 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
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: