Enigmatic Code

Programming Enigma Puzzles

Enigma 319: Mix and match

From New Scientist #1467, 1st August 1985 [link]

On the next five Saturdays, Albion, Borough, City, Rangers and United will be competing against each other in a league. There will be two matches each Saturday, each of the five teams having one Saturday without a match. At the end, each team will have played each of the others once, and will have played two home matches and two away matches alternating.

Next Saturday, the competition starts with Albion at home to Borough, and City at home to Rangers. A fortnight later, Borough will be playing at home.

What will be the two matches on the final Saturday (the home team to be named first in each match)?

[enigma319]

Advertisements

One response to “Enigma 319: Mix and match

  1. Jim Randell 13 November 2015 at 8:10 am

    I think this one is easier to do with pencil and paper.

    Nevertheless here is a Python 3 program that runs in 53ms.

    from itertools import combinations, permutations
    from enigma import join, printf
    
    # the teams are represented by letters
    teams = set('ABCRU')
    
    # weeks are represented by a dict, w:
    #  w['H1'] = home team for match 1
    #  w['A1'] = away team for match 1
    #  w['H2'] = home team for match 2
    #  w['A2'] = away team for match 2
    #  w['X'] = non playing team
    
    # return type of previous fixture
    # 'H' for home, 'A' for away, '' for none
    def previous(t, ws):
      for w in reversed(ws):
        p = w[t][0]
        if p != 'X': return p[0]
      return ''
    
    # generate possible weeks
    # ws - weeks (list of dict)
    # ms - matches played (set of str)
    def generate(ws, ms):
      # are we done?
      if len(ws) == 5:
        yield ws
      else:
        # choose the team not playing
        xs = set(t for t in teams if any(w[t][0] == 'X' for w in ws))
        for x in teams.difference(xs):
          ts = teams.difference([x])
          # choose two of the remaining teams to play at home
          for (h1, h2) in combinations(ts, 2):
            # home/away matches alternate
            if previous(h1, ws) == 'H' or previous(h2, ws) == 'H': continue
            # and two corresponding away teams
            for (a1, a2) in permutations(ts.difference((h1, h2)), 2):
              # home/away matches alternate
              if previous(a1, ws) == 'A' or previous(a2, ws) == 'A': continue
              # teams play each other once
              (m1, m2) = (join(sorted((a, b))) for (a, b) in ((h1, a1), (h2, a2)))
              if m1 in ms or m2 in ms: continue
              # generate the remaining weeks
              w = { h1: 'H1', h2: 'H2', a1: 'A1', a2: 'A2', x: 'X' }
              yield from generate(ws + [w], ms.union((m1, m2)))
    
    # week 1: A v B and C v R
    w1 = { 'A': 'H1', 'B': 'A1', 'C': 'H2', 'R': 'A2', 'U': 'X' }
    ms = set(['AB', 'CR'])
    
    # generate possible schedules for the 5 weeks
    for ws in generate([w1], ms):
    
      # B plays at home in week 3
      if ws[2]['B'][0] != 'H': continue
    
      # output the matches by week
      for (i, w) in enumerate(ws, start=1):
        d = dict((v, k) for (k, v) in w.items())
        printf("week {i}: {h1} vs {a1}, {h2} vs {a2}", h1=d['H1'], a1=d['A1'], h2=d['H2'], a2=d['A2'])
      printf()
    

    Solution: The matches on the final Saturday are: Borough vs. City and Rangers vs. United. (The home teams listed first).

    The full schedule is:

    Week 1: A vs. B, C vs. R
    Week 2: R vs. A, U vs. C
    Week 3: A vs. U, B vs. R
    Week 4: C vs. A, U vs. B
    Week 5: B vs. C, R vs. U

    The home team is given first in each match.

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: