Enigmatic Code

Programming Enigma Puzzles

Enigma 1322: Geometric runs

From New Scientist #2481, 8th January 2005

In cross-country races with teams of six runners, the team scores are calculated by adding together the finishing positions of the first four runners in each team, the lowest-scoring team being the winner. Individuals never tie for any position.

The fifth and sixth runners to finish in each team do not contribute to the team score, but if they finish ahead of scoring runners in other teams they make the positions of those runners and their teams’ scores that much worse.

In a race involving seven teams of six runners, the scores of the first four teams formed a geometric progression, as did the scores of the last four teams.

What were the scores of the first and last teams?

This puzzle completes the archive of Enigmas from the beginning of 2005 up to the end of 2013 (and the end of Enigma), which is 459 puzzles. There are also 193 puzzles available from the start of Enigma (in 1979) to the beginning of 1983, which together with a random puzzle from 2000 currently makes up the 653 Enigma puzzles on the site.

[enigma1322]

Advertisements

12 responses to “Enigma 1322: Geometric runs

  1. Jim Randell 24 May 2014 at 9:17 am

    This Python program looks for possible scores that are in the required geometric progressions, and then, once it finds a possible sequence of scores it tries to find an actual assignment of positions to make up the sequences. This program runs in 2m14s.

    from enigma import irange, diff, chunk, uniq, cached, printf
    
    # there are 7 teams of 6 runners
    N = 7 * 6
    
    # possible scoring positions (the final 2 runners can never score)
    ns = tuple(irange(1, N - 2))
    
    # generate possible scores that are in geometric progressions
    def generate():
    
      # lowest possible team score
      lo = sum(ns[:4])
      # highest possible team score
      hi = sum(ns[-4:])
      # highest possible total score
      total = sum(ns) - sum(ns[i] + ns[i + 1] for i in irange(4, N - 6, step=6))
      printf("[lo={lo} hi={hi} total={total}]")
    
      # possible scores for the 1st placed team
      for s1 in irange(lo, min(hi, total // 7)):
        # possible scores for the 2nd placed team
        for s2 in irange(s1 + 1, min(hi, (total - s1) // 6)):
          # s1, s2, s3, s4 are in geometric progression
          (s3, r) = divmod(s2 * s2, s1)
          if r or s3 > hi: continue
          (s4, r) = divmod(s3 * s2, s1)
          if r or s4 > hi: continue
          t1 = s1 + s2 + s3 + s4
          if t1 + s4 * 3 > total: continue
    
          # possible scores for the 5th placed team
          for s5 in irange(s4 + 1, min(hi, (total - t1) // 3)):
            # s4, s5, s6, s7 are in geometric progression
            (s6, r) = divmod(s5 * s5, s4)
            if r or s6 > hi: continue
            (s7, r) = divmod(s6 * s5, s4)
            if r or s7 > hi: continue
            t2 = s5 + s6 + s7
            if t1 + t2 > total: continue
    
            yield (s1, s2, s3, s4, s5, s6, s7)
    
    
    # decompose n into m numbers from ns
    def decompose(n, m, ns):
      if m == 1:
        if n in ns:
          yield [n]
      else:
        for (i, x) in enumerate(ns):
          if x > n: break
          for ds in decompose(n - x, m - 1, ns[i + 1:]):
            yield [x] + ds
    
    # can we allocate the remaining positions to the teams? there may
    # be many ways to do this, but we only need to find one that works.
    # we order the teams by the position of their last scoring runner,
    # and then allocate the remaining runners in order
    def allocate_remaining(ns, ps):
      # add the final 2 runners back in
      ns = ns + (N - 1, N)
      r = [None] * len(ps)
      for (i, x) in zip(sorted((j for (j, _) in enumerate(ps)), key=lambda j: ps[j][-1]), chunk(ns, 2)):
        if not(x[0] > ps[i][-1]): return
        r[i] = x
      return r
    
    # ns - numbers to allocate
    # ss - team scores to achieve
    # ps - positions for teams allocated so far
    # ds - decompositions of team scores
    def allocate(ns, ss, ps=[], ds=None):
      if not ss:
        if allocate_remaining(ns, ps):
          yield ps
      else:
        if ds is None:
          # find decompositions for all the scores
          ds = dict()
          for s in uniq(ss):
            ds[s] = list(decompose(s, 4, ns))
        else:
          # reduce the current decompositions
          sns = set(ns)
          ds = dict((s, list(v for v in ds[s] if sns.issuperset(v))) for s in uniq(ss))
        # try the score with the fewest decompositions
        m = min(ds.keys(), key=lambda k: len(ds[k]))
        ss2 = list(ss)
        ss2.remove(m)
        for p in ds[m]:
          for x in allocate(diff(ns, p), ss2, ps + [p], ds):
            yield x
    
    for ss in generate():
      printf("[checking {ss} ...]")
      for ps in allocate(ns, ss):
        printf("positions = {ps}")
        break
    

    Solution: The team in 1st place scored 27. The team in last place scored 125.

    The scores (from 1st to 7th place) are: 27, 36, 48, 64, 80, 100, 125.

    The first four terms form a geometric progression with a common ratio of 4/3. The final four terms form a geometric progression with a common ratio of 5/4.

    There are many possible ways for the finishing positions to give the scores above. Here’s one of them:

    1st. 1, 2, 3, 21, (26, 27) = 27 points.
    2nd. 4, 5, 7, 20, (23, 24) = 36 points.
    3rd. 6, 8, 9, 25, (29, 30) = 48 points.
    4th. 13, 16, 17, 18, (19, 22) = 64 points.
    5th. 10, 11, 28, 31, (32, 33) = 80 points.
    6th. 14, 15, 35, 36, (37, 38) = 100 points.
    7th. 12, 34, 39, 40, (41, 42) = 125 points.

    There are only two possible sequences of scores that form the required geometric progressions. The other one is:

    16, 24, 36, 54, 72, 96, 128.

    But it is not possible to assign positions to achieve this sequence.

    If, however, we allow geometric progressions with a common ratio of 1 (i.e. where some of the teams have the same score), then we can find further solutions. For example, from the additional 99 candidate sequences, the following sequences of scores work:

    12, 24, 48, 96, 96, 96, 96.
    13, 26, 52, 104, 104, 104, 104.
    24, 36, 54, 81, 81, 81, 81.
    40, 40, 40, 40, 60, 90, 135.
    58, 58, 58, 58, 58, 58, 58.
    59, 59, 59, 59, 59, 59, 59.
    60, 60, 60, 60, 60, 60, 60.
    61, 61, 61, 61, 61, 61, 61.
    62, 62, 62, 62, 62, 62, 62.
    63, 63, 63, 63, 63, 63, 63.
    64, 64, 64, 64, 64, 64, 64.
    65, 65, 65, 65, 65, 65, 65.
    66, 66, 66, 66, 66, 66, 66.

    Since you don’t get a unique answer this way I think we can assume that geometric progression with a common ratio of 1 are not what the puzzle setter had in mind.

    I’ve not marked the puzzle as flawed, even though this situation could easily have been avoided in the phrasing of the question (as it was in Enigma 1418 by stating: “no two teams had the same score”).

    • Jim Randell 5 June 2014 at 5:20 pm

      Here’s a program that takes a different approach, and solves the problem in 265ms.

      It constructs the sequence of runners labelled by teams, which it does recursively by keeping track for each team of the remaining score needed and the number of scoring runners remaining. For each position the teams with remaining scores are considered, when the 3rd runner is positioned the position of the 4th runner (the final scoring runner) is determined and is assigned (if possible). The 5th and 6th runners are then placed on the list of non-scoring runners. After scoring runners have been considered for a position then if there are any valid non-scoring runners available one of those is placed in the position.

      It also uses a Python exception to pass the first solution found out of the main solver, as I found this was faster than using yield.

      The code to determine the possible sequences of scores is the same as my previous version.

      from enigma import irange, printf
      
      # generate possible scores that are in geometric progressions
      def generate():
      
        # possible scoring runners
        ns = tuple(irange(1, 40))
      
        # lowest possible team score
        lo = sum(ns[:4])
        # highest possible team score
        hi = sum(ns[-4:])
        # highest possible total score
        total = sum(ns) - sum(ns[i] + ns[i + 1] for i in irange(4, 36, step=6))
        printf("[lo={lo} hi={hi} total={total}]")
      
        # possible scores for the 1st placed team
        for s1 in irange(lo, min(hi, total // 7)):
          # possible scores for the 2nd placed team
          for s2 in irange(s1 + 1, min(hi, (total - s1) // 6)):
            # s1, s2, s3, s4 are in geometric progression
            (s3, r) = divmod(s2 * s2, s1)
            if r or s3 > hi: continue
            (s4, r) = divmod(s3 * s2, s1)
            if r or s4 > hi: continue
            t1 = s1 + s2 + s3 + s4
            if t1 + s4 * 3 > total: continue
      
            # possible scores for the 5th placed team
            for s5 in irange(s4 + 1, min(hi, (total - t1) // 3)):
              # s4, s5, s6, s7 are in geometric progression
              (s6, r) = divmod(s5 * s5, s4)
              if r or s6 > hi: continue
              (s7, r) = divmod(s6 * s5, s4)
              if r or s7 > hi: continue
              t2 = s5 + s6 + s7
              if t1 + t2 > total: continue
      
              yield (s1, s2, s3, s4, s5, s6, s7)
      
      
      # an exception to return the first solution found
      class Solved(Exception):
        def __init__(self, message, positions):
          Exception.__init__(self, message)
          self.positions = positions
      
      # sum of the next n available positions from p
      def sum_next(ps, p, n):
        sn = [0]
        s = 0
        try:
          while True:
            while ps[p] > 0:
              p += 1
            s += p
            sn.append(s)
            if len(sn) > n: break
            p += 1
        except IndexError:
          pass
      
        return sn
      
      # ps - positions
      # p - next position to allocate
      # ss - (score, runners) for each team
      # ns - non-scoring runners to be allocated
      def _solve(ps, p, ss, ns):
        # are we done?
        if p == 43:
          raise Solved("solution found", ps)
        # is this position already allocated?
        elif ps[p] > 0:
          _solve(ps, p + 1, ss, ns)
        else:
          # try to allocate scoring runners
          if ss:
            # sum of the next few positions
            sn = sum_next(ps, p, 4)
            # go through the teams starting with the ones that need lower positions
            for t in sorted(ss.keys(), key=lambda k: (ss[k][0] // ss[k][1], -ss[k][1])): 
              (s, n) = ss[t]
              # is this score still possible?
              if sn[n] > s: return
              # the remaining score is...
              r = s - p
              ps2 = list(ps)
              ss2 = ss.copy()
              # allocate the 3rd and 4th runners at the same time
              if n == 2:
                # can the 4th runner be allocated?
                if not(p < r < 41 and ps[r] == 0): continue
                # assign the 3rd and 4th runners
                ps2[p] = ps2[r] = t
                # all scoring runners assigned
                del ss2[t]
                # 5th and 6th runners can be allocated
                # record (team, number of remaining runners, highest scoring position)
                ns2 = ns + [(t, 2, r)]
                _solve(ps2, p + 1, ss2, ns2)
              else:
                # assign the runner (1st or 2nd)
                ps2[p] = t
                # reduce the score and remaining runners
                ss2[t] = (r, n - 1)
                _solve(ps2, p + 1, ss2, ns)
          # allocate a non-scoring runner (if any are available)
          for (i, (t, n, r)) in enumerate(ns):
            if p > r:
              ps2 = list(ps)
              ps2[p] = t
              ns2 = list(ns)
              if n == 1:
                del ns2[i]
              else:
                ns2[i] = (t, n - 1, r)
              _solve(ps2, p + 1, ss, ns2)
              break
      
      # solve for the specified scores, returning the first solution found
      def solve(scores):
        try:
          _solve([0] * 43, 1, dict((i, (s, 4)) for (i, s) in zip(irange(1, 7), scores)), [])
        except Solved as e:
          return e.positions
        else:
          return None
      
      # check all possible sequences of scores
      for scores in generate():
        printf("[checking {scores} ...]")
        ps = solve(scores)
        if ps:
          printf("positions={ps}", ps=ps[1:])
          for t in irange(1, 7):
            rs = list(i for (i, p) in enumerate(ps) if p == t)
            printf("team {t}: {rs} score = {s}", s=sum(rs[:4]))
          printf()
      
  2. arthurvause 27 May 2014 at 10:00 pm

    My variation, which chooses the smallest possible non-scoring team positions (fifth and sixth) for each combination of scoring positions. It finds an example set of team positions in a respectable 250ms.

    from itertools import combinations, permutations
    
    # best and worst scores
    best, worst  = 1+2+3+4,  37+38+39+40
    
    progressions = set()
    for d,n in combinations(range(1,7),2):
      for m in xrange(1,11):
        if m*d**3 >= best and m*n**3 <=worst:
          progressions.add(( m*d**3, m*d**2*n, m*d*n**2, m*n**3))
    print "candidate geometric progressions of 4 teams", progressions
    
    scores=set()          
    for p,q in permutations(progressions,2):
      if p[3]==q[0]:
        scores.add( p + q[1:4] )
    
    def TeamPositions(positions,s,n):
      for c3 in combinations(positions & set(range(1,s[n]-5)),3):
        fourth=s[n]-sum(c3)
        if fourth in positions and fourth>max(c3):
          fifths = [x for x in positions- set(c3+(fourth,)) if x>fourth]
          if len(fifths)>0:
            fifth=min(fifths)
            sixths = [x for x in positions- set(c3+(fourth,fifth)) if x>fifth]
            if len(sixths)>0:
              sixth=min(sixths)
              c=tuple(sorted(c3))+(fourth,fifth,sixth)
              if n==6:
                yield [c]
              else:
                for p in  TeamPositions(positions-set(c),s,n+1):
                  yield [c]+p
    
    for s in scores:
      print "\nExample position for team scores",s
      
      for teams in TeamPositions(set(range(1,43)),s,0):
    
        used = set()
        for team in teams:
          print team, "score",sum(team[:4])
          for rider in team:
            used.add(rider)
        assert(len(used)==42)   
        break
    
    
    • arthurvause 28 May 2014 at 2:44 pm

      I realised that my code above doesn’t exhaustively check that there are no solutions for the scores 16, 24, 36, 54, 72, 96, 128, as only non-scoring postions immediately following the fourth scoring position are checked.

      To remedy this, here is another version that checks for any set of scoring postions, and if one is found checks for scoring +non-scoring positions.

      The code mecomes a bit messier, but in fact runs slightly faster at 187ms, and verifies that there isn’t any combination of scoring positions for 16, 24, 36, 54, 72, 96, 128.

      from itertools import combinations, permutations
      
      # best and worst scores
      best, worst  = 1+2+3+4,  37+38+39+40
      
      progressions = set()
      for d,n in combinations(range(1,7),2):
        for m in xrange(1,11):
          if m*d**3 >= best and m*n**3 <=worst:
            progressions.add(( m*d**3, m*d**2*n, m*d*n**2, m*n**3))
      print "candidate geometric progressions of 4 teams", progressions
      
      scores=set()          
      for p,q in permutations(progressions,2):
        if p[3]==q[0]:
          scores.add( p + q[1:4] )
      
      
      # find a set of scoring and optionally non-scoring positions for the seven teams
      def TeamPositions(positions,s,n,NonScoring):
        for c3 in combinations(positions & set(range(1,s[n]-5)),3):
          fourth=s[n]-sum(c3)
          if fourth in positions and fourth>max(c3):
            if NonScoring:
              fifthssixths = sorted([x for x in positions- set(c3+(fourth,)) if x>fourth])
              if len(fifthssixths)>=2:
                fifth,sixth = fifthssixths[0],fifthssixths[1]
                c=tuple(sorted(c3))+(fourth,fifth,sixth)
              else:
                return
            else:
              c=c3+(fourth,)
            if n==6:
              yield [c]
            else:
              for p in  TeamPositions(positions-set(c),s,n+1,NonScoring):
                yield [c]+p
      
      for s in scores:
        print "\nExample position for team scores",s
      
        for test in TeamPositions(set(range(1,43)),s,0, False):
          print "scoring positions exist for",s
          print "trying scoring + non-scoring positions..."
          for teams in TeamPositions(set(range(1,43)),s,0,True):
      
            used = set()
            for team in teams:
              print team, "score",sum(team[:4])
              for rider in team:
                used.add(rider)
            assert(len(used)==42)
            print ""
            break
          break
      
      • Jim Randell 1 June 2014 at 10:50 am

        Hi Arthur. Thanks for posting your code.

        I’ve been looking at this puzzle again to try and see if I can generate a definitive list of solutions where geometric progressions with a common ratio of 1 are allowed, but one bit of your code that I don’t quite follow is the part where non-scoring runners are allocated.

        It looks like the algorithm allocates them as it goes along after it allocates the scoring runners for a team. Then it chooses the next two available positions as the non-scoring positions for that team. But how do we know that these positions won’t be required to make up the score of a team whose positions haven’t been determined yet? I think it may be possible that this means the algorithm could fail to find an allocation of positions where one exists. (Although obviously it does find positions that solve the problem).

        • arthurvause 2 June 2014 at 9:37 am

          Yes, that is correct, allocating the non-scoring postions for each team as it goes along might exclude a possible solution, hence the second version, which checks only scoring positions first, to verify that there are no scoring positions for team scores 16, 24, 36, 54, 72, 96, 128.

          The algorithm isn’t ideal, as it doesn’t find all solutions, and would not have worked at all if there had been valid scoring postions for 16, 24, 36, 54, 72, 96, 128, or if there weren’t team positions for 27, 36, 48, 64, 80, 100, 125 with non-scoring positions immediately following the fourth team member.

          It was really just an attempt to find a solution quickly. I can’t see a way of performing a rigorous check in a fast time.

          In fact I was wondering how anyone could have found a solution to the problem without the aid of a computer program.

          • Jim Randell 2 June 2014 at 10:26 am

            I think once you’ve found the two possible sequences – 16, 24, 36, 54, 72, 96, 128 and 27, 36, 48, 64, 80, 100, 125 – we can eliminate the first one by summing the terms and comparing them with the triangular numbers T(4), T(8), T(12), …

            T(4) = 10 ≤ 16
            T(8) = 36 ≤ 40 = 16 + 24
            T(12) = 78 > 76 = 16 + 24 + 36

            So it is not possible for the first three teams to score 16, 24, 36 (= 76 points) as the sum of the positions of 12 scoring runners has to be at least 78.

            So, we’re left with 27, 36, 48, 64, 80, 100, 125 as the only possible solution. So if the question has an answer we can determine it without finding an example of the finishing positions.

            I like constructive solutions, so I wrote a program to determine a possible assignment of finishing positions, but it does run slower than I would like.

  3. Brian Gladman 20 June 2014 at 7:26 pm

    I only noticed this one recently and decided to try it as Jim has given it four stars.

    from itertools import combinations, count
    from fractions import Fraction
    
    # A 4 term geometric progression (a, a.(n/d), a.(n/d)^2, a.(n/d)^3),
    # where n / d is a rational fraction in its lowest terms,  will have 
    # integer values only if a is a multiple of d. So a 4 term geometric
    # progression is a multiple of (d^3, d^2.n, d.n^2, n^3). The minimum
    # first term is 10 (1+2+3+4) and the maximum last term is 154 (37+38
    # +39+40) so (n/d)^3 <= 154 / 10 and hence 2.n < 5.d. And n^3 <= 154
    # so n < 6.
    def geometric_seqs():
      # generate possible four term sequences
      t = ((d ** 3, d ** 2 * n, d * n ** 2, n ** 3) for n in range(1, 6) 
           for d in range(1, n) if 2 * n < 5 * d)
      # now join two such sequences into one seven term sequence
      for a, b in combinations(t, 2):
        # the last term of the first equals the first term of the last
        if a[-1] == b[0]:
          c = a + b[1:]
          # now apply a possible multiplier to the whole sequence
          for m in count(1):
            if m * c[-1] > 154:
              break
            if m * c[0] >= 10:
              yield tuple(m * x for x in c)
    
    # return partitions of the integer 'n' into 'l' different
    # integers in increasing order
    def int_part(n, l, v = []):
      lv = len(v)
      # if we have l - 1 parts and the remainder is largest
      if lv == l - 1 and n > v[-1]:
        # return the partition
        yield v + [n]
      else:
        # otherwise remove another part (larger than previous) 
        if not lv or n >= (l - lv) * (v[-1] + 1):
          for i in range(v[-1] + 1 if lv else 1, n + 1):
            yield from int_part(n - i, l, v + [i])
    
    def solve(seq, ns, tt, l):
      # if all teams have been allocated winning positions
      if l == 7:
        yield tt
      else:
        # find four possible winning positions for team 'l'
        for ip in int_part(seq[l], 4):
          # if they are so far unallocated, allocate them and
          # move on to the next team
          if set(ip) < ns:
            yield from solve(seq, ns - set(ip), tt + [ip], l + 1)
    
    # the set of scoring positions
    scores = set(range(1, 41))
    # run through the possible geometric sequences
    for seq in geometric_seqs():
      # find a valid set of scoring positions for the seven teams
      for s in solve(seq, scores, [], 0):
        # find the non scoring positions
        rem = scores 
        for v in s:
          rem -= set(v)
        print('Team scores:        {}'.format(seq))
        print('Winning positions : {}'.format(s))
        print('No-score positions: {}'.format(tuple(sorted(rem))))
        break
    
    • Brian Gladman 20 June 2014 at 8:01 pm

      The documentation in the first ten lines contains some errors – these lines should be replaced with:

      from itertools import combinations, count
      
      # The geometric progression {a, a.(n/d), a.(n/d)^2, a.(n/d)^3}, where
      # n/d is a rational value in its lowest terms,  has integer values if
      # d^3 divides a.  It is hence a multiple of (d^3, d^2.n, d.n^2, n^3). 
      # The minimum first term is 10 (1+2+3+4) and the maximum last term is
      # 154 (37+38+39+40) so (n/d)^3 <= 154 / 10 and hence 2.n < 5.d;  also
      # n^3 <= 154 so n < 6.
      
      • Brian Gladman 20 June 2014 at 8:28 pm

        And to play with more than one geometric sequence (for example with some values the same), line 60 needs to be changed to ‘scores.copy()’ (this is really a bug).

    • Jim Randell 20 June 2014 at 11:40 pm

      Hi Brian. Thanks for posting your code. I haven’t gone through it in detail, but I think you might need something like the allocate_remaining() routine in my first program to check that the non-scoring runners can be allocated given the positions of the scoring runners.

      When I run your program it gives the scoring positions for the teams with 100 and 125 points as [16, 17, 27, 40] and [18, 32, 36, 39], but there are only two runners (in positions 41 and 42) that can be the non-scoring runners for both of these teams, so that particular arrangement won’t be possible.

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: