Enigmatic Code

Programming Enigma Puzzles

Enigma 1693: Inseparable

From New Scientist #2860, 14th April 2012 [link]

Albion, Borough, City, Rangers and United have staged a tournament in which each team played each of the others once. No two matches had the same score, and no team scored more than three goals in any match. Each played two home and two away fixtures.

Albion drew against Borough; both won their other three matches. Albion scored the same number of goals at home as Borough, and conceded the same number of goals at home as Borough. Albion also scored the same number of goals away as Borough scored away, and conceded the same number of goals away as Borough.

If I told you how many goals Albion and Borough each scored at home you could deduce with certainty the score in the fixture between Albion and Borough.

Tell me what the score was in that match.

[enigma1693]

Advertisements

4 responses to “Enigma 1693: Inseparable

  1. Jim Randell 11 April 2012 at 9:33 pm

    The following Python code runs in 40ms.

    from itertools import combinations
    from collections import defaultdict
    from enigma import printf
    
    # home goals scored by A and B are equal
    # away goals scored by A and B are equal
    # so the total number of goals scored by A and B are equal
    # likewise for goals conceded
    
    # A v B is drawn, so consider the remaining matches
    wins = set(((1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)))
    
    r = defaultdict(set)
    for A in combinations(wins, 3):
      # total goals for and against A (in the remaining matches)
      fT = sum(x[0] for x in A)
      aT = sum(x[1] for x in A)
      # B has the other wins (as no scoreline is repeated)
      B = wins.difference(A)
      if fT != sum(x[0] for x in B): continue
      if aT != sum(x[1] for x in B): continue
    
      # whatever type A v B was for A (home or away),
      # we need to split A's remaining games into 1 game (same type) + 2 games (other type)
      for Ax in A:
        # compute goals for and against (in the "other type" games)
        fA = sum(x[0] for x in A if x != Ax)
        aA = sum(x[1] for x in A if x != Ax)
    
        # and there must be one game in B's remaining matches that is "other type"
        # and that has the same for/against scores less the score of the A v B game
        for Bx in B:
          d = fA - Bx[0]
          if not(0 <= d < 4): continue
          if not(d == aA - Bx[1]): continue
    
          # compute B's goals for and against (in the "same type" game)
          fB = sum(x[0] for x in B if x != Bx)
          aB = sum(x[1] for x in B if x != Bx)
    
          # and these should match A's scores (in the "same type" game)
          if not(d == fB - Ax[0] == aB - Ax[1]): continue
    
          # we don't know whether same/different type is home or away, so consider both
          r[fA].add(d)
          r[fB].add(d)
    
    # and look for a key that identifies a unique value
    for k, v in r.items():
      if len(v) > 1: continue
      printf("A v B: {d}-{d} [A,B home goals scored: {k}]", d=v.pop())
    

    Solution: The score in the Albion vs. Borough match was 2 – 2.

    • Jim Randell 15 April 2012 at 5:22 pm

      As the puzzle is completely symmetrical in terms of A and B you can half the number of cases considered, by assigning a specific score to A, and then considering the remaining two games – although this makes no practical difference to the run time of the program (which is dominated by Python startup time anyway). However using the cProfile module you can see that it reduces the number of function calls from 457 (in 1ms) to 249 (also in 1ms).

  2. Brian Gladman 12 April 2012 at 7:11 am

    Here is my solution:

    from itertools import permutations, product
    from collections import defaultdict
    
    wins = ((1,0), (2,0), (2,1), (3,0), (3,1), (3,2))
    di = defaultdict(set)
    # the score for the Albion v Borough draw
    for draw in range(4):
      # the three wins for the team with a home draw (assume Albion)
      for awins in product(wins, repeat=3):
        # scores must be different
        if len(set(awins)) == 3:
          # the home/away goals for/against Albion
          aha = (draw + awins[0][0], draw + awins[0][1], 
                 awins[1][0] + awins[2][0], awins[1][1] + awins[2][1])
          # Borough's three winning scores must be different to Albion's
          for bwins in product(set(wins) - set(awins), repeat=3):
            # and be different themselves
            if len(set(bwins)) == 3:
              # the home/away goals for/against Borough
              bha = (bwins[1][0] + bwins[2][0], bwins[1][1] + bwins[2][1], 
                     draw + bwins[0][0], draw + bwins[0][1])
              # the home/away and for/against goals for Albion and Borough match
              if all(aha[i] == bha[i] for i in range(4)):
                # store matches with respect to Albion and Borough home goals 
                di[(draw + awins[0][0], bwins[1][0] + bwins[2][0])] |= set((draw,))
    
    for k in di:
      # look for a unique result
      if len(di[k]) == 1:
        print('Albion and Borough draw {0:d}:{0:d}'.format(min(di[k])))
    
  3. Brian Gladman 12 April 2012 at 2:49 pm

    And a slightly more intelligent one:

    
    from itertools import permutations
    from collections import defaultdict
    
    wins = ((1,0), (2,0), (2,1), (3,0), (3,1), (3,2))
    di = defaultdict(set)
    # the score for the Albion v Borough draw
    for draw in range(4):
      for p in permutations(wins):
        # the home/away goals for/against Albion
        aha = (draw + p[0][0], draw + p[0][1], 
               p[1][0] + p[2][0], p[1][1] + p[2][1])
        # the home/away goals for/against Borough
        bha = (p[4][0] + p[5][0], p[4][1] + p[5][1],
               draw + p[3][0], draw + p[3][1])
        # the home/away and for/against goals for Albion and Borough match
        if all(aha[i] == bha[i] for i in range(4)):
          # store matches with respect to Albion and Borough home goals 
          di[(draw + p[0][0], p[4][0] + p[5][0])] |= set((draw,))
    
    for k in di:
      # look for a unique result
      if len(di[k]) == 1:
        print('Albion and Borough draw {0:d}:{0:d}'.format(min(di[k])))
    

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: