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]

Advertisements

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
    def votes(vs=[], t=0):
      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
    for vs1 in votes():
      # 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):
        # second round votes
        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):
          # third round votes
          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):
            # fourth round votes
            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()
    

    Solution: The winner received 7 votes in the first round.

    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
      min_votes, max_votes = rnd[0][1], rnd[-1][1]
      # 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
      if not any(votes[0] + v > votes[-1] for v in votes[1:-1]):
        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):
              
              # now consider adding the votes for the third
              # 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]))
    

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: