Sunday Times Teaser 2721 – Milliner’s Hat-Trick

by Nick MacKinnon

Four groups of four teams each play in a football tournament in which teams within a group play each other once. So far each team has played two matches and the distribution of points within each group is different. Also two teams in each group are level on points and have their positions set by their goals scored.

Nine players have each scored 1 goal, Milliner has scored 4 (including a hat trick) and Orlando has scored 2, although his team is not top of its group.

What are the results of the games played by Milliner’s and Orlando’s teams?

One Comment Leave one →

brian gladman permalink

This one is a very laborious programming exercise. This solution uses my football solver class


from itertools import combinations
from collections import defaultdict

# convert a dictionary of matches to scores for each team 
def get_results(d):
  gms = defaultdict(list)
  for n, (x, y) in d.items():
    gms[n[0]].append((x, y))
    gms[n[1]].append((y, x))
  return [sorted(gms[x]) for x in 'ABCD']

from football import Football

# a team score of 4 in one match, 2 in another, all others being at most one goal
allowed_scores = {(0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (0, 3), (1, 3), 
                  (0, 4), (1, 4)}

f = Football('ABCD', outcomes='uldw', scoring={'w':3, 'd':1}, order="pts/gf", sep='')

# dictionaries indexed on points distributions, one
# giving the minimum necessary goals to achieve the
# distribution, the other giving the set of possible
# match results for the distribution
dpd = dict()
mpd = defaultdict(set)

# generate outcomes for four teams A, B, C and D with
# each team playing two games ending with leaague
# table positions such that A >= B >= C >= D
for d1 in f.games(dict(), 'A'):
  At = f.table(d1, 'A')
  if At.p != 2:
    continue
  for d2 in f.games(d1, 'B'):
    Bt = f.table(d2, 'B')
    if Bt.p != 2 or At.pts < Bt.pts:
      continue

    for d3 in f.games(d2, 'C'):
      Ct = f.table(d3, 'C')
      if Ct.p != 2 or Bt.pts < Ct.pts:
        continue

      for d4 in f.games(d3, 'D'):
        Dt = f.table(d4, 'D')
        if Dt.p != 2 or Ct.pts < Dt.pts:
          continue

        tb = tuple((At, Bt, Ct, Dt))

        # find combinations with exactly two teams equal on points
        eqt = [(i, j) for (i, x), (j, y) in 
               combinations(enumerate(tb), 2) if x.pts == y.pts]
        if len(eqt) != 1:
          continue
        eqt = eqt[0]

        # find possible maatch scores for the four games
        for d5 in f.matches(d4, 'A', (0, 4), (0, 4)):
          At = f.table(d5, 'A')
          for d6 in f.matches(d5, 'B', (0, 4), (0, 4)):
            Bt = f.table(d6, 'B') 
            for d7 in f.matches(d6, 'C', (0, 4), (0, 4)):
              Ct = f.table(d7, 'C') 
              for d8 in f.matches(d7, 'D', (0, 4), (0, 4)):
                Dt = f.table(d8, 'D')

                # the scores must allow the rank of the
                # equal teams to be resolved 
                tb = tuple((At, Bt, Ct, Dt))
                if tb[eqt[0]].gf <= tb[eqt[1]].gf:
                  continue

                # check that all the scores in matches are
                # within those allowed 
                _, mchs, gf = f.results(d8, ordered=True)
                if not set(mchs) <= allowed_scores:
                  continue

                # find the minimum goals required for each distribution 
                pts4 = tuple(x.pts for x in tb)
                dpd[pts4] = min(gf, dpd.setdefault(pts4, gf))
                # save possible match results for each distribution
                nms, mchs, gf = f.results(d8)
                mpd[pts4].add((nms, tuple(mchs)))

# output the minimum goals for each points distribution
print("Distributions minimum points")
for pts, min_g in sorted(dpd.items()):
  print(f" {pts}       {min_g}")
print()

# we need four 'four match' groups with different distributions
for pd1, pd2, pd3, pd4 in combinations(sorted(mpd.keys()), 4):

  # consider possible matches for each distribution, tracking
  # the total goals across all the matches 

  for n1, m1 in mpd[pd1]:
    g11 = sum(sum(x) for x in m1)

    for n2, m2 in mpd[pd2]:
      g12 = g11 + sum(sum(x) for x in m2)
      if g12 > 9:
        continue
      
      for n3, m3 in mpd[pd3]:
        g13 = g12 + sum(sum(x) for x in m3)
        if g13 > 12:
          continue
        
        for n4, m4 in mpd[pd4]:
          g14 = g13 + sum(sum(x) for x in m4)

          # there must be 15 goals in total and one group with a hat trick
          mg4 = [m1, m2, m3, m4]
          if g14 != 15 or sum(sum(1 for x in m if 3 in x) for m in mg4) != 1:
            continue

          # compose the results for each of the four 'four match' groups
          dg4 = [dict(), dict(), dict(), dict()]
          ng4 = [n1, n2, n3, n4]
          pg4 = [pd1, pd2, pd3, pd4]
          pts = [0] * 4
          for i, (n, m, p) in enumerate(sorted(zip(ng4, mg4, pg4), 
                key=lambda x: max(a for a, b in x[1]), reverse=True)):            
            dg4[i].update(zip(n, m))
            pts[i] = p

          # compile match results for each team 
          grpr = [get_results(dg4[i]) for i in range(4)]

          # the team with the hat trick must also score another goal
          mm3 = [r2 for r2 in grpr[0] if (r2[0][0], r2[1][0]) == (1, 3)]
          if mm3:
            mm3 = mm3[0]

            # there is a team, not top of its group, with a score of 2 in a match
            mm2 = [[r2 for j, r2 in enumerate(gr) if j and r2[1][0] == 2] for gr in grpr]
            mm2 = [x for x in mm2 if x]
            if mm2:
              print(f"Miliner's team: {mm3}, Orlando's team {mm2[0][0]}")
              for d, p in zip(dg4, pts):
                print(d, p)
              print()

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

from itertools import combinations

from collections import defaultdict

# convert a dictionary of matches to scores for each team

def get_results(d):

gms = defaultdict(list)

for n, (x, y) in d.items():

gms[n[0]].append((x, y))

gms[n[1]].append((y, x))

return [sorted(gms[x]) for x in 'ABCD']

from football import Football

# a team score of 4 in one match, 2 in another, all others being at most one goal

allowed_scores = {(0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (0, 3), (1, 3),

(0, 4), (1, 4)}

f = Football('ABCD', outcomes='uldw', scoring={'w':3, 'd':1}, order="pts/gf", sep='')

# dictionaries indexed on points distributions, one

# giving the minimum necessary goals to achieve the

# distribution, the other giving the set of possible

# match results for the distribution

dpd = dict()

mpd = defaultdict(set)

# generate outcomes for four teams A, B, C and D with

# each team playing two games ending with leaague

# table positions such that A >= B >= C >= D

for d1 in f.games(dict(), 'A'):

At = f.table(d1, 'A')

if At.p != 2:

continue

for d2 in f.games(d1, 'B'):

Bt = f.table(d2, 'B')

if Bt.p != 2 or At.pts < Bt.pts:

continue

for d3 in f.games(d2, 'C'):

Ct = f.table(d3, 'C')

if Ct.p != 2 or Bt.pts < Ct.pts:

continue

for d4 in f.games(d3, 'D'):

Dt = f.table(d4, 'D')

if Dt.p != 2 or Ct.pts < Dt.pts:

continue

tb = tuple((At, Bt, Ct, Dt))

# find combinations with exactly two teams equal on points

eqt = [(i, j) for (i, x), (j, y) in

combinations(enumerate(tb), 2) if x.pts == y.pts]

if len(eqt) != 1:

continue

eqt = eqt[0]

# find possible maatch scores for the four games

for d5 in f.matches(d4, 'A', (0, 4), (0, 4)):

At = f.table(d5, 'A')

for d6 in f.matches(d5, 'B', (0, 4), (0, 4)):

Bt = f.table(d6, 'B')

for d7 in f.matches(d6, 'C', (0, 4), (0, 4)):

Ct = f.table(d7, 'C')

for d8 in f.matches(d7, 'D', (0, 4), (0, 4)):

Dt = f.table(d8, 'D')

# the scores must allow the rank of the

# equal teams to be resolved

tb = tuple((At, Bt, Ct, Dt))

if tb[eqt[0]].gf <= tb[eqt[1]].gf:

continue

# check that all the scores in matches are

# within those allowed

_, mchs, gf = f.results(d8, ordered=True)

if not set(mchs) <= allowed_scores:

continue

# find the minimum goals required for each distribution

pts4 = tuple(x.pts for x in tb)

dpd[pts4] = min(gf, dpd.setdefault(pts4, gf))

# save possible match results for each distribution

nms, mchs, gf = f.results(d8)

mpd[pts4].add((nms, tuple(mchs)))

# output the minimum goals for each points distribution

print("Distributions minimum points")

for pts, min_g in sorted(dpd.items()):

print(f" {pts} {min_g}")

print()

# we need four 'four match' groups with different distributions

for pd1, pd2, pd3, pd4 in combinations(sorted(mpd.keys()), 4):

# consider possible matches for each distribution, tracking

# the total goals across all the matches

for n1, m1 in mpd[pd1]:

g11 = sum(sum(x) for x in m1)

for n2, m2 in mpd[pd2]:

g12 = g11 + sum(sum(x) for x in m2)

if g12 > 9:

continue

for n3, m3 in mpd[pd3]:

g13 = g12 + sum(sum(x) for x in m3)

if g13 > 12:

continue

for n4, m4 in mpd[pd4]:

g14 = g13 + sum(sum(x) for x in m4)

# there must be 15 goals in total and one group with a hat trick

mg4 = [m1, m2, m3, m4]

if g14 != 15 or sum(sum(1 for x in m if 3 in x) for m in mg4) != 1:

continue

# compose the results for each of the four 'four match' groups

dg4 = [dict(), dict(), dict(), dict()]

ng4 = [n1, n2, n3, n4]

pg4 = [pd1, pd2, pd3, pd4]

pts = [0] * 4

for i, (n, m, p) in enumerate(sorted(zip(ng4, mg4, pg4),

key=lambda x: max(a for a, b in x[1]), reverse=True)):

dg4[i].update(zip(n, m))

pts[i] = p

# compile match results for each team

grpr = [get_results(dg4[i]) for i in range(4)]

# the team with the hat trick must also score another goal

mm3 = [r2 for r2 in grpr[0] if (r2[0][0], r2[1][0]) == (1, 3)]

if mm3:

mm3 = mm3[0]

# there is a team, not top of its group, with a score of 2 in a match

mm2 = [[r2 for j, r2 in enumerate(gr) if j and r2[1][0] == 2] for gr in grpr]

mm2 = [x for x in mm2 if x]

if mm2:

print(f"Miliner's team: {mm3}, Orlando's team {mm2[0][0]}")

for d, p in zip(dg4, pts):

print(d, p)

print()

Sunday Times Teaser 2721 – Milliner’s Hat-Trick

by Nick MacKinnon

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta