# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1209: The league game

From New Scientist #2365, 19th October 2002 [link]

Lloyd and Owen have a new game. They imagine there is a football league with four teams, A, B, C and D. Each team plays every other team once, scoring 1 point for a draw and 2 for a win. The teams are ordered in their league by points and, where there are equal points, by goal difference.

At the start of their game, Lloyd has six cards in his hand, each with a different match on it, A v B, A v C, etc. The game consists of six rounds, numbered 1 to 6 in order. In each round Lloyd chooses one of the cards in his hand and lays it on the table. Owen writes a score on it, for example if the card was A v B, he might write A2 v B1. They then work out the league table for the matches played so far and see who is top. They also work out if it is certain that the team will be top after all the six matches have been played, whatever the scores of the remaining matches. If it is certain and it was not certain in the previous round then that round is called the “Decisive” round. That completes the round.

Lloyd plays so as to make the Decisive round as late as possible and Owen aims to make it as early as possible.

Question 1: If they both play as well as possible, what is the number of the Decisive round?

Question 2: If they change the rules so that a team gets 3 points for a win, what then is the number of the Decisive round?

[enigma1209]

Advertisements

### One response to “Enigma 1209: The league game”

1. Jim Randell 19 August 2015 at 11:56 am

I didn’t particularly like this puzzle. I’m not usually a fan of the “football league table”-type puzzle, and I found this one quite a tricky one to write a program for, and while it looks OK I’m not completely confident in it.

This Python program examines the possible game play. It runs in 5.6s. The number of points for a win can be specified on the command line (default = 2).

```from enigma import Football, chunk, diff, printf

# points for a win (2 or 3)
import sys
W = (2 if len(sys.argv) < 2 else int(sys.argv[1]))
printf("[win = {W} points]")

# scoring regime
football = Football(points={ 'w': W, 'd': 1 })

# teams and matches
teams = 'ABCD'
matches = ('AB', 'AC', 'AD', 'BC', 'BD', 'CD')

# number of matches each team plays
P = len(teams) - 1

# marker for indecisive tournaments
X = len(matches) + 1

# construct the table for a sequence
def table(s):
t = list()
# dictionary of matches
d = dict(chunk(s, 2))
# compute tables
for x in teams:
ms = tuple(k for k in d.keys() if x in k)
t.append(football.table(tuple(d[k] for k in ms), tuple(k.index(x) for k in ms)))
# sort it
t.sort(key=lambda x: (x.points, x.w, x.d, x.l), reverse=True)
return t

# is the sequence decisive
def is_decisive(s):
t = table(s)
# is there a leader?
v = t[0].points
vs = tuple(x for x in t if x.points == v)
if len(vs) > 1:
# if there are no wins we can't choose on goal difference
if all(x.w == 0 for x in vs):
return False
# can anyone catch up with the leader?
return all(x.points + W * (P - x.played) < v for x in t[1:])

# play the game
# return the number of the decisive round
def play(s, ms):

(n, r) = divmod(len(s), 2)
if r == 0:

# is this round decisive?
if is_decisive(s):
return n

# are there any matches left?
if not ms:
return X

# player 1: choose a match
# try to make the decisive round as late as possible
return max(play(s + [x], diff(ms, [x])) for x in ms)

else:

# player 2: choose an outcome for the match
# try to make the decisive round as early as possible
return min(play(s + [x], ms) for x in 'wdl')

# play the game, starting with the first match
n = play(list(matches[:1]), list(matches[1:]))
printf("decisive round = {n}")
```

Solution: Q1. With 2 points for a win the decisive round is round 6; Q2. With 3 points for a win the decisive round is round 5.