Enigmatic Code

Programming Enigma Puzzles

Enigma 192: Merry Christmas

From New Scientist #1337, 23rd December 1982 [link]

Mr Pickwick and his friends, Mr Snodgrass, Mr Tupman and Mr Winkle spent last Christmas together. “No children this year, alas,” observed Mr Pickwick on Christmas morning, “I am very fond of children.” But just then there was a knock on the front door. Opening it, Mr Pickwick beheld more than half a dozen children, who thereupon sang God Rest Ye Merry Gentlemen. “Bless my soul!” he beamed and, fetching a tin of striped humbugs from the mantelpiece, shared them out equally and exactly among the children. The tin had once held a gross of humbugs but Mr Pickwick had already eaten some. Yet there were still enough (more than a hundred) to ensure that each child would receive more than half a dozen. In fact, if you knew how many Mr Pickwick had eaten himself, you could work out exactly how many each child got.

With the carollers gone, it was time for presents. As usual each person gave, and each received, one scarf, one pair of gloves and one bottle of port. Each gave a present to each. Mr Pickwick gave gloves to the person who gave Mr Snodgrass a scarf; and Mr Winkle gave port to the person who gave Mr Tupman gloves.

The dinner was a true feast — a sizzling goose, which weighed 8lb plus half its own weight, pursued by a pudding decked with holly and enriched with as many silver coins as you could place bishops on a chess board without any attacking any square occupied by another. Afterwards came cigars. “I would have you know”, remarked Mr Pickwick, puffing contentedly, “that if cigar-smokers always told the truth and others never did, then Mr Snodgrass would say that Mr Winkle would deny being a cigar smoker. Furthermore Mr Tupman would say that Mr Winkle would deny that Mr Snodgrass smokes cigars”. After these and other pleasant exchanges the quartet retired a trifle unsteadily to bed.

Thus were Mr Pickwick’s Yuletide jollifications exceedingly merry. He wishes similar Christmastide celebrations for revellers everywhere.

A few questions remain.

(1) How many humbugs had Mr Pickwick eaten himself?
(2) Who gave a bottle of port to whom? (four answers)
(3) What did the goose weigh?
(4) How many coins were hidden in the pudding?
(5) Was Mr Winkle a cigar-smoker?
(6) What are the four words of a, b, c, d letters in the sentences in italics [or bold] such that:
a³ – a = 20b and b² = 2bc and 2b² = c²d.

This puzzle completes the archive of Enigmas from 1982.

There are now 650 puzzles on the site, with a full archive from the start of Enigma in 1979 to the end of 1982 (192 puzzles) and also puzzles from January 2005 up to the end of Enigma in December 2013 (457 puzzles) — which is just over 36.5% of all Enigma puzzles.

[enigma192]

Advertisements

One response to “Enigma 192: Merry Christmas

  1. Jim Randell 18 May 2014 at 7:49 am

    I have written a separate Python program for each part of the problem.

    (1) This code examines the possible number humbugs in the tin and eliminates those where there are multiple possibilities for the number of children and number of humbugs each receives. It runs in 32ms.

    from collections import defaultdict
    from enigma import irange, divisors, printf
    
    # there are more than 6 children, and more than 100 but less than 144
    # humbugs, each child receives more than 6.
    
    r = defaultdict(list)
    
    # h = number of humbugs
    for h in irange(101, 143):
      # consider divisors of h, for the number of children
      for n in divisors(h):
        if n < 7: continue
        # each child gets more than 6 humbugs
        g = h // n
        if g < 7: break
        # record number of children and allocation of humbugs
        r[144 - h].append((n, g))
    
    for (k, vs) in r.items():
      if len(vs) == 1:
        printf("{k} humbugs eaten, {vs[0][0]} children, {vs[0][1]} humbugs each")
    

    (2) This code examines all possible permutations of gift giving. It runs in 63ms.

    from collections import defaultdict
    from itertools import product, permutations
    from enigma import diff, flatten
    
    people = 'PSTW'
    gifts = 'gps'
    
    # give[<person>]: maps <gift> -> <person>
    for ps in product(*(permutations(diff(people, p)) for p in people)):
      give = dict(zip(people, (dict(zip(gifts, p)) for p in ps)))
    
      # determine what gifts each recieves
      r = defaultdict(set)
      for d in give.values():
        for (k, v) in d.items():
          r[v].add(k)
      # each should get all three gifts
      if not all(len(x) == 3 for x in r.values()): continue
    
      # "Pickwick gave gloves to the person who gave Snodgrass a scarf"
      if not(give[give['P']['g']]['s'] == 'S'): continue
    
      # "Winkle gave port to the person who gave Tupman gloves"
      if not(give[give['W']['p']]['g'] == 'T'): continue
    
      print(', '.join(k + ' -> ' + v['p'] for (k, v) in give.items()))
    

    (3) I’ve used SymPy to solve the equation (although it is easy to solve by hand). This program runs in 371ms.

    from sympy import symbols, Eq, solve
    from enigma import printf
    
    # the goose weighs w: w = 8 + w/2
    w = symbols('w')
    for r in solve(Eq(w, 8 + w / 2)):
      if r.is_real and r > 0:
        printf("goose weighs {r} lbs")
    

    (4) This is the hardest part of the problem. The following Python program examines all possible placements of bishops on an N×N grid. I’ve assumed that the chessboard we’re interested in is an 8×8 grid, and the program runs in 1m46s in this case.

    from enigma import irange, chunk, Accumulator, printf
    
    import sys
    N = (8 if len(sys.argv) < 2 else int(sys.argv[1]))
    N1 = N - 1
    
    # we use a grid to keep track of bishops
    # None = unallocated, 1 = bishop, 0 = attacked by bishop
    
    # update a grid with a bishop at position i
    def update(g, i):
      g = list(g)
      g[i] = 1
      (y, x) = divmod(i, N)
      # NW
      for j in irange(1, min(x, y)):
        g[(y - j) * N + (x - j)] = 0
      # NE
      for j in irange(1, min(N1 - x, y)):
        g[(y - j) * N + (x + j)] = 0
      # SW
      for j in irange(1, min(x, N1 - y)):
        g[(y + j) * N + (x - j)] = 0
      # SE
      for j in irange(1, min(N1 - x, N1 - y)):
        g[(y + j) * N + (x + j)] = 0
      return g
    
    # g = current grid
    # i = start position
    # n = number of positions
    # m = accumulator
    def solve(g, i, n, m):
      if i == n:
        b = g.count(1)
        m.accumulate_data(b, g)
      else:
        for j in irange(i, n - 1):
          if g[j] is None:
            solve(update(g, j), j + 1, n, m)
    
    m = Accumulator(fn=max)
    n = N * N
    g = [None] * n
    solve(g, 0, n, m)
    
    printf("[N={N}] max value = {m.value} {grid}", grid=list(chunk(m.data, N)))
    

    (5) This program examines the possibilities for the preferences of the four friends. It runs in 30ms, but finds several solutions.

    from itertools import product
    from enigma import printf
    
    # True => always tells the truth (cigar smoker)
    # False => never tells the truth (i.e. always tells lies) (non-smoker)
    #
    # so "X says Y" can only be true if X == True and Y == True, or
    # X == False and Y == False, i.e. it corresponds to X == Y.
    #
    # and "X denies Y" can only be true if X == True and Y == False, or
    # X == False and Y == True, i.e. it corresponds to X != Y
    
    for (S, T, W) in product((True, False), repeat=3):
    
      # Snodgrass would say Winkle would deny being a cigar smoker
      # Tupman would say that Winkle would deny that Snodgrass smokes cigars
      if S == (W != (W == True)) and T == (W != (S == True)):
        printf("[1] S={S} T={T} W={W}")
    
      # but maybe Pickwick (a confirmed cigar smoker) is lying, and smokers
      # always lie and non-smokers always tell the truth
      if not(S == (W != (W == False))) and not(T == (W != (S == False))):
        printf("[2] S={S} T={T} W={W}")
    

    (6) This program extracts the words from the sentences, arranges them by number of letters and then looks for a collection of word lengths that satisfy the constraints. It runs in 44ms.

    from collections import defaultdict
    from itertools import product
    from enigma import flatten, printf
    
    words = flatten(x.split() for x in (
      'God Rest Ye Merry Gentlemen',
      'Thus were Mr Pickwick\'s Yuletide jollifications exceedingly merry',
      'He wishes similar Christmastide celebrations for revellers everywhere'
    ))
    
    # accumulate the words by word length (normalised to upper case)
    l2w = defaultdict(set)
    for w in words:
      n = sum(1 for x in w if x.isalpha())
      l2w[n].add(w.upper())
    
    # choose four word lengths
    for (a, b, c, d) in product(l2w.keys(), repeat=4):
      # check the equations
      if a ** 3 - a == 20 * b and b ** 2 == 2 * b * c and 2 * b ** 2 == c ** 2 * d:
        # output matching sentences
        for ws in product(*(l2w[x] for x in (a, b, c, d))):
          printf("words = {ws}", ws=' '.join(ws))
    

    These programs can all be tied together with the following Python program:

    import subprocess
    import sys
    
    parts = (
      ('enigma192a.py', '(1) How many humbugs had Mr Pickwick eaten himself?'),
      ('enigma192b.py', '(2) Who gave a bottle of port to whom?'),
      ('enigma192c.py', '(3) What did the goose weigh?'),
      ('enigma192d.py', '(4) How many coins were hidden in the pudding?'),
      ('enigma192e.py', '(5) Was Mr Winkle a cigar smoker?'),
      ('enigma192f.py', '(6) What are the four words...?'),
    )
    
    for (p, q) in parts:
      print(q)
      subprocess.call([sys.executable, p])
      print()
    

    Solution: (1) Mr Pickwick had eaten 23 humbugs from the tin. (2) The bottles of port were distributed as follows: from Mr Pickwick to Mr Snodgrass, from Mr Snodgrass to Mr Tupman, from Mr Tupman to Mr Winkle, and from Mr Winkle to Mr Pickwick. (3) The goose weighs 16 lb. (4) There were 14 coins hidden in the pudding. (5) It’s not possible to determine if Mr Winkle is a cigar smoker [*]. (6) The four words are: MERRY WISHES FOR YULETIDE [**].

    Some notes on the answers:

    (1) The number of children (n) and the number of humbugs each gets (g) must be the same, as we can’t distinguish between n children receiving g humbugs (h = n×g) and g children receiving n humbugs (h = g×n), so we need to find a square number between 10² and 12², so h=11², and hence there are 11 children and each gets 11 humbugs, meaning that Pickwick had already eaten 23 humbugs.

    (3) A straightforward solution to the equation w = 8 + w/2.

    (4) See [ http://mathworld.wolfram.com/BishopsProblem.html ] for more information on the Bishop Problem.

    (5) I’ve not been able to come up with a unique solution for W.

    If we assign a truth value (t, f) to (S, T, W), such that X = t means X tells the truth (and so is a smoker), and X = f means X always lies (and is a non-smoker).

    Then for a statement Y (that is true or false), “X states Y” is equivalent to X = Y.

    We get the following statements:

    (A) S states (W states (W is a non-smoker))
    → S = (W = (W = false))
    → S = (W = not(W))
    → S = false

    So S is a liar (and a non-smoker).

    And this fits with our intuition, as W cannot deny being a smoker. If W tells the truth (and so is a smoker) he would say “I am a smoker”, and if he lies (and so is a non-smoker) he would also say “I am a smoker”. So in order for S to report that W denies being a smoker, S has to be lying.

    (B) T states (W states not(S is a smoker))
    → T = (W = not(S = true))
    → T = (W = not(false))
    → T = (W = true)
    → T = W

    So we can’t determine the preferences of T and W, only that they are identical.

    And again this fits with out intuition. S is not a smoker, so if W denies S is a smoker he is telling the truth, and if T tells us that W would deny S is a smoker then he is also telling the truth. However, if W does not deny that S is a smoker then he is lying, but T tells us that he does deny S is a smoker, so he is also lying.

    Another alternative I considered was that smokers always lied and non-smokers always told the truth, that way everything P says is a lie, so we are looking for the negation of (A) and (B) (and of course X = t now corresponds to “X is a non-smoker”).

    But that gets us the same results:

    (A) not(S states (W states (W is a non-smoker)))
    → not(S = (W = (W = true)))
    → not(S = (W = W))
    → not(S = true)
    → S = false

    So S is a liar (and a smoker).

    (B) not(T states (W states not(S is a smoker)))
    → not(T = (W = not(S = false)))
    → not(T = (W = not(true)))
    → not(T = (W = false))
    → not(T = not(W))
    → T = W

    T and W have identical preferences.

    I like to think the “best” solution is that P, S, T, W are all smoking and lying.

    [*] The published solution is that Mr Winkle is a cigar smoker.

    (6) There are also multiple solutions to this part of the problem. Although the lengths of the words are unique: (a, b, c, d) = (5, 6, 3, 8), there are two possible words with 3 letters giving the two solutions: MERRY WISHES GOD YULETIDE, and MERRY WISHES FOR YULETIDE. Although only one of these collections of words makes sense as a sentence.

    [**] The published solution is “Merry wishes for Yuletide!”.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: