Enigmatic Code

Programming Enigma Puzzles

Enigma 1220: Matchless days

From New Scientist #2376, 4th January 2003 [link]

Albion, Borough, City, Rangers and United are due to play another tournament in which each team will play each of the other teams once. One match will be played on each of 10 consecutive days.

Though the schedule of matches ensures that no team will ever play on two consecutive days United has complained that it has fewer matchless days between its first match and it last match than any of the other teams. Albion has the greatest number of matchless days between its first match and its last match, and Borough the second greatest number of matchless days between its first match and its last match. Rangers will play United one day before Albion play City.

On which of the days 1 to 10 will Borough play? And who will be Borough’s opponents on each of those days?

This puzzle completes the archive for 2003. There is a now full archive of the final 11 years of Enigma puzzles, from the start of 2003 to the end of 2013, as well as an archive from the start of Enigma in February 1979 to January 1985. In total there are currently 858 Enigma puzzles on the site.

[enigma1220]

Advertisements

One response to “Enigma 1220: Matchless days

  1. Jim Randell 6 July 2015 at 7:16 am

    This Python 3 program generates possible sequences of matches where no team plays in consecutive matches. It then applies the additional constraints. It runs in 67ms.

    from itertools import combinations
    from enigma import diff, printf
    
    # team labels
    teams = tuple('ABCRU')
    
    # possible matches
    matches = tuple(x + y for (x, y) in combinations(teams, 2))
    
    # generate matches, so that no team plays in consecutive matches
    def generate(ms, ss):
      if not ms:
        yield ss
      else:
        # choose the next match
        for m in ms:
          # no teams play consecutive weeks
          if ss and (m[0] in ss[-1] or m[1] in ss[-1]): continue
          yield from generate(diff(ms, [m]), ss + [m])
    
    for ss in generate(matches, []):
      # map matches to days
      day = dict((m, i) for (i, m) in enumerate(ss, start=1))
    
      # AC is the day after RU
      if day['RU'] + 1 != day['AC']: continue
    
      # record the difference between the min and max days for each team
      d = list()
      for t in teams:
        ds = sorted(v for (k, v) in day.items() if t in k)
        d.append((t, ds[-1] - ds[0]))
      d.sort(key=lambda v: v[1])
    
      # U has the smallest difference
      if not(d[0][0] == 'U' and d[0][1] < d[1][1]): continue
    
      # A has the largest difference
      if not(d[-1][0] == 'A' and d[-1][1] > d[-2][1]): continue
    
      # B has the second largest difference
      if not(d[-2][0] == 'B' and d[-2][1] > d[-3][1]): continue
    
      printf("({ss})", ss=', '.join(ss))
    

    Solution: Borough plays on Day 2 (Borough vs. City), Day 5 (Borough vs. United), Day 8 (Borough vs. Rangers) and Day 10 (Albion vs. Borough).

    The full schedule is:

    Day 1: Albion vs. Rangers
    Day 2: Borough vs. City
    Day 3: Rangers vs. United
    Day 4: Albion vs. City
    Day 5: Borough vs. United
    Day 6: City vs. Rangers
    Day 7: Albion vs. United
    Day 8: Borough vs. Rangers
    Day 9: City vs. United
    Day 10: Albion vs. Borough

    Between its first and last match United has 3 rest days (4, 6, 8).
    City has 4 rest days (3, 5, 7, 8).
    Rangers has 4 rest days (2, 4, 5, 7).
    Borough has 5 rest days (3, 4, 6, 7, 9).
    Albion has 6 rest days (2, 3, 5, 6, 8, 9).

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: