Enigmatic Code

Programming Enigma Puzzles

Enigma 1295: United could win

From New Scientist #2453, 26th June 2004 [link]

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

Three points are awarded for a win and one point for a draw. The third Saturday’s matches have just been played. The current points table shows the teams standing in the order Albion, Borough, City, Rangers, United; some of these teams are tied on points and separated only by goal difference, but United have fewer points than any other team. But the United players know that if they win their last two matches their team is sure to end up with more points than any other team. Albion beat City. What are the results of the other five matches that have been played?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.



One response to “Enigma 1295: United could win

  1. Jim Randell 8 September 2014 at 2:20 pm

    I was a bit unsure of the best way to tackle this football problem (geddit?), it’s not as straightforward as these football problems usually are.

    This Python program uses the Football() class from enigma.py. It runs in 579ms.

    from itertools import combinations
    from enigma import Football, diff, filter2, printf
    # matches
    matches = ('AB', 'AC', 'AR', 'AU', 'BC', 'BR', 'BU', 'CR', 'CU', 'RU')
    # scoring regime
    football = Football(points={ 'w': 3, 'd': 1 })
    # compute a table for team <t> for matches <ms> with outcomes from <d>
    def table(t, ms, d):
      return football.table(*(zip(*((d.get(m, 'x'), m.index(t)) for m in ms))))
    # generate matches for a week given a non-playing team
    # and a collection of previous matches
    def generate(t, x=()):
      for m1 in matches:
        if t in m1: continue
        m2 = ''.join(diff('ABCRU', m1 + t))
        if m2 < m1: continue
        if m1 in x or m2 in x: continue
        yield (m1, m2)
    # generate possible matches for each week
    def weeks():
      # in the first 3 weeks U has a non playing week, let that be week 1
      for w1 in generate('U'):
        # choose teams for week 2 and week 3
        for (t2, t3) in combinations('ABCR', 2):
          for w2 in generate(t2, w1):
            for w3 in generate(t3, w1 + w2):
              # A beats C in the first 3 weeks
              if not 'AC' in w1 + w2 + w3: continue
              # consider the future non-playing teams
              (t4, t5) = diff('ABCR', t2 + t3)
              for w4 in generate(t4, w1 + w2 + w3):
                for w5 in generate(t5, w1 + w2 + w3 + w4):
                  yield (w1, w2, w3, w4, w5)
    # consider possible matches for the five weeks
    for (w1, w2, w3, w4, w5) in weeks():
      # generate possible outcomes for the first 3 weeks
      for ms in football.games('wdl', repeat=6):
        # and assign them to the games
        d = dict(zip(w1 + w2 + w3, ms))
        # A beat C
        if d['AC'] != 'w': continue
        # compute the tables
        A = table('A', ['AB', 'AC', 'AR', 'AU'], d)
        B = table('B', ['AB', 'BC', 'BR', 'BU'], d)
        C = table('C', ['AC', 'BC', 'CR', 'CU'], d)
        R = table('R', ['AR', 'BR', 'CR', 'RU'], d)
        U = table('U', ['AU', 'BU', 'CU', 'RU'], d)
        # check the points are ordered
        if not(A.points >= B.points >= C.points >= R.points > U.points): continue
        # and some teams are tied for points
        if A.points > B.points > C.points > R.points: continue
        # the remaining matches (for U and other teams)
        (rU, rX) = filter2(lambda m: 'U' in m, w4 + w5)
        # and consider the outcomes of the non-U matches
        for ms in football.games('wdl', repeat=2):
          d2 = d.copy()
          d2.update(zip(rX, ms))
          # U win their remaining matches (so the other team lose)
          d2.update(zip(rU, 'll'))
          # compute the final tables
          A2 = table('A', ['AB', 'AC', 'AR', 'AU'], d2)
          B2 = table('B', ['AB', 'BC', 'BR', 'BU'], d2)
          C2 = table('C', ['AC', 'BC', 'CR', 'CU'], d2)
          R2 = table('R', ['AR', 'BR', 'CR', 'RU'], d2)
          U2 = table('U', ['AU', 'BU', 'CU', 'RU'], d2)
          # U can win whatever the remaining outcomes
          if not(U2.points > max(A2.points, B2.points, C2.points, R2.points)):
          # output a solution
          printf("w1={w1} w2={w2} w3={w3} w4={w4} w5={w5}")

    Solution: The result of the other five matches are:

    Albion vs. Borough – win for Borough;
    Albion vs. United – match drawn;
    Borough vs. Rangers – win for Rangers;
    Borough vs. United – match drawn;
    City vs. Rangers – win for City.

    The matches remaining to be played are: Albion vs. Rangers, Borough vs. City, City vs. United and Rangers vs. United. (So one week will be: B vs. C, R vs. U, and the other week will be A vs. R, C vs. U).

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

%d bloggers like this: