Enigmatic Code

Programming Enigma Puzzles

Enigma 1236: United share the title

From New Scientist #2392, 26th April 2003 [link]

Albion, Borough, City, Rangers and United have played another tournament in which each team played each of the other teams once. Two matches took place on each of five successive Saturdays, each of the five teams having one Saturday without a match.

Three points were awarded for a win and one for a draw. Albion had a clear points lead after the first Saturday, likewise Borough after the second Saturday, City after the third and Rangers after the fourth; and United were joint leaders after the final Saturday.

Knowing this you would be able to deduce with certainty the results of both the matches played on the final Saturday if I told you which matches were played on that day.

Which matches were played on the final Saturday and what was the result for each one?

[enigma1236]

Advertisements

3 responses to “Enigma 1236: United share the title

  1. Jim Randell 3 May 2015 at 9:14 am

    We don’t need to bother with the actual scores in the matches, so here’s a solution that doesn’t use the Football() helper class from enigma.py. Instead of coding it as a bunch of nested loops I used a recursive routine, although even that gets a little involved.

    This Python 3 program runs in 115ms.

    from itertools import combinations, product
    from collections import defaultdict
    from enigma import compare, diff, printf
    
    # scoring regime
    score = { 'w': (3, 0), 'd': (1, 1), 'l': (0, 3) }
    
    # update points based on the (<match>, <result>) pairs in <gs>
    def points(pts, gs):
      pts = dict(pts)
      for (m, r) in gs:
        s = score[r]
        pts[m[0]] += s[0]
        pts[m[1]] += s[1]
      return pts
    
    # update dict <d> with (<key>, <value>) pairs <vs>
    def update(d, vs):
      d = dict(d)
      d.update(vs)
      return d
    
    # solve the matches for each week
    # pts - points for each team
    # ms - remaining matches
    # ls - leaders for each weak
    # cs - compare leaders to the rest
    # rs - results of matches
    # ws - matches played for each week
    def solve(pts, ms, ls, cs, rs, ws):
      # are we done?
      if not ms:
        # return the results and the matches played by week
        yield (rs, ws)
      else:
        # choose two disjoint remaining matches
        for (m1, m2) in combinations(ms, 2):
          if len(set(m1 + m2)) != 4: continue
          # choose outcomes for these matches
          for (r1, r2) in product('wdl', repeat=2):
            # update the points
            pts1 = points(pts, ((m1, r1), (m2, r2)))
            # compare the leader to the rest
            if compare(pts1[ls[0]], max(v for (k, v) in pts1.items() if k != ls[0])) == cs[0]:
              # solve for the remaining matches
              yield from solve(pts1, diff(ms, (m1, m2)), ls[1:], cs[1:], update(rs, ((m1, r1), (m2, r2))), ws + [(m1, m2)])
    
    # initial points
    pts = dict((t, 0) for t in 'ABCRU')
    # all matches
    matches = ('AB', 'AC', 'AR', 'AU', 'BC', 'BR', 'BU', 'CR', 'CU', 'RU')
    # record candidate solutions
    r = defaultdict(list)
    
    # generate results for each week
    for (rs, ws) in solve(pts, matches, 'ABCRU', (1, 1, 1, 1, 0), {}, []):
      printf("[ws={ws}, rs={rs}]")
      # record candidate solutions by the final matches and their results
      (m1, m2) = ws[-1]
      r[(m1, m2)].append((rs[m1], rs[m2]))
    
    # the solution is unique by the matches played
    for (k, v) in r.items():
      if len(v) == 1:
        printf("solution = {k[0]}:{v[0][0]}, {k[1]}:{v[0][1]}")
    

    Solution: The matches played on the final Saturday were Borough vs. United, which was a win for United, and City vs. Rangers, which was a draw.

    There is only one possible sequence of matches that leads to a unique solution:

    Week 1: A vs. R, A wins; B vs. C, match drawn. Points: A=3, B=1, C=1, R=0, U=0.
    Week 2: A vs. B, B wins; C vs. U, match drawn. Points: B=4, A=3, C=2, U=1, R=0.
    Week 3: A vs. C, C wins; R vs. U, R wins. Points: C=5, B=4, A=3, R=3, U=1.
    Week 4: A vs. U, U wins; B vs. R, R wins. Points: R=6, C=5, B=4, U=4, A=3.
    Week 5: B vs. U, U wins; C vs. R, match drawn. Points: R=7, U=7, C=6, B=4, A=3.

    • Jim Olson 4 May 2015 at 12:11 am

      There is a unique solution but in the sequence week four matches can be interchanged- A v R, R wins and B v U, U wins.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: