# Enigmatic Code

Programming Enigma Puzzles

## Enigma 353: Up the polls

From New Scientist #1502, 3rd April 1986 [link]

When electing a mayor, our town councillors each vote for one of the candidates, and if a candidate obtains over half the votes in this first count he is elected. If this fails to happen, then the candidate with the least votes “donates” his votes entirely to one of the remaining candidates and takes no further part of the procedure.

The new totals are then calculated and if one candidate has over half the votes, or if a candidate has been first in the two counts, then he is elected. If both those fail to happen, then again the candidate with fewest votes in the second count donates his votes to one of the remaining candidates and retires. This continues until someone has over half the votes or has been top in any two counts.

When the current mayor was elected the 31 counsellors each voted for their choice of one of the five candidates, and each candidate received a different number (but less than half) of the votes. So the candidate with fewest votes donated his and retired. The second count gave a new clear leader, but it was still indecisive. The third account gave a new clear leader, but it too was still indecisive. At last, on the fourth count, the mayor was elected, and in none of the counts had he been placed second.

How many votes did that mayor get in the very first vote?

[enigma353]

### 2 responses to “Enigma 353: Up the polls”

1. Jim Randell 15 July 2016 at 9:06 am

This Python 3 program runs in 180ms.

```from enigma import irange, printf

# let's suppose A wins
# B is eliminated in round 4
# C is eliminated in round 3
# D is eliminated in round 2
# E is eliminated in round 1

# indices for the candidates
(A, B, C, D, E) = (0, 1, 2, 3, 4)

# generate votes for each of the five candidates
# each vote is different and in the range 0 to 15
if len(vs) == 4:
# the remaining candidate gets the rest
v = 31 - t
if v < 16 and v not in vs:
yield vs + [v]
else:
# allocate votes to the next candidate
for v in irange(0, 15):
u = t + v
if u < 32 and v not in vs:
yield from votes(vs + [v], u)

# update list s, add value v to index i
def update(s, i, v):
s = list(s)
s[i] += v
return s

# votes for the 5 candidates in round 1
# E is eliminated in round 1
if not all(vs1[E] < vs1[x] for x in (A, B, C, D)): continue
# and the winner is...
w1 = vs1.index(max(vs1))
# A is not placed second
if all(x == w1 or vs1[A] > vs1[x] for x in (B, C, D)): continue

# donate E's votes to someone
for dE in (A, B, C, D):
vs2 = update(vs1[:4], dE, vs1[E])
# D is eliminated
if not all(vs2[D] < vs2[x] < 16 for x in (A, B, C)): continue
# there is a new clear leader, but the result is indecisive
v = max(vs2)
if not vs2.count(v) == 1: continue
w2 = vs2.index(v)
if w2 == w1: continue
# A is not placed second
if all(x == w2 or vs2[A] > vs2[x] for x in (B, C)): continue

# donate D's votes to someone
for dD in (A, B, C):
vs3 = update(vs2[:3], dD, vs2[D])
# C is eliminated
if not all(vs3[C] < vs3[x] < 16 for x in (A, B)): continue
# there is a new clear leader
v = max(vs3)
if not vs3.count(v) == 1: continue
w3 = vs3.index(v)
if w3 == w1 or w3 == w2: continue
# A is not placed second (so must have won)
if w3 != A: continue

# donate C's votes to someone
for dC in (A, B):
vs4 = update(vs3[:2], dC, vs3[C])
# B is eliminated
if not(vs4[B] < vs4[A]): continue

# output the solution
L = 'ABCDE'
printf("1: {vs1}, winner = {w1}, eliminated = E -> {dE}", w1=L[w1], dE=L[dE])
printf("2: {vs2}, winner = {w2}, eliminated = D -> {dD}", w2=L[w2], dD=L[dD])
printf("3: {vs3}, winner = {w3}, eliminated = C -> {dC}", w3=L[w3], dC=L[dC])
printf("4: {vs4}, winner = A, eliminated = B")
printf()
```

The result of the first round is: C=9, B=8, A=7, D=5, E=2. C wins, B is second, E is eliminated and donates his votes to B.

The result of the second round is: B=10, C=9, A=7, D=5. B wins, C is second, D is eliminated and donates his votes to A.

The result of the third round is: A=12, B=10, C=9. A wins, B is second, C is eliminated and donates his votes to A.

The result of the fourth round is: A=21, B=10. A wins with more than half the votes (and with wins in two rounds) and is elected.

2. Brian Gladman 15 July 2016 at 11:51 pm
```from itertools import permutations

# partition the integer <n> into <m> different, non-zero parts
# (in sort order) with each part not greater than <maxv>
def partition(n, m, maxv, seq=[]):
if not n:
if not m:
yield seq
else:
for i in range(1 if not seq else (seq[-1] + 1), min(maxv, n) + 1):
yield from partition(n - i, m - 1, maxv, seq + [i])

# generate the results for round two or round three
# <rnd> contains a list of (candidate, vote) pairs
# in increasing vote order for the previous round
def do_round(rnd):
# find the minimum and maximum votes in the previous round
# for each of the votes between the minimum and maximum
for cc, _ in rnd[1:-1]:
# form the new list of votes (in increasing vote order) for
# each candidate except the lowest when the latter's vote is
# added to the identified vote
r2 = sorted(((c, v) if c != cc else (c, v + min_votes)
for c, v in rnd[1:]), key=lambda x: x[1])
# find the new maximum vote and the new lead candidate
max_v, win_r2 = r2[-1][1], r2[-1][0]
# we must have a new lead candidate but not a winner
if r2[-2][1] == max_v or not (max_votes < max_v < 16):
continue
# return the winner and the list of (candidate, vote) pairs
yield win_r2, r2

# divide the 31 votes between the five candidates with each
# receiving a different non-zero vote of fiftenn or less
for votes in partition(31, 5, 15):

# when the minimum number of votes is added to one of the
# middle three votes a new winner must emerge
continue

# name the candidates A .. E in order of increasing votes
r1, winner_r1 = list(zip('EDCBA', votes)), 'A'

# consider all possible results for round two
for winner_r2, r2 in do_round(r1):
# the must be a new lead candidate
if winner_r2 != winner_r1:

# consider all possible results for round three
for winner_r3, r3 in do_round(r2):
# the must again be a new lead candidate
if winner_r3 not in (winner_r1, winner_r2):

# candidate to the votes of either of the top two
for c4, v4 in r3[1:]:
r4 = sorted(((c, v) if c != c4 else (c, v + r3[0][1])
for c, v in r3[1:]), key=lambda x: x[1])

# one candidate must now win with 16 or more votes - check that
# the winner has never been second in the previous rounds
winner_r4 = r4[-1][0]
if not any(r[-2][0] == winner_r4 for r in (r1, r2, r3)):

# output the results for the four rounds
for i, r in enumerate((r1, r2, r3, r4)):
t = ', '.join('{:}:{:02}'.format(c, v) for c, v in sorted(r))
print('Round {}: {}'.format( i + 1, t))

fs = 'The mayor got {} votes in round one.'
print(fs.format(dict(r1)[winner_r4]))
```