Enigmatic Code

Programming Enigma Puzzles

Enigma 1559: Points for a win

From New Scientist #2722, 22nd August 2009 [link]

In a tournament in which each team played each of the other teams four times, with 2 points awarded for each win and 1 point to each team for a draw, the teams finished in the order Albion, Borough, City, Rangers, United, each team having a different number of points.

If 3 points had been awarded for each win and 1 point to each team for a draw, once again each team would have had a different number of points; but City would have won the tournament and none of the teams would have finished in the same position as with 2 points for a win.

11 matches were drawn, including the first match of the tournament. If I told you which teams played in that match you could deduce with certainty how many matches each team won, drew and lost. How many matches did each team win?

Enigma 1380 is also called “Points for a win”.

[enigma1559]

Advertisements

One response to “Enigma 1559: Points for a win

  1. Jim Randell 5 March 2012 at 1:58 pm

    The following Python program runs in 1.8s.

    Originally I wrote code with more nested loops to find the answer. It runs faster, but is even longer and messier than this. I’ve tried to come up with a cleaner version (that also goes all the way to analysing the possibilities and finding the answer), and this is the best I’ve managed so far.

    # each team plays each of the other teams 4 times
    # so there must be 40 matches, and each team plays in 16 matches
    # 11 are drawn (so the sum of the d's must be 22)
    # so 29 matches are won (the sum of the w's must be 29)
    
    # with w=2, d=1 the points are pA > pB > pC > pR > pU.
    # with w=3, d=1 all points would have been different and C would have won.
    
    # all the points being different in the second case implies that no team had 0w.
    
    # 2.wA + dA > 2.wC + dC + 1 (because B is inbetween)
    # 3.wC + dC > 3.wA + dA
    # so adding together and removing (2.wA + 2.wC + dA + dC) we get:
    # wC > wA + 1
    
    from itertools import product
    from collections import defaultdict
    from enigma import is_distinct, printf
    
    # points
    def points(w, d):
      p = 2 * w + d # actual points
      h = 3 * w + d # hypothetical points
      return (p, h)
    
    # the matches are: (each happens 4 times)
    matches = ['AvB', 'AvC', 'AvR', 'AvU', 'BvC', 'BvR', 'BvU', 'CvR', 'CvU', 'RvU']
    
    # the scores for each combination are: (<w>, <d>, <l>)
    scores = [
      (4, 0, 0),
      (3, 0, 1), (3, 1, 0),
      (2, 0, 2), (2, 1, 1), (2, 2, 0),
      (1, 0, 3), (1, 1, 2), (1, 2, 1), (1, 3, 0),
      (0, 0, 4), (0, 1, 3), (0, 2, 2), (0, 3, 1), (0, 4, 0)
    ]
    
    # generate possible points for a team
    def generate(ws=0, ds=0, minw=1,):
      for w in range(minw, min(16, 29 - ws) + 1):
        for d in range(0, min(11, 16 - w, 23 - ds)):
          (p, h) = points(w, d)
          yield (w, d, p, h)
    
    def find_points():
      # points for A
      for (wA, dA, pA, hA) in generate():
    
        # points for C
        for (wC, dC, pC, hC) in generate(wA, dA, minw=wA + 1):
          if not(pA > pC): continue
          if not(hC > hA): continue
    
          # points for B
          for (wB, dB, pB, hB) in generate(wA + wC, dA + dC):
            if not(pA > pB > pC): continue
            if not(hC > hB): continue
            if not is_distinct(hB, hA, pB): continue
    
            # points for R
            for (wR, dR, pR, hR) in generate(wA + wB + wC, dA + dB + dC):
              if not(pC > pR): continue
              if not(hC > hR): continue
              if not is_distinct(hR, hA, hB, pR): continue
    
              # points for U
              (wU, dU) = (29 - (wA + wB + wC + wR), 22 - (dA + dB + dC + dR))
              if not(wU > 0): continue
              (pU, hU) = points(wU, dU)
              if not(pR > pU): continue
              if not(hC > hU): continue
              if not is_distinct(hU, hA, hB, hR, pR): continue
    
              # check no team would be in the same place in hypothetical scoring
              h = sorted((hA, hB, hC, hR, hU), reverse=True)
              if h[1] == hB or h[3] == hR or h[4] == hU: continue
    
              printf("A={wA}w{dA}d {pA}/{hA} B={wB}w{dB}d {pB}/{hB} C={wC}w{dC}d {pC}/{hC} R={wR}w{dR}d {pR}/{hR} U={wU}w{dU}d {pU}/{hU}")
    
              yield (wA, dA, wB, dB, wC, dC, wR, dR, wU, dU)
    
    
    # derive a score against the remaining team
    def score(w, d):
      if not(0 <= w <= 4): return
      if not(0 <= d <= 4): return
      l = 4 - (w + d)
      if not(0 <= l <= 4): return
      return (w, d, l)
    
    # find possible matches to give the required scores
    # and return possibilities for draws
    def find_matches(wA, dA, wB, dB, wC, dC, wR, dR, wU, dU):
      d = defaultdict(int)
      for (AB, AC, AR) in product(scores, repeat=3):
        AU = score(wA - (AB[0] + AC[0] + AR[0]), dA - (AB[1] + AC[1] + AR[1]))
        if not AU: continue
    
        for (BC, BR) in product(scores, repeat=2):
          BU = score(wB - (AB[2] + BC[0] + BR[0]), dB - (AB[1] + BC[1] + BR[1]))
          if not BU: continue
    
          for CR in scores:
            CU = score(wC - (AC[2] + BC[2] + CR[0]), dC - (AC[1] + BC[1] + CR[1]))
            if not CU: continue
            RU = score(wR - (AR[2] + BR[2] + CR[2]), dR - (AR[1] + BR[1] + CR[1]))
            if not RU: continue
    
            # check the scores for U
            if not(wU == AU[2] + BU[2] + CU[2] + RU[2]): continue
            if not(dU == AU[1] + BU[1] + CU[1] + RU[1]): continue
    
            # check draws and wins / losses achieve the right totals
            ms = (AB, AC, AR, AU, BC, BR, BU, CR, CU, RU)
            if sum(m[1] for m in ms) != 11: continue
            if sum(m[0] + m[2] for m in ms) != 29: continue
            # accumulate possible draws
            for (i, m) in enumerate(ms):
              if m[1]: d[matches[i]] += 1
      return d
    
    # accumulate draws by team wins
    draws = defaultdict(set)
    for ps in find_points():
      d = find_matches(*ps)
      if not d: continue
      print("is possible...")
      for k in d.keys():
        draws[k].add(ps[0:10:2]) # weed out the wins
    
    # looks for draws that indicate a unique outcome
    for (k, v) in draws.items():
      if len(v) > 1: continue
      printf("SOLUTION: draw = {k} => wins = {w}", w=list(v)[0])
    

    Solution: Albion won 6 matches. Borough won 6 matches. City won 9 matches. Rangers won 3 matches. United won 5 matches.

    In fact it turns out that you only need to know that United played in one of the drawn matches.

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: