Sunday Times Teaser 2714 – Group of Death

by Nick MacKinnon

In a Champions League four teams play each other twice with the top two teams going through to the next stage. If teams are equal on points, their positions are determined by their games against each other.

After five games each in one such contest the order was (A, B, C, D), each with a different number of points, A was certain to go through but teams B and C could still lead the group. But the last two games were draws.

All games had different results; none with more than 5 goals; the total goals for and against team D were equal; team A scored fewer goals than B, C or D, while team D scored more goals that A, B or C.

What were the results of the two games B v C?

One Comment Leave one →

brian gladman permalink

This was a really laborious programming exercise, which would have taken even longer without help from the guys here. Its quite possible that Jim Randell’s football class in his enigma.py could make a better job of it but I felt that would be like cheating. I could write my own generic solution but I don’t like football teasers so I am not inclined to do this!


from itertools import product, combinations
from os import path
from pickle import load, dump

# debug and speed up of first phase by saving its results
debug = False
saved = False
dump_file = path.dirname(__file__) + r'res.dmp'

# the 12 games will be in a list in the following order 
# da db dc ad bd cd ca cb ac bc ba ab

# the names of the four teams
A, B, C, D = 0, 1, 2, 3

# map the teams playing a game to the game position in the list of games
ix = { (D, A): 0, (D, B): 1, (D, C): 2, (A, D): 3, (B, D): 4, (C, D): 5,
       (C, A): 6, (C, B): 7, (A, C): 8, (B, C): 9, (B, A):10, (A, B):11 }

# map the game position in the list of games to the teams that play it
xi = { 0: (D, A), 1: (D, B), 2: (D, C), 3: (A, D), 4: (B, D), 5: (C, D),
       6: (C, A), 7: (C, B), 8: (A, C), 9: (B, C), 10:(B, A), 11:(A, B) } 

# list the positions of the games for each team, three in which it is the
# first player listed and three for which it is the second player
a_i = ( (ix[(A, B)],  ix[(A, C)], ix[(A, D)]), 
        (ix[(B, A)],  ix[(C, A)], ix[(D, A)]) )
b_i = ( (ix[(B, A)],  ix[(B, C)], ix[(B, D)]), 
        (ix[(A, B)],  ix[(C, B)], ix[(D, B)]) )
c_i = ( (ix[(C, A)],  ix[(C, B)], ix[(C, D)]), 
        (ix[(A, C)],  ix[(B, C)], ix[(D, C)]) )
d_i = ( (ix[(D, A)],  ix[(D, B)], ix[(D, C)]), 
        (ix[(A, D)],  ix[(B, D)], ix[(C, D)]) )

# a dictionary to change a score to the other team's point of view
rev = { 'w': 'l', 'd':'d', 'l':'w' }

res = []
if not saved:
  # consider all outcomes of the 12 games in terms of win, draw or loss
  for p in product(('w', 'd', 'l'), repeat=12):
    # find the 6 games played by each team with the team first in the games  
    g_a = tuple(p[i] for i in a_i[0]) + tuple(rev[p[i]] for i in a_i[1])
    g_b = tuple(p[i] for i in b_i[0]) + tuple(rev[p[i]] for i in b_i[1])
    g_c = tuple(p[i] for i in c_i[0]) + tuple(rev[p[i]] for i in c_i[1])
    g_d = tuple(p[i] for i in d_i[0]) + tuple(rev[p[i]] for i in d_i[1])
    # calculate the points for each team
    pt_a = 3 * g_a.count('w') + g_a.count('d')
    pt_b = 3 * g_b.count('w') + g_b.count('d')
    pt_c = 3 * g_c.count('w') + g_c.count('d')
    pt_d = 3 * g_d.count('w') + g_d.count('d')
    # skip solutions if the points order is not correct
    if pt_a > pt_b > pt_c > pt_d:
      # every team must have at least one draw
      if any(x.count('d') == 0 for x in (g_a, g_b, g_c, g_d)):
        continue
      # there must be exactly three draws
      if sum(x.count('d') for x in (g_a, g_b, g_c, g_d)) != 6:
        continue
      # B must be able to overtake A if A lose their their last game
      # and B win their own. But if A lose their last game and C win 
      # their own, C cannot overtake A since A cannot be eliminated
      if pt_a > pt_b + 3 or pt_a != pt_c + 3:
        continue
      res += [p]
  with open(dump_file, 'wb') as f:
    dump(res, f)
else:
  with open(dump_file, 'rb') as f:
    res = load(f)

# find the points for a team given the team index and the list of games
def pt(ix, g):
  p1 = sum((3 if g[i][0] > g[i][1] else 1 if g[i][0] == g[i][1] else 0) 
                for i in ix[0])
  p2 = sum((3 if g[i][0] < g[i][1] else 1 if g[i][0] == g[i][1] else 0) 
                for i in ix[1])
  return p1 + p2

# rank two teams on points or if their points are equal
# on their points in games against each other
def rank(t1, t2, ix1, ix2, g):
  p1, p2 = pt(ix1, g), pt(ix2, g)
  if p1 != p2:
    return p1 > p2
  m1, m2 = g[ix[(t1, t2)]], g[ix[(t2, t1)]]
  p1 = (3 if m1[0] > m1[1] else 0) + (0 if m2[0] > m2[1] else 3)
  p2 = (0 if m1[0] > m1[1] else 3) + (3 if m2[0] > m2[1] else 0)
  return p1 > p2

# results   = the win, draw, loss list for the 12 games
# wl_scores = the 9 scores that for the non-drawn games
# d_scores  = the 3 scores for the drawn matches
# g         = results of the games played so far
# sol       = solutions for B v C games 
def play(res, wl_scores, d_scores, g, l):
  # have we finished?
  if l == 12:
    # find the total goals scored by each team
    ag = sum(g[i][0] for i in a_i[0]) + sum(g[i][1] for i in a_i[1])
    bg = sum(g[i][0] for i in b_i[0]) + sum(g[i][1] for i in b_i[1])
    cg = sum(g[i][0] for i in c_i[0]) + sum(g[i][1] for i in c_i[1])
    dg = sum(g[i][0] for i in d_i[0]) + sum(g[i][1] for i in d_i[1])
    # A scores the fewest and D the most
    if ag >= min(bg, cg, dg) or dg <= max(ag, bg, cg):
      return

    # find the positions of the three draws in the list of games    
    dr = [i for i, m in enumerate(g) if m[0] == m[1]]
    # consider them in pairs
    for i1, i2 in combinations(dr, 2):
      # and find two pairs that among them involve all four teams
      if len(set(xi[i1]) | set(xi[i2])) == 4:
        h = g[:]
        # change the drawn game involving A to a loss for A
        if A in xi[i1]:
          h[i1] = (0, 3) if A == xi[i1][0] else (3, 0)
        else:
          h[i2] = (0, 3) if A == xi[i2][0] else (3, 0)
        # change the drawn game involving C to a win for C 
        if C in xi[i2]:
          h[i2] = (0, 3) if C == xi[i2][1] else (3, 0)
        else:
          h[i1] = (0, 3) if C == xi[i1][1] else (3, 0)
        # C must be able to win
        if rank(C, A, c_i, a_i, h):
          # but A must then come second or else it would
          # be eliminated
          if rank(A, B, a_i, b_i, h):
            break
    else:
      # no solution for these games
      return
    
    yield tuple(sorted(((g[7][1], g[7][0]), g[9])))
    if debug:
      # output a solution
      print(     '      ', g[ix[(A, B)]], g[ix[(A, C)]], g[ix[(A, D)]])
      print(g[ix[(B, A)]],      '      ', g[ix[(B, C)]], g[ix[(B, D)]])
      print(g[ix[(C, A)]], g[ix[(C, B)]],      '      ', g[ix[(C, D)]])
      print(g[ix[(D, A)]], g[ix[(D, B)]], g[ix[(D, C)]],      '      ')
      print()
  
  else:
    # if all D's games have been played
    if l == 6:
      # check that goals for and against D are equal
      dg = sum(g[i][0] for i in d_i[0]) + sum(g[i][1] for i in d_i[1])
      dd = sum(g[i][1] for i in d_i[0]) + sum(g[i][0] for i in d_i[1])
      if dg != dd:
        return
    if res[l] == 'd':
      # select a score giving a draw and continue to the next game
      for s in d_scores:
        yield from play(res, wl_scores, d_scores - set((s,)), g + [s], l + 1)
    else:
      # select a score giving a win or loss and continue to the next game
      for s in wl_scores:
        t = s if res[l] == 'w' else (s[1], s[0])
        yield from play(res, wl_scores - set((s,)), d_scores, g + [t], l + 1)

# winning scores
ws = set(((1, 0), (2, 0), (2, 1), (3, 0), (3, 1), 
         (3, 2), (4, 0), (4, 1), (5, 0)))
# scores for draws
ds = set(((0, 0), (1, 1), (2, 2)))
# for each win, draw, loss result, look for 12 matching game scores  
sol = set()
for i, r in enumerate(res):
  for s in play(r, ws, ds, [], 0):
    sol.add(s)
for s in sol:
  print('Scores when B plays C are {0[0]:} and {0[1]:}'.format(s))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

from itertools import product, combinations

from os import path

from pickle import load, dump

# debug and speed up of first phase by saving its results

debug = False

saved = False

dump_file = path.dirname(__file__) + r'res.dmp'

# the 12 games will be in a list in the following order

# da db dc ad bd cd ca cb ac bc ba ab

# the names of the four teams

A, B, C, D = 0, 1, 2, 3

# map the teams playing a game to the game position in the list of games

ix = { (D, A): 0, (D, B): 1, (D, C): 2, (A, D): 3, (B, D): 4, (C, D): 5,

(C, A): 6, (C, B): 7, (A, C): 8, (B, C): 9, (B, A):10, (A, B):11 }

# map the game position in the list of games to the teams that play it

xi = { 0: (D, A), 1: (D, B), 2: (D, C), 3: (A, D), 4: (B, D), 5: (C, D),

6: (C, A), 7: (C, B), 8: (A, C), 9: (B, C), 10:(B, A), 11:(A, B) }

# list the positions of the games for each team, three in which it is the

# first player listed and three for which it is the second player

a_i = ( (ix[(A, B)], ix[(A, C)], ix[(A, D)]),

(ix[(B, A)], ix[(C, A)], ix[(D, A)]) )

b_i = ( (ix[(B, A)], ix[(B, C)], ix[(B, D)]),

(ix[(A, B)], ix[(C, B)], ix[(D, B)]) )

c_i = ( (ix[(C, A)], ix[(C, B)], ix[(C, D)]),

(ix[(A, C)], ix[(B, C)], ix[(D, C)]) )

d_i = ( (ix[(D, A)], ix[(D, B)], ix[(D, C)]),

(ix[(A, D)], ix[(B, D)], ix[(C, D)]) )

# a dictionary to change a score to the other team's point of view

rev = { 'w': 'l', 'd':'d', 'l':'w' }

res = []

if not saved:

# consider all outcomes of the 12 games in terms of win, draw or loss

for p in product(('w', 'd', 'l'), repeat=12):

# find the 6 games played by each team with the team first in the games

g_a = tuple(p[i] for i in a_i[0]) + tuple(rev[p[i]] for i in a_i[1])

g_b = tuple(p[i] for i in b_i[0]) + tuple(rev[p[i]] for i in b_i[1])

g_c = tuple(p[i] for i in c_i[0]) + tuple(rev[p[i]] for i in c_i[1])

g_d = tuple(p[i] for i in d_i[0]) + tuple(rev[p[i]] for i in d_i[1])

# calculate the points for each team

pt_a = 3 * g_a.count('w') + g_a.count('d')

pt_b = 3 * g_b.count('w') + g_b.count('d')

pt_c = 3 * g_c.count('w') + g_c.count('d')

pt_d = 3 * g_d.count('w') + g_d.count('d')

# skip solutions if the points order is not correct

if pt_a > pt_b > pt_c > pt_d:

# every team must have at least one draw

if any(x.count('d') == 0 for x in (g_a, g_b, g_c, g_d)):

continue

# there must be exactly three draws

if sum(x.count('d') for x in (g_a, g_b, g_c, g_d)) != 6:

continue

# B must be able to overtake A if A lose their their last game

# and B win their own. But if A lose their last game and C win

# their own, C cannot overtake A since A cannot be eliminated

if pt_a > pt_b + 3 or pt_a != pt_c + 3:

continue

res += [p]

with open(dump_file, 'wb') as f:

dump(res, f)

else:

with open(dump_file, 'rb') as f:

res = load(f)

# find the points for a team given the team index and the list of games

def pt(ix, g):

p1 = sum((3 if g[i][0] > g[i][1] else 1 if g[i][0] == g[i][1] else 0)

for i in ix[0])

p2 = sum((3 if g[i][0] < g[i][1] else 1 if g[i][0] == g[i][1] else 0)

for i in ix[1])

return p1 + p2

# rank two teams on points or if their points are equal

# on their points in games against each other

def rank(t1, t2, ix1, ix2, g):

p1, p2 = pt(ix1, g), pt(ix2, g)

if p1 != p2:

return p1 > p2

m1, m2 = g[ix[(t1, t2)]], g[ix[(t2, t1)]]

p1 = (3 if m1[0] > m1[1] else 0) + (0 if m2[0] > m2[1] else 3)

p2 = (0 if m1[0] > m1[1] else 3) + (3 if m2[0] > m2[1] else 0)

return p1 > p2

# results = the win, draw, loss list for the 12 games

# wl_scores = the 9 scores that for the non-drawn games

# d_scores = the 3 scores for the drawn matches

# g = results of the games played so far

# sol = solutions for B v C games

def play(res, wl_scores, d_scores, g, l):

# have we finished?

if l == 12:

# find the total goals scored by each team

ag = sum(g[i][0] for i in a_i[0]) + sum(g[i][1] for i in a_i[1])

bg = sum(g[i][0] for i in b_i[0]) + sum(g[i][1] for i in b_i[1])

cg = sum(g[i][0] for i in c_i[0]) + sum(g[i][1] for i in c_i[1])

dg = sum(g[i][0] for i in d_i[0]) + sum(g[i][1] for i in d_i[1])

# A scores the fewest and D the most

if ag >= min(bg, cg, dg) or dg <= max(ag, bg, cg):

return

# find the positions of the three draws in the list of games

dr = [i for i, m in enumerate(g) if m[0] == m[1]]

# consider them in pairs

for i1, i2 in combinations(dr, 2):

# and find two pairs that among them involve all four teams

if len(set(xi[i1]) | set(xi[i2])) == 4:

h = g[:]

# change the drawn game involving A to a loss for A

if A in xi[i1]:

h[i1] = (0, 3) if A == xi[i1][0] else (3, 0)

else:

h[i2] = (0, 3) if A == xi[i2][0] else (3, 0)

# change the drawn game involving C to a win for C

if C in xi[i2]:

h[i2] = (0, 3) if C == xi[i2][1] else (3, 0)

else:

h[i1] = (0, 3) if C == xi[i1][1] else (3, 0)

# C must be able to win

if rank(C, A, c_i, a_i, h):

# but A must then come second or else it would

# be eliminated

if rank(A, B, a_i, b_i, h):

break

else:

# no solution for these games

return

yield tuple(sorted(((g[7][1], g[7][0]), g[9])))

if debug:

# output a solution

print( ' ', g[ix[(A, B)]], g[ix[(A, C)]], g[ix[(A, D)]])

print(g[ix[(B, A)]], ' ', g[ix[(B, C)]], g[ix[(B, D)]])

print(g[ix[(C, A)]], g[ix[(C, B)]], ' ', g[ix[(C, D)]])

print(g[ix[(D, A)]], g[ix[(D, B)]], g[ix[(D, C)]], ' ')

print()

else:

# if all D's games have been played

if l == 6:

# check that goals for and against D are equal

dg = sum(g[i][0] for i in d_i[0]) + sum(g[i][1] for i in d_i[1])

dd = sum(g[i][1] for i in d_i[0]) + sum(g[i][0] for i in d_i[1])

if dg != dd:

return

if res[l] == 'd':

# select a score giving a draw and continue to the next game

for s in d_scores:

yield from play(res, wl_scores, d_scores - set((s,)), g + [s], l + 1)

else:

# select a score giving a win or loss and continue to the next game

for s in wl_scores:

t = s if res[l] == 'w' else (s[1], s[0])

yield from play(res, wl_scores - set((s,)), d_scores, g + [t], l + 1)

# winning scores

ws = set(((1, 0), (2, 0), (2, 1), (3, 0), (3, 1),

(3, 2), (4, 0), (4, 1), (5, 0)))

# scores for draws

ds = set(((0, 0), (1, 1), (2, 2)))

# for each win, draw, loss result, look for 12 matching game scores

sol = set()

for i, r in enumerate(res):

for s in play(r, ws, ds, [], 0):

sol.add(s)

for s in sol:

print('Scores when B plays C are {0[0]:} and {0[1]:}'.format(s))

Sunday Times Teaser 2714 – Group of Death

by Nick MacKinnon

Leave a comment to brian gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta