# 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]

### 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': (6, 13, 10, 7),
'q2': (10, 6, 14, 6),
'q2': (14, 10, 5, 7),
'q2': (9, 5, 12, 10),
'q2': (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.split())) }
if len(argv) > 1: vs = tuple(map(int, argv.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([],  * 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])
```

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