Enigmatic Code

Programming Enigma Puzzles

Enigma 993: If you lose…

From New Scientist #2148, 22nd August 1998 [link]

Each year the four football teams A, B, C and D play each other once, getting 3 points for a win and 1 for a draw. At the end of the year the teams are ordered by total points and those with equal points by goal difference. Any still not ordered are then ordered by goals scored and then, if necessary, by the result of the match between the two to be ordered. Any still not ordered draw lots. The top two teams with a prize.

The order the games are played in can vary, except that A always plays its opponents in the order B, C, D, and A vs B is always the very first match of the year.

By an amazing coincidence the following has happened in 1996, 1997 and 1998. One hour before A v C kicks off, team A’s manager/mathematician announces to the team that if they lose to C then they cannot possibly get a prize. Team A has gone on to win a prize in spite of losing to D.

1. Is it possible in 1996 A vs C was the 3rd game of the tournament?

2. In 1997, A vs C was the 4th games of the tournament. Name the two teams that you can say for certain met in the 2nd or 3rd game of the tournament.

3. In 1998, a total of 4 goals was scored in the tournament. What was the score in B vs C?

[enigma993]

One response to “Enigma 993: If you lose…

  1. Jim Randell 13 September 2019 at 7:40 am

    I think this one is probably easier to do manually than with a program, but as I’ve written one here it is.

    Q1 and Q2 are relatively straightforward, Q3 is more convoluted.

    This Python 3 program uses the [[ Football() ]] helper class from the enigma.py library. It runs in 472ms.

    Run: [ @repl.it ]

    from collections import defaultdict
    from functools import cmp_to_key
    from enigma import Football, subsets, unpack, Accumulator, multiset, irange, update, compare, join, args, printf
    
    # logical implication: p -> q
    implies = lambda p, q: not(p) or q
    
    # scoring system
    football = Football(games='wdl', points=dict(w=3, d=1))
    
    # labels for the teams
    teams = (A, B, C, D) = tuple("ABCD")
    
    # keys for the matches
    ks = list(x + y for (x, y) in subsets(teams, size=2))
    
    # consider possible match outcomes
    rs = list()
    for ms in football.games(repeat=len(ks)):
      ms = dict(zip(ks, ms))
      # compute the points for each team
      pts = dict((t, football.extract_table(ms, t).points) for t in teams)
      # how many teams did better than A
      better = sum(pts[x] > pts[A] for x in teams if x != A)
      # record the outcome (matches, better)
      rs.append((ms, better))
    
    # find cases where if we know the outcomes of matches in <ks>, then (AvC = lose) -> (no prize)
    def extract(ks):
      f = unpack(lambda ms, better: tuple(ms[k] for k in ks))
      g = unpack(lambda ms, better: implies(ms["AC"] == 'l', better > 1))
      d = defaultdict(set)
      for r in rs:
        d[f(r)].add(g(r))
      # look for keys that only give True
      for (k, v) in d.items():
        if v != set([True]): continue
        # select outcomes with this key, and where AvD = lose and A wins a prize
        h = unpack(lambda ms, better: ms["AD"] == 'l' and better < 2)
        for r in rs:
          if f(r) == k and h(r):
            yield r[0]
    
    
    # question 1
    def q1():
      # record number of viable outcomes
      ans = 0
      # match 1 is AvB, match 3 is AvC
      # match 2 is one of BvC, BvD, CvD
      for k2 in ["BC", "BD", "CD"]:
        for ms in extract(["AB", k2]):
          printf("[q1: k2={k2} -> {ms}]")
          ans += 1
    
      printf("q1: {x}", x=("possible" if ans > 0 else "not possible"))
      printf()
    
    
    # question 2
    def q2():
      # look for matches that appear in all viable outcomes
      ans = Accumulator(fn=lambda s, x: s.intersection(x))
      # match 1 is AvB, match 4 is AvC
      # consider possible 2nd, 3rd matches from BvC, BvD, CvD
      for (k2, k3) in subsets(["BC", "BD", "CD"], size=2):
        for ms in extract(["AB", k2, k3]):
          printf("[q2: k2={k2}, k3={k3} -> {ms}]")
          ans.accumulate(set([k2, k3]))
    
      printf("q2: {ans}", ans=(join((x + "v" + y for (x, y) in sorted(ans.value)), sep=" ") if ans.value else "<none>"))
      printf()
    
    
    # generate scores for matches ms, with t total goals scores
    def scores(ms, t, ss=dict()):
      if not ms:
        if t == 0:
          yield ss
      else:
        # choose a match
        ms = dict(ms)
        (k, v) = ms.popitem()
        if v in 'wl':
          for x in irange(1, t):
            for y in irange(0, min(x - 1, t - x)):
              s = ((x, y) if v == 'w' else (y, x))
              yield from scores(ms, t - x - y, update(ss, [k], [s]))
        elif v in 'd':
          for x in irange(0, t // 2):
            yield from scores(ms, t - x - x, update(ss, [k], [(x, x)]))
    
    # compute the order of the teams given match outcomes <ms> and scores <ss>
    def order(ms, ss):
      # calculate the points
      pts = dict((t, football.extract_table(ms, t).points) for t in teams)
      # calculate goals (for, against)
      goals = dict((t, football.extract_goals(ss, t)) for t in teams)
    
      # compare performance in game x vs. y
      def game(x, y):
        if x < y:
          (fx, fy) = ss[x + y]
        else:
          (fy, fx) = ss[y + x]
        return compare(fx, fy)
    
      # compare teams on points, then goal difference, then goals scored, then performance in the match between them
      cmp = lambda x, y: (
        compare(pts[x], pts[y]) or
        compare(goals[x][0] - goals[x][1], goals[y][0] - goals[y][1]) or
        compare(goals[x], goals[y]) or
        game(x, y)
      )
    
      # order the teams (winner first)
      return sorted(teams, key=cmp_to_key(cmp), reverse=1)
    
    # question 3
    def q3():
      # look for scores in the BvC match
      ans = multiset()
      # match 1 is AvB
      # and before AvC is played some subset of BvC, BvD, CvD are also played
      for ks in subsets(["BC", "BD", "CD"]):
        for ms in extract(["AB"] + list(ks)):
          # but there can't be more than 4 matches won/lost
          if sum(m in 'wl' for m in ms.values()) > 4: continue
          # find possible scores for each game
          for ss in scores(ms, 4):
            # and check A wins a prize
            r = order(ms, ss)
            if r.index('A') > 1: continue
            printf("[q3: ks={ks} -> {ss} {r}]")
            ans.add((ms["BC"], ss["BC"]))
    
      for ((m, s), n) in ans.most_common():
        printf("q3: BvC = {m}:{s} [{n} solutions]")
      printf()
    
    
    arg = join(args("123", 0))
    if "1" in arg: q1()
    if "2" in arg: q2()
    if "3" in arg: q3()
    

    Solution: (1) No, it is not possible that A vs C was the third game of the tournament. (2) The C vs D match must have been played as the second or third game. (3) The score in the B vs C match was 0-0.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: