Enigmatic Code

Programming Enigma Puzzles

Enigma 201: Secret ballot

From New Scientist #1347, 3rd March 1983 [link]

The Progressive Party has just chosen its prospective parliamentary candidate for Mudbridge North. Six persons were short-listed, and, having duly confided their belief in peace, progress and plenty, were voted upon by the members present. The members have been tight-lipped about the voting figures but the candidates more (apparently) forthcoming. Tabulated below are the votes which the candidates (listed down the left) allege were got by various candidates (listed across the top). For instance D says that F scored 10. You will need to know, however, that there were three candidates of each sex, that each has overstated the votes for anyone of his or her own sex and understated those for anyone of the other sex, and that the same number of votes was cast in total for men as for women. Can you reveal the true voting figures?

Enigma 201

[enigma201]

Advertisements

One response to “Enigma 201: Secret ballot

  1. Jim Randell 23 June 2014 at 8:23 am

    This puzzle is somewhat similar to Enigma 70, so I re-used the Interval() class I wrote for that puzzle in this one.

    This Python code runs in 38ms.

    from itertools import combinations
    from enigma import irange, sprintf, Accumulator, 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))
    
    # the candidates
    candidates = (A, B, C, D, E, F) = tuple(irange(0, 5))
    names = 'ABCDEF'
    
    # the table
    table = {
      A: { B: 9, F: 14 },
      B: { A: 5, C: 9, E: 6 },
      C: { A: 6, B: 13 },
      D: { F: 10 },
      E: { C: 13, D: 8, F: 8 },
      F: { B: 11, C: 7 },
    }
    
    # determine votes given a gender map
    def votes(g):
    
      # make an interval for each candidate
      vs = list(Interval() for _ in candidates)
    
      # and update according to the table
      for (c1, ss) in table.items():
        g1 = g[c1]
        for (c2, v) in ss.items():
          if g[c2] == g1:
            # for the same gender the value is an overestimate
            vs[c2].update(mx=v - 1)
          else:
            # for different genders the value is an underestimate
            vs[c2].update(mn=v + 1)
    
      # return the possible intervals
      return vs
    
    # generate possible votes for a group of candidates given:
    # t - the total to achieve
    # g - the indices of the candidates
    # vs - array of votes (as intervals) for each candidate
    def generate(t, g, vs):
      if len(g) == 1:
        if t in vs[g[0]]:
          yield [(g[0], t)]
      else:
        for v in vs[g[0]]:
          if not(v < t): break
          for gs in generate(t - v, g[1:], vs):
            yield [(g[0], v)] + gs
    
    # choose three candidates to be a different gender from A
    for g1 in combinations(candidates[1:], 3):
      # map candidates to gender
      g = dict((x, int(x in g1)) for x in candidates)
    
      # determine possible votes
      try:
        vs = votes(g)
      except ValueError:
        # if a bad interval happens, skip to the next choice
        continue
    
      # determine total number of votes for each gender
      t = list(Accumulator(fn=lambda x, y: x.sum(y)) for _ in (0, 1))
      for (c, v) in enumerate(vs):
        t[g[c]].accumulate(v)
      total = list(x.value for x in t)
    
      # consider possible totals (for the genders)
      g0 = tuple(c for c in candidates if c not in g1)
      for t in total[0].intersect(total[1]):
        printf("total votes = {t} (for each gender)")
    
        # generate possible votes for each gender and display
        for (l, g) in (('gender=0', g0), ('gender=1', g1)):
          for x in generate(t, g, vs):
            printf("{l}: {x}", x=', '.join(names[i] + '=' + str(v) for (i, v) in x))
        printf()
    

    Solution: The actual voting figures are: A=7, B=12, C=8, D=9, E=5, F=9.

    A, D and F are the same gender, and have 25 votes between them. And B, C and E are the other gender, and also have 25 votes between them.

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: