Enigmatic Code

Programming Enigma Puzzles

Enigma 70: Find the catch

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

Enigma 70

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]

Advertisements

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:
            # statement about your brother = correct
            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 my 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)))
    

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: