Enigmatic Code

Programming Enigma Puzzles

Enigma 1116: United win at last

From New Scientist #2272, 6th January 2001 [link]

Albion, Borough, City, Rangers and United played a tournament in which each team played each of the other teams once. Two matches took place in each of five weeks, each team having one week without a match.

One point was awarded for winning in the first week, 2 points for winning in the second week, 3 points for winning in the third week, 4 points for winning in the fourth week and 5 points for winning in the fifth week. For a drawn match each team gained half the points it would have gained for winning it. At any stage, teams that had gained the same number of points were regarded as tying.

After the first week A led, with B tying for second place. After the second week B led, with C tying for second place. After the third week C led, with R tying for second place. After the fourth week R led, with U tying for second place. After the fifth week U had won the tournament with more points than any of the other teams.

(1) Which team or teams finished in second place after the fifth week?

(2) Give the results of Albion’s matches, listing them in the order in which they were played and naming the opponents in each match.

This completes the archive of Enigma puzzles from 2001. There are now 1065 Enigma puzzles on the site, the archive is complete from the beginning of Enigma in February 1979 to January 1987, and from January 2001 to the final Enigma puzzle in December 2013. Altogether there are currently 59.5% of all Enigmas published available on the site, which leaves 726 Enigmas between 1987 and 2000 left to publish.

[enigma1116]

Advertisements

One response to “Enigma 1116: United win at last

  1. Jim Randell 8 May 2017 at 7:08 am

    This Python 3 program attacks the problem recursively. Internally it deals in half-points, so that the totals remain integers. It runs in 76ms.

    from itertools import product
    from enigma import partitions, diff, update, join, compare, printf
    
    # labels for the 5 teams
    teams = 'ABCRU'
    
    # possible match outcomes (multiples of points for each side)
    matches = {
      'w': (2, 0), # win
      'd': (1, 1), # draw
      'l': (0, 2), # lose
    }
    
    # update dictionary <d> with (<match>, <result>) pairs in <ps>
    # allocating multiples of <k> points
    def points(d, k, ps):
      # add in the points for the matches
      d = d.copy()
      for (m, r) in ps:
        d[m[0]] += r[0] * k
        d[m[1]] += r[1] * k
      return d
    
    # return the positions in the table
    # (element 0 = first, element 1 = second, etc.)
    def table(d):
      t = list()
      for x in sorted(set(d.values()), reverse=1):
        t.append(list(k for (k, v) in d.items() if v == x))
      return t
    
    # accumulate possible match outcomes and points
    # k = week number
    # ps = point multiples for each week
    # ws = teams that can miss a week
    # ms = matches played so far [map of (<team 1>, <team 2>) -> (<week number>, <match outcome>)]
    # cs = checks for each work (functions)
    # d = dictionary mapping teams to points
    def solve(k, ps, ws, ms, cs, d):
      if not ps:
        yield (ms, d)
      else:
        # choose the team that doesn't play this week
        for w in ws:
    
          # pair up the remaining teams to give the matches
          for (m1, m2) in partitions(diff(teams, w), 2):
            if m1 in ms or m2 in ms: continue
    
            # choose outcomes for the two matches
            for (r1, r2) in product(matches.keys(), repeat=2):
    
              # accumulate the points and calculate the table
              dx = points(d, ps[0], [(m1, matches[r1]), (m2, matches[r2])])
    
              # apply checks
              if not(cs[0](dx)): continue
    
              # solve for the remainder
              yield from solve(k + 1, ps[1:], ws.difference([w]), update(ms, [(m1, (k, r1)), (m2, (k, r2))]), cs[1:], dx)
    
    
    # check points in <d> for "<X> is in the lead, <Y> is tied for second"
    def check(d, X, Y=None):
      t = table(d)
      # X is in the lead
      if not(len(t[0]) == 1 and X in t[0]): return False
      # Y is tied for second
      if Y is not None:
        if not(len(t[1]) > 1 and Y in t[1]): return False
      return True
    
    # the checks for the 5 weeks
    checks = [
      lambda d: check(d, 'A', 'B'),
      lambda d: check(d, 'B', 'C'),
      lambda d: check(d, 'C', 'R'),
      lambda d: check(d, 'R', 'U'),
      lambda d: check(d, 'U'),
    ]
    
    # solve the puzzle
    for (ms, d) in solve(1, [1, 2, 3, 4, 5], set(teams), dict(), checks, dict((t, 0) for t in teams)):
      t = table(d)
      printf("[points = {d}, table = {t}]")
      printf("[matches = {ms}]")
    
      # answer the specific questions
      printf("\nANSWERS:")
    
      # (1) which team(s) finished the tournament in second place
      printf("(1) 2nd place = {t1}", t1=join(t[1], sep=','))
    
      # (2) output A's matches
      printf("(2) matches for A:")
      for (m, (k, r)) in sorted(((k, v) for (k, v) in ms.items() if 'A' in k), key=lambda m: m[1][0]):
        printf("  week {k}: {m[0]} v {m[1]} = {r}")
    
      printf()
    

    Solution: (1) Albion finished in second place; (2) Albion’s matches were: week 1 = beat City, week 2 = lost to Borough; week 3 = no match; week 4 = drew with United; week 5 = beat Rangers.

    The complete results are:

    Week 1: A beat C, B drew with U. Points: (A=1), (B=½, U=½).
    Week 2: A lost to B, C drew with R. Points: (B=2½), (A=1, C=1, R=1), (U=½).
    Week 3: B lost to C, R drew with U. Points: (C=4), (B=2½, R=2½), (U=2), (A=1).
    Week 4: A drew with U, B lost to R. Points: (R=6½), (C=4, U=4), (A=3), (B=2½).
    Week 5: A beat R, C lost to U. Points: (U=9), (A=8), (R=6½), (C=4), (B=2½).

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: