Enigmatic Code

Programming Enigma Puzzles

Enigma 70: Find the catch

From New Scientist #1213, 7th August 1980 [link]

Three pairs of brothers went off or a day’s fishing and each pair caught the same number of fish between the two of them. Anglers are not everyone’s first choice for guardians of truth, however, and the table above needs a pinch of salt. It records what each man (listed down the left) claimed that three men (listed across the top) had caught. (For instance, Charles claimed that Bert had caught 11). To sort it out, you need to know that each always states his brother’s catch correctly but overstates his own and understates anyone else’s.

Who really caught how many?

[enigma70]

3 responses to “Enigma 70: Find the catch”

1. Jim Randell 12 March 2013 at 8:51 am

This Python program examines all possible pairings of the brothers. It then uses a class representing intervals to track the minimum and maximum possible values for each fisherman. If the interval holds no values then an exception is raised (by using Python’s `assert` construct, in a “real” program I would define my own exception), and the code moves on to the next possibility.

Interval.__iter__() can be implemented using yield from ... in Python 3.3, but here I implemented it with a loop so the program will also run under Python 2.7.

The output code takes into account the fact that multiple values may arise from the intervals – although it turns out there is a single solution, so for solving this particular puzzle the code could be simplified.

This code runs in 38ms.

```from collections import defaultdict
from itertools import product
from enigma import irange, sprintf, printf

# represent an interval by its min and max values
class Interval(object):

def __init__(self, mn=None, mx=None):
self.mn = 0 # lower limit
self.mx = 999 # upper limit
self.update(mn, mx)

def __repr__(self):
return sprintf("<{self.mn},{self.mx}>")

# update the min/max values
def update(self, mn=None, mx=None):
if mn is not None and mn > self.mn: self.mn = mn
if mx is not None and mx < self.mx: self.mx = mx
if self.mn > self.mx: raise ValueError(sprintf("Bad Interval {self}"))

# iterate through the values in an interval
def __iter__(self):
for i in irange(self.mn, self.mx): yield i

# an interval that is the sum of this interval and another
def sum(self, other):
return Interval(mn=self.mn + other.mn, mx=self.mx + other.mx)

# an interval that is the intersection of this interval and another
def intersect(self, other):
return Interval(mn=max(self.mn, other.mn), mx=min(self.mx, other.mx))

# people
ps = set('ABCDEF')

# statements (from the table)
s = {
'A': { 'A': 10, 'E': 8, 'F':  3 },
'B': { 'C':  3, 'D': 4, 'E': 10 },
'C': { 'B': 11, 'C': 9, 'F':  2 },
'D': { 'A':  8, 'C': 6, 'E':  7 },
'E': { 'B':  6, 'D': 7, 'E': 15 },
'F': { 'B': 12, 'D': 6, 'F':  7 },
}

# generate pairs of brothers as a dict
def generate():
X = 'A'
for bX in ps.difference(X):
Y = min(ps.difference(X + bX))
for bY in ps.difference(X + bX + Y):
Z, bZ = tuple(ps.difference(X + bX + Y + bY))
yield { X: bX, bX: X, Y: bY, bY: Y, Z: bZ, bZ: Z }

# examine the statements given a pairing order
# b - dictionary mapping person to brother
def solve(b):
# make an interval for each brother
r = dict((x, Interval()) for x in s.keys())
# update the intervals according to each statement
for (x, v) in s.items():
for (y, n) in v.items():
# there are 3 cases for each statement
if x == y:
# statement about yourself = overestimate
r[y].update(mx=n-1)
elif b[x] == y:
r[y].update(mn=n, mx=n)
else:
# statement about other = underestimate
r[y].update(mn=n+1)

# determine intersection of the sums for each pair of brothers
i = Interval()
for (k, v) in r.items():
if not(k < b[k]): continue
i = i.intersect(v.sum(r[b[k]]))

# consider the possible values for the sum and generate solutions
for t in i:
check(t, b, r)

# check for possible solutions
# t - total sum for each pair
# b - dictionary mapping person to brother
# r - dictionary mapping person to interval
def check(t, b, r):
s = defaultdict(list)
# find possible values for each pair of brothers
for (k, v) in r.items():
# only consider each pair once
if not(k < b[k]): continue
# and consider the possible values
for v in r[k]:
bv = t - v
if bv in r[b[k]]:
s[(k, b[k])].append((v, bv))
# pairs of brothers
p = sorted(s.keys())
# output pairs of brothers and numbers of fish
for v in product(*(s[i] for i in p)):
print(' / '.join(sprintf("{b[0]}: {f[0]}, {b[1]}: {f[1]}") for (b, f) in zip(p, v)))

# consider each possible pairing
for b in generate():
try:
solve(b)
except ValueError:
# if there's a problem move onto the next pairing
continue
```

Solution: Each pair caught 18 fish. The pairs are: A caught 8, D caught 10; B caught 12, F caught 6; C caught 7, E caught 11.

• Jim Randell 19 March 2013 at 10:25 am

Using the partitions() routine recently added to the enigma.py library the generate() function could be written as:

```from enigma import partitions

# generate pairs of brothers as a dict
def generate():
for (X0, X1), (Y0, Y1), (Z0, Z1) in partitions('ABCDEF', 2):
yield { X0: X1, X1: X0, Y0: Y1, Y1: Y0, Z0: Z1, Z1: Z0 }
```
2. Brian Gladman 15 March 2013 at 5:28 pm

This one looked quite hard so I fancied having a go at it:

```from collections import defaultdict as dfd

people = ( 'A', 'B', 'C', 'D', 'E', 'F' )

claims = { 'A':(('A', 10), ('E', 8), ('F',  3)),
'B':(('C',  3), ('D', 4), ('E', 10)),
'C':(('B', 11), ('C', 9), ('F',  2)),
'D':(('A',  8), ('C', 6), ('E',  7)),
'E':(('B',  6), ('D', 7), ('E', 15)),
'F':(('B', 12), ('D', 6), ('F',  7)) }

def rep(x):
f, *r = x
return '{:s}'.format(x) if r else '{:d}'.format(f)

def gen_pair_lists(s, r = []):
if len(s) <= 2:
yield r + [(s[0], s[1])]
else:
for i in range(1, len(s)):
new_s = s[1:i] + s[i+1:]
yield from gen_pair_lists(new_s, r + [(s[0], s[i])])

for brother_list in gen_pair_lists(people):
f_min, f_max = dfd(lambda:0), dfd(lambda:100)
for claimant in people:
for who, fish in claims[claimant]:
# if the claims is about his own catch, it is an
# overestimate - we need the minimum of such claims
if who == claimant:
f_max[who] = min(f_max[who], fish - 1)
# if the claims is about his brother it is correct
elif tuple(sorted((claimant, who))) in brother_list:
f_min[who] = f_max[who] = fish
# if the claims is not about him or his brother, it is an
# underestimate - we need the maximum of such claims
else:
f_min[who] = max(f_min[who], fish + 1)

# now for the three pairs find a common range for
# the total number of fish caught by each pair
common = set(range(100))
for x, y in brother_list:
common &= set(range(f_min[x] + f_min[y], f_max[x] + f_max[y] + 1))
if common:
# for each number in the common range
for fish in common:
# for each pair of brothers
for x, y in brother_list:
# find the range for the number of fish caught by brother x
# and this range again but based on the combined total and
# the range for brother y --- the actual range must then lie
# in the intersection of these two ranges
range_x = set(range(f_min[x], f_max[x] + 1))
range_x &= set(range(fish - f_max[y], fish - f_min[y] + 1))
# now calculate the range for brother y from that for brother x
range_y = set(range(fish - max(range_x), fish - min(range_x) + 1))
print('Brothers {:s} and {:s} catch {:s} and {:s} respectively.'
.format(x, y, rep(range_x), rep(range_y)))
```

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