Enigmatic Code

Programming Enigma Puzzles

Enigma 1166: Order the presents

From New Scientist #2322, 22nd December 2001

Each year there are eight presents in the sack, their values whole numbers of pounds from 1 to 8, to be distributed to the children Amber, Ben, Christine, and Dick. The presents are drawn from the sack at random, one at a time. Each is given to the child who has already received the lowest total value; if more than one qualify, then to whichever of them whose name comes first in alphabetic order.

Last year, Amber received a final total value of £8, Ben £5, Christine £11, Dick £12.

Q1: What were the values of the first and the seventh presents drawn?

I recorded the values in pounds for the previous five years:

1995: A 6, B 13, C 10, D 7
1996: A 10, B 6, C 14, D 6
1997: A 14, B 10, C 5, D 7
1998: A 9, B 5, C 12, D 10
1999: A 13, B 6, C 5, D 12

Unfortunately I must have made some mistakes because for some of those years the values could not have been achieved.

Q2: Which years were correctly written down?

Thanks to Hugh Casement for providing a transcript for this puzzle.

[enigma1166]

Advertisements

2 responses to “Enigma 1166: Order the presents

  1. Jim Randell 23 May 2016 at 9:16 am

    This Python 3 program takes 449ms to check all six outcomes given in the puzzle and find all possible sequences that could lead to those outcomes. You can also use it to solve other problems by specifying the required outcomes and values on the command line.

    from enigma import irange, diff, printf
    
    # return a list the same as s, except with value v at index i
    def update(s, i, v):
      s = list(s)
      s[i] = v
      return s
    
    # generate permutations that lead to this outcome
    # cs - required outcome
    # vs - values remaining to distribute
    # s - sequence of values used
    def solve(cs, vs, s):
      # are we done?
      if not vs:
        yield s
        return
      # choose an slot to distribute the next value to
      for (i, v1) in enumerate(cs):
        # choose a value
        for v in vs:
          # it can't be more than is in the slot
          if v1 < v: continue
          # the previous value would be
          v0 = v1 - v
          # and it must be the first lowest value
          if all(v0 < x for x in cs[:i]) and all(v0 <= x for x in cs[i + 1:]):
            # solve for the remaining values
            yield from solve(update(cs, i, v0), diff(vs, [v]), [v] + s)
    
    # the values to distribute
    vs = list(irange(1, 8))
    
    # results that the puzzle is interested in
    qs = {
      'q1': (8, 5, 11, 12),
      'q2[1995]': (6, 13, 10, 7),
      'q2[1996]': (10, 6, 14, 6),
      'q2[1997]': (14, 10, 5, 7),
      'q2[1998]': (9, 5, 12, 10),
      'q2[1999]': (13, 6, 5, 12),
    }
    
    # command line:
    # '<r> <r> ... <r>' - required outcomes, space separated list of ints
    # '<v> <v> ... <v>' - values to distribute, space separate list of ints
    import sys
    argv = sys.argv[1:]
    if len(argv) > 0: qs = { 'cmd-line': tuple(map(int, argv[0].split())) }
    if len(argv) > 1: vs = tuple(map(int, argv[1].split()))
    
    t = sum(vs)
    printf("[values = {vs}, sum = {t}]")
    
    r = dict()
    for k in sorted(qs.keys()):
      cs = qs[k]
      if sum(cs) != t: continue
      r[k] = 0
      for s in solve(cs, vs, []):
        printf("{k}: {s} -> {cs}")
        r[k] += 1
    
    for k in sorted(r.keys()):
      printf("{k}: {cs} {n} solutions", cs=qs[k], n=r[k])
    

    Solution: Q1: The first present drawn was £2. The seventh present drawn was £7. Q2: The values given for 1995 and 1998 are correct.

    For Q1 there are four sequences that end with A=£8, B=£5, C=£11, D=£12:

    (£2, £5, £1, £4, £3, £6, £7, £8)
    (£2, £5, £4, £1, £3, £6, £7, £8)
    (£2, £5, £3, £4, £6, £1, £7, £8)
    (£2, £5, £4, £3, £6, £1, £7, £8)

    For Q2 there are no possible solutions for the values given for 1996, 1997, and 1999.

    For the values given for 1995 – (£6, £13, £10, £7) – there are 36 possible sequences that end with those values.

    For the values given for 1998 – (£9, £5, £12, £10) – there are 8 possible sequences that end with those values.

    So we assume that the values for these two years have been correctly recorded.

  2. Brian Gladman 27 May 2016 at 12:34 pm
    from collections import defaultdict
    
    # given:    the list of presents given out so far
    # values:   the total values so far for A, B, C and D
    # presents: the set of presents still to be distributed
    def distribute(given, values, presents):
      # if we have finsihed return the values for the four
      # children and the list of presents given
      if not presents:
        yield tuple(values), tuple(given)
      else:
        # identify who gets the next present
        pos = values.index(min(values))
        # try each present that remains
        for p in presents:
          # add it to the value for the child identified 
          v2 = values[:]
          v2[pos] += p
          # and continue to distribute the presents that remain
          yield from distribute(given + [p], v2, presents.difference([p]))
    
    # the target values for last year
    vals = (8, 5, 11, 12)
    
    # the map from previous years to their lists of values
    prev = { 1995: (6, 13, 10, 7), 1996: (10, 6, 14, 6), 1997: (14, 10, 5, 7),
             1998: (9, 5, 12, 10), 1999: (13, 6, 5, 12) }
    set_prev = set(prev.values())
    
    # for the years that have correct value lists
    pres = defaultdict(int)
    
    # check possible present distributions for those specified 
    for v, p in distribute([], [0] * 4, set(range(1, 9))):
    
      # check for the last year
      if v == vals:
        print(p)
    
      # count how many sets of possible values match those
      # specified in previous years
      if v in set_prev:
        pres[v] += 1
    
    print()
    for y, v in sorted(prev.items()):
      print(y, v, pres[v])
    

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: