Enigmatic Code

Programming Enigma Puzzles

Enigma 1418: Non-scoring runners

From New Scientist #2578, 18th November 2006

In cross-country races, teams consist of six runners; team scores are calculated by adding together the finishing positions of the first four runners to finish in each team, the team with the lowest score winning. Individuals never tie. The fifth and sixth runners in each team do not score but if they finish ahead of scoring runners in other teams they make the positions of those runner and their teams’ scores worse.

In a race involving three teams, each of six runners, no two teams had the same score. The third team’s score was a multiple of the second team’s score, which itself was a multiple of the winning team’s score. The sum of the positions of the first three finishers in the winning team, the sum of the positions of the first two finishers in the second team and the position of the first finisher in the third team were identical.

What were the positions of the non-scoring runners in the second team?

[enigma1418]

Advertisements

One response to “Enigma 1418: Non-scoring runners

  1. Jim Randell 24 June 2013 at 8:42 am

    This Python program runs in 107ms.

    from itertools import combinations, product
    from collections import defaultdict
    from enigma import irange, diff, printf
    
    # there are 18 runners, so 18 finishing positions
    pos = list(irange(1, 18))
    
    # accumulate scores by positions
    r = defaultdict(list)
    for t in combinations(pos, 4):
      r[sum(t[:4])].append(t)
    
    # C is a multiple of B, B is a multiple of A
    # so the maximum value of A is the max score / 4
    (mn, mx) = (min(r.keys()), max(r.keys()))
    for A in irange(mn, mx // 4):
      if A not in r: continue
      for B in irange(2 * A, mx // 2, A):
        if B not in r: continue
        for C in irange(2 * B, mx, B):
          if C not in r: continue
    
          # choose non-intersecting solutions
          for (a, b, c) in product(r[A], r[B], r[C]):
            s = set(a).union(b, c)
            if len(s) != 12: continue
            # check the conditions
            if not(c[0] == sum(b[:2]) == sum(a[:3])): continue
    
            # find the non-scoring runners
            ns = diff(pos, s)
            for cn in combinations((x for x in ns if x > max(c)), 2):
              for bn in combinations((x for x in ns if x > max(b) and x not in cn), 2):
                an = tuple(x for x in ns if x > max(a) and x not in bn and x not in cn)
                if len(an) != 2: continue
    
                printf("A={A} {a} {an}, B={B} {b} {bn}, C={C} {c} {cn}")
    

    Solution: The non-scoring runners in the second team were placed 12th and 14th.

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: