Programming Enigma Puzzles
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?
[enigma201]
 | Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
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.