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]

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.

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