Enigmatic Code

Programming Enigma Puzzles

Enigma 1345: Score? Date?

From New Scientist #2504, 18th June 2005

The football teams Ark, Bat, Cat and Dog played each other once in the period January to March. Each match started at 3:00pm and no team played two games on consecutive days. In the evening of each match day the local paper printed a chart which gave the scores of all matches played so far and the dates of all matches still to be played. Below is one of the charts produced during the season.

Enigma 1345

As an example of the meaning, the top left entry is A4-B1 or 4 January. The paper used different coloured print to distinguish between scores and dates but I forgot to record the colours. However I can tell you that at the end of the season, with 3 points for a win and 1 for a draw, one team’s total points was 5 and the sum of the four totals was odd.

For which matches were the entries actually scores?

[enigma1345]

Advertisements

One response to “Enigma 1345: Score? Date?

  1. Jim Randell 21 February 2014 at 8:41 am

    I think this one is probably easier to solve analytically than by programming, but here’s a Python program that solves it in 52ms.

    from itertools import product, permutations
    from enigma import powerset, irange, Football, first, printf
    
    # valid dates
    dates = set(product(irange(1, 31), (1, 2, 3))).difference(((30, 2), (31, 2)))
    
    # games and values
    matches = ("AvB",  "AvC",  "AvD",  "BvC",  "BvD",  "CvD")
    values  = ((4, 1), (2, 3), (1, 3), (4, 1), (4, 2), (3, 4))
    
    # which values belong to which team
    teams = (
      (0, 1, 2), # A
      (0, 3, 4), # B
      (1, 3, 5), # C
      (2, 4, 5), # D
    )
    
    # set up the scoring rules
    football = Football(points={ 'w': 3, 'd': 1 })
    
    # check for duplicate or consecutive dates
    def check(s):
      return (
        len(set(s)) == len(s) and 
        all((x + 1, y) not in s for (x, y) in s)
      )
    
    # for comparing dates (month then day)
    def compare(x):
      return x[::-1]
    
    # assign dates to all matches
    # ds - subset of matches yet to be played
    def assign(ds):
      # which matches have been played
      ms = list(i for (i, _) in enumerate(values) if i not in ds)
      # find the earliest unplayed match
      d0 = min(compare(values[i]) for i in ds)
      # and the dates before this
      dp = set(x for x in dates if compare(x) < d0)
      # assign dates to each played match
      for mds in product(dp, repeat=len(ms)):
        # make a list of dates for each match
        vs = list(values)
        for (i, v) in zip(ms, mds):
          vs[i] = v
        # make the dates for each team
        (dA, dB, dC, dD) = list(list(vs[i] for i in t) for t in teams)
        # check the dates are allowable
        if all(check(s) for s in (dA, dB, dC, dD)):
          yield vs
    
    # consider possible sets of dates
    for ds in powerset(i for (i, v) in enumerate(values) if v in dates):
      # dates for each team
      (dA, dB, dC, dD) = list(list(values[i] for i in t if i in ds) for t in teams)
      # check the dates are allowable
      if not all(check(s) for s in (dA, dB, dC, dD)): continue
    
      # possibile outcomes of the non-date games
      games = list(('wld' if i in ds else p) for (i, p) in enumerate('wllwwl'))
      for (AB, AC, AD, BC, BD, CD) in product(*games):
        # calculate the tables
        A = football.table([AB, AC, AD], [0, 0, 0])
        B = football.table([AB, BC, BD], [1, 0, 0])
        C = football.table([AC, BC, CD], [1, 1, 0])
        D = football.table([AD, BD, CD], [1, 1, 1])
        # one team has 5 points and the total of the points is odd
        points = (A.points, B.points, C.points, D.points)
        if not(points.count(5) == 1 and sum(points) % 2 == 1): continue
    
        # check that played matches can be scheduled before the earliest date
        if ds:
          # find a valid assignment of dates for all matches
          f = first(assign(ds))
          if not f: continue
          printf("possible date assignment = {f[0]}")
    
        printf("AvB: {AB}, AvC: {AC}, AvD: {AD}, BvC: {BC}, BvD: {BD}, CvD: {CD}")
        printf("A: {A}")
        printf("B: {B}")
        printf("C: {C}")
        printf("D: {D}")
        printf("played = {s}", s=' '.join(matches[i] for (i, v) in enumerate(values) if i not in ds))
        printf('')
    

    Solution: The entries that are scores are A vs. D, B vs. C and C vs. D.

    We can deduce quite a lot more information from the unique solution. We know that the the table must have been published on the evening of the 3rd January (3/1), and that the A vs. B match was played on the 4th January (4/1), and that the match was drawn. A vs. C was played on 2nd March (2/3) and was also a draw. The A vs. D match was played on 1st January (1/1), and the score was 1-3 (a win for D). B vs. C was also played on 1st January (1/1) (and so there must be two venues, as we are told the matches all start at 3pm). B vs. D was played on the 4th February (4/2), and was a draw. Finally C vs. D was played on 3rd January (3/1), the result was 3-4 (another win for D).

    The final points table is: D = 7 points (wins against A and C, draw against B), B = 5 points (win against C, draws against A and D), A = 2 points (draws against B and C), C = 1 point (draw against A). Giving an odd total of 15 points.

    We have to schedule two matches on 1st January (1/1) to permit a solution, but this is not explicitly disallowed by the problem statement.

    The programming turned out to be a bit more convoluted than I was expecting. If you don’t try work out a valid schedule for the played matches you end up with a second possibility, which is that A vs. B, A vs. C and C vs. D are the entries that are scores. But in this situation B vs. C is scheduled to be played on 4th January (4/1), so the paper must be published on (or before) 3rd January (3/1). So the three played games (A vs. B, A vs. C, C vs. D) must all have happened on the 1st, 2nd or 3rd January, but there is no way to schedule them (there are two matches involving A, so they must have been played on 1/1 and 3/1, but B vs. C is scheduled for 4/1 so the A vs. C match cannot be played on 3/1 (to avoid C playing on two consecutive days), but neither can the A vs. B match (to avoid B playing on two consecutive days), hence there is no possible way the matches can have been scheduled).

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: