# Enigmatic Code

Programming Enigma Puzzles

## Enigma 286: Final analysis

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

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]

### 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.