S2T2

Jim Randell 11:43 am on 11 August 2020 Permalink Reply
Tags: by: John Feather ( 3 )   

• 

  Jim Randell 11:44 am on 11 August 2020 Permalink | Reply

  When we look at the table we can spot teams that might have been knocked out in the first round. The number of goals for and against must be different (no draws) and neither must be more than 5. We can then choose 8 such teams, and their values in the table give the scores in the matches. We then choose 8 of the remaining teams to be their opponents and see if we can construct a new table for the next round of the tournament (which will have half as many matches). And so on until we reach the last 2 teams.

  This Python 3 program runs in 1.2s.

  Run: [ @repl.it ]

  from enigma import subsets, diff, ordered, flatten, join, printf
  
  # the total goals scored/conceded
  gs0 = dict(
    A=(5, 6), B=(14, 0), C=(15, 8), D=(2, 4), E=(1, 3), F=(0, 5), G=(4, 6), H=(1, 4),
    I=(1, 2), J=(12, 12), K=(6, 5), L=(0, 1), M=(4, 5), N=(1, 5), O=(2, 3), P=(7, 6),
  )
  
  # do the list of <ls>, <ws> make a set of matches using goals scored/conceded in <gs>?
  # return list of (<winner> + <loser>, (<scored>, <conceded>))
  # and a new version of <gs> for the next round
  def matches(gs, ls, ws):
    ms = list()
    d = dict()
    for (w, l) in zip(ws, ls):
      ((fw, aw), (fl, al)) = (gs[w], gs[l])
      (f, a) = (fw - al, aw - fl)
      if f < 0 or a < 0: return (None, None)
      ms.append((w + l, (al, fl)))
      d[w] = (f, a)
    return (ms, d)
  
  # allowable score:
  # no side scores more than 5 goals, and no draws
  score = lambda x, y: not(x > 5 or y > 5 or x == y)
  
  # play out a tournament
  # k = number of matches in this round
  # gs = total number of goals scored in the remaining rounds
  # ms = match outcomes in each round
  # ss = scores used so far
  def tournament(k, gs, ms=list(), ss=set()):
    # how many matches?
    if k == 1:
      # there should be 2 teams
      (x, y) = gs.keys()
      ((fx, ax), (fy, ay)) = (gs[x], gs[y])
      if fx == ay and ax == fy and score(fx, ax):
        yield ms + [[(x + y, (fx, ax)) if fx > ax else (y + x, (fy, ay))]]
    else:
      # teams that can be knocked out in this round
      teams = list(k for (k, (f, a)) in gs.items() if score(f, a))
      # choose the losers
      for ls in subsets(teams, size=k):
        # choose the winners from the remaining teams
        for ws in subsets(diff(gs.keys(), ls), size=k, select="P"):
          (ms_, gs_) = matches(gs, ls, ws)
          if not gs_: continue
          ss_ = set(ordered(*xs) for (ts, xs) in ms_)
          if ss_.intersection(ss): continue
          yield from tournament(k // 2, gs_, ms + [ms_], ss.union(ss_))
          
  
  # there are 8 matches in the first round
  for ms in tournament(8, gs0):
    # check K is knocked out by the champions
    champ = ms[-1][0][0][0]
    if not(champ + 'K' in (ts for (ts, xs) in flatten(ms))): continue
    # output the tournament
    for (i, vs) in enumerate(ms, start=1):
      printf("Round {i}: {vs}", vs=join((f"{t[0]}v{t[1]} = {x}-{y}" for (t, (x, y)) in sorted(vs)), sep="; "))
    printf()
  

  Solution: The semi-finals were: B vs K = 3-0; C vs J = 5-3.

  So the final was: B vs C = 2-0, and B were the champions.

  The strategy given above finds two possible tournaments, but only in one of them is K knocked out by the eventual champions.

  LikeLike

  • 

    Frits 8:13 pm on 18 August 2020 Permalink | Reply

    @Jim

    Did you also solve the puzzle manually?

    It is not so difficult to determine who is playing whom in the semi-finals.
    The scores are not easy to determine.

    LikeLike

    • 

      Jim Randell 12:00 pm on 19 August 2020 Permalink | Reply

      @Frits: I didn’t do a manual solution for this one. But I imagine the fact there are only 15 possible scores for the 15 games must make things a bit easier. (This is something I didn’t use in my program).

      LikeLike