Sunday Times Teaser 2707 – Good Times

by H Bradley and C Higgins

A bus travels on a straight road between two towns, passing through six others on the way. The distances between adjacent towns are all different whole numbers of miles with the longest and shortest differing by six miles. The average of the distances between adjacent towns and the average of the distances between any pair of towns have the same two digits but in a different order.

How long is the bus route?

3 Comments Leave one →

brian gladman permalink


from itertools import count, permutations 

def cumulative_sum(x):
  it = iter(x)
  s = next(it)
  yield s
  for c in it:
    s = s + c
    yield s

# the average distance between adjacent towns has two digits
for av1 in count(11):
  # the digit reversed value
  av2 = 10 * (av1 % 10) + av1 // 10
  if av1 < av2:
  
    sol = set()
    # test each possible arrangement of the seven distances
    for s1 in permutations(i for i in range(av1 - 3, av1 + 4)): 
      
      # don't check symmetrical arrangements
      if s1[0] < s1[-1]:
        # calculate the distances of each town from the start
        s2 = [0] + list(cumulative_sum(s1))  
        
        # and the average of the distances between any two towns
        s3 = list(abs(j - i) for j in s2 for i in s2 if j != i)
        av3, r = divmod(sum(s3), len(s3))
        
        if not r and av3 == av2:
          sol.add(7 * av1)
    else:
      if not sol:
        continue
      for s in sol:
        print('The route is {} miles.'.format(s))
      break
    break

from itertools import count, permutations

def cumulative_sum(x):

it = iter(x)

s = next(it)

yield s

for c in it:

s = s + c

yield s

# the average distance between adjacent towns has two digits

for av1 in count(11):

# the digit reversed value

av2 = 10 * (av1 % 10) + av1 // 10

if av1 < av2:

sol = set()

# test each possible arrangement of the seven distances

for s1 in permutations(i for i in range(av1 - 3, av1 + 4)):

# don't check symmetrical arrangements

if s1[0] < s1[-1]:

# calculate the distances of each town from the start

s2 = [0] + list(cumulative_sum(s1))

# and the average of the distances between any two towns

s3 = list(abs(j - i) for j in s2 for i in s2 if j != i)

av3, r = divmod(sum(s3), len(s3))

if not r and av3 == av2:

sol.add(7 * av1)

else:

if not sol:

continue

for s in sol:

print('The route is {} miles.'.format(s))

break

As pointed out by Peter below, the teaser is OK. My original code (now corrected) was based on an incorrect assumption.

With some analysis, a much faster version is possible:


from itertools import count, permutations 

# Distances between towns x + a, x + b, x + c, x + d, x + e, x + f, x + g 
# with average value x and (a .. g) permutations of (-3 .. 3)

# pair average = 3.x + { 7.(a + g) + 12.(b + f) + 15.(c + e) + 16.d } / 28
# the only permutations that work are those where this value is an integer

# compute the {} term above for those permutations that give integer values
p_set = set()
for p in permutations(range(-3, 4)):
  # skip permutations that are left/right reflections
  if p[0] < p[6]:
    s = 7 * sum(p) + 5 * (p[1] + p[5]) + 8 * (p[2] + p[4]) + 9 * p[3]  
    if not s % 28:
      p_set.add(s // 28)

# the average distance between adjacent towns has two different digits
for av1 in count(12):
  # the digit reversed value
  av2 = 10 * (av1 % 10) + av1 // 10
  # check all possible pair averages
  for sp in p_set:
    if 3 * av1 + sp == av2:
      print('The route is {} miles.'.format(7 * av1))
      break
  else:
    continue
  break

from itertools import count, permutations

# Distances between towns x + a, x + b, x + c, x + d, x + e, x + f, x + g

# with average value x and (a .. g) permutations of (-3 .. 3)

# pair average = 3.x + { 7.(a + g) + 12.(b + f) + 15.(c + e) + 16.d } / 28

# the only permutations that work are those where this value is an integer

# compute the {} term above for those permutations that give integer values

p_set = set()

for p in permutations(range(-3, 4)):

# skip permutations that are left/right reflections

if p[0] < p[6]:

s = 7 * sum(p) + 5 * (p[1] + p[5]) + 8 * (p[2] + p[4]) + 9 * p[3]

if not s % 28:

p_set.add(s // 28)

# the average distance between adjacent towns has two different digits

for av1 in count(12):

# the digit reversed value

av2 = 10 * (av1 % 10) + av1 // 10

# check all possible pair averages

for sp in p_set:

if 3 * av1 + sp == av2:

print('The route is {} miles.'.format(7 * av1))

break

else:

continue

break

This is one of the best teasers we have seen recently.

Peter Hayes permalink

There is nothing wrong with this teaser and it has a solution; indeed, a unique one.

Re-examine your assumptions.

Reply
- brian gladman permalink
  
  Yes, when I woke up this morning I realised what was wrong. 🙂
  
  Reply

Sunday Times Teaser 2707 – Good Times

by H Bradley and C Higgins

Leave a comment to brian gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta