Enigmatic Code

Programming Enigma Puzzles

Enigma 286: Final analysis

From New Scientist #1433, 6th December 1984 [link]

Enigma 286

The diagram shows all the draws in the recent Golden Rook all-against-all chess tournament. In all other games, the winner scored 1 and the loser 0. Play was in five rounds with three games each.

“How did you do?”, I asked Alexander Alapin.

“Not well”, he replied. “Freddie French and I were so worn out by our first round draw (with each other) that we came equal bottom behind all the rest”.

“A lot of draws!”, I remarked.

“Yes. At least one in each round, with each player drawing in at least two consecutive rounds”.

There were two equal winners. Given that they did not meet in the second round, can you work out who they were and whom they played in the final round?

[enigma286]

Advertisements

One response to “Enigma 286: Final analysis

  1. Jim Randell 6 June 2015 at 7:13 am

    This Python3 program runs in 83ms.

    from collections import defaultdict
    from itertools import product
    from enigma import diff, flatten, printf
    
    # players
    players = list('ABCDEF')
    
    # all matches ('x' = unknown outcome)
    matches = {
      'AB': 'd', 'AC': 'x', 'AD': 'x', 'AE': 'x', 'AF': 'd',
      'BC': 'd', 'BD': 'x', 'BE': 'd', 'BF': 'x',
      'CD': 'x', 'CE': 'x', 'CF': 'd',
      'DE': 'd', 'DF': 'd',
      'EF': 'd',
    }
    
    # compute scores (in half points)
    def score(p, matches):
      t = 0
      for (k, v) in matches.items():
        i = k.find(p)
        if i == -1:
          pass
        elif v == 'd':
          t += 1
        elif (v == 'w' and i == 0) or (v == 'l' and i == 1):
          t += 2
      return t
    
    # generate possible rounds
    # n - number of rounds to generate
    # rs - the matches in each round
    # r - current round we're working on
    # matches - available matches
    def generate(n, rs, r, matches):
      # are all rounds complete?
      if len(rs) == n:
        yield rs
      # is the current round complete?
      elif len(r) == 2:
        # the final match is determined
        m = ''.join(diff(players, flatten(r)))
        if m in matches:
          yield from generate(n, rs + [r + [m]], [], diff(matches, [m]))
      else:
        # add a match to the current round
        # find the first unused player
        for p in players:
          if not any(p in x for x in r): break
        # choose a match for this player
        for m in matches:
          if p not in m: continue
          if any(len(set(m + x)) != 4 for x in r): continue
          yield from generate(n, rs, r + [m], diff(matches, [m]))
    
    # record possible rounds
    rounds = list()
    # generate possible rounds (starting with AF in the first round)
    for rs in generate(5, [], ['AF'], diff(matches.keys(), ['AF'])):
      # check there is (at least) one draw in each round
      if not all(list(matches[x] for x in r).count('d') > 0 for r in rs): continue
      # record rounds with draws for each player
      ps = defaultdict(list)
      for (i, r) in enumerate(rs, start=1):
        for x in r:
          if matches[x] == 'd':
            ps[x[0]].append(i)
            ps[x[1]].append(i)
      # each player must have draws in consecutive rounds
      if not all(any(i + 1 in ps[p] for i in ps[p]) for p in players): continue
      rounds.append(rs)
    
    # find matches with unknown outcomes 'x'
    ks = list(k for (k, v) in matches.items() if v == 'x')
    # choose outcomes for those matches
    for vs in product('wl', repeat=len(ks)):
      # record the outcomes
      matches.update(zip(ks, vs))
    
      # determine the scores for each player
      ss = dict((p, score(p, matches)) for p in players)
      # lowest score must belong only to A and F
      b = min(ss.values())
      if list(p for p in players if ss[p] == b) != ['A', 'F']: continue
      # determine the winners
      w = max(ss.values())
      ws = list(p for p in players if ss[p] == w)
      # there should be exactly two
      if len(ws) != 2: continue
      mw = ''.join(ws)
    
      # now find possible rounds where the winners didn't play in the second round
      for rs in rounds:
        if mw in rs[1]: continue
    
        # who did the winners play in the final rounds
        final = list(x for x in rs[-1] if any(w in x for w in ws))
    
        printf("winners = {mw}")
        printf("rounds = {rs}")
        printf("matches = {matches}")
        printf("scores = {ss}")
        printf("victors matches in the final round = {final}")
        printf()
    

    Solution: The winning players were Colle and Dragon. In the final round Colle played French and Dragon played Bishop.

    There is only one possible sequence of rounds, but there are three possible outcomes for the matches (distinguished by the numbers in square brackets below):

    Round 1: AvF (draw), BvE (draw), CvD (C wins [1, 2], D wins [3])
    Round 2: AvB (draw), CvE (C wins [1, 3], E wins [2]), DvF (draw)
    Round 3: AvC (A wins [1], C wins [2, 3]), BvF (B wins), DvE (draw)
    Round 4: AvD (D wins [1, 2], A wins [3]), BvC (draw), EvF (draw)
    Round 5: AvE (E wins [1, 3], A wins[2]), BvD (D wins), CvF (draw)

    The final scores are always: C and D, 3 points; B and E 2½ points; A and F, 2 points.

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: