Sunday Times Teaser 3213 – A Streetcar Named Divisor

by BRG on April 19, 2024

by Colin Vout

Published Friday April 19 2024 (link)

In retrospect it was inadvisable to ask an overenthusiastic mathematician to overhaul our local tram routes. They allocated a positive whole number less than 50 to each district’s tram stop. To find the number of the tram going from one district to another you would “simply” (their word, not mine) find the largest prime divisor of the difference between the two districts’ numbers; if this was at least 5 it was the unique route number, and if not there was no direct route.

The routes, each in increasing order of the stop numbers, were: Atworth, Bratton, Codford; Atworth, Downlands, Enford; Bratton, Figheldean, Enford; Downlands, Figheldean, Codford; Codford, Enford.

What were the route numbers, in the order quoted above?

From → Uncategorized

8 Comments Leave one →

BRG permalink

Painfully slow in CPython but tolerable using PyPy (but now amended with speed improvements suggested by Frits).


from itertools import combinations

# the set of primes less than 49
pr = {3, 5, 7}
pr |= {2} | {n for n in range(11, 49, 2) if all(n % p for p in pr)}
pr = sorted(pr, reverse=True)

# map numbers in 1..48 to their maximum prime factors
n2mf = {1:1}
for d in range(2, 49):
  for p in pr:
    if not d % p:
      n2mf[d] = p
      break

# routes (regions within routes are in numeric order)
routes = {'ABC', 'ADE', 'BFE', 'DFC', 'CEC'}

# hence possible orders for tram stop numbers 
# A < B < D < F < C < E
# A < D < B < F < C < E
# nine routes: (AB, BC) (AD, DE) (BF, FE), (DF, FC), (CE)

# since all route numbers depend on differences between
# region numbers, we can set A equal to one
a = 1

# consider possible tram stop numbers for F, C and E
# D - A >= 5; F - D >= 7; |B - D| >= 1  ==> F >= A + 13 
for f, c, e in combinations(range(14, 50), 3):
  # check that routes CE, FC and FE are valid
  if c >= e or (r5 := n2mf[e - c]) < 5:
    continue
  if f >= c or (r4 := n2mf[c - f]) < 5:
    continue
  if f >= e or (r3 := n2mf[e - f]) < 5:
    continue
  
  # route numbers must be different
  if len({r3, r4, r5}) != 3:
    continue
  
  # consider possible tram stop numbers for B and D 
  for b, d in combinations(range(6, f - 4), 2):
    for b, d in ((b, d), (d, b)):
      # check that routes BF, DF, AB and AD are valid
      if not (n2mf[f - b] == r3):
        continue
      if not (n2mf[f - d] == r4):
        continue
      if not ((r1 := n2mf[b - a]) == n2mf[c - b] >= 5):
        continue
      if not ((r2 := n2mf[d - a]) == n2mf[e - d] >= 5):
        continue

      # check that the route numbers are unique
      if len(set((rns := (r1, r2, r3, r4, r5)))) == 5:
        print(f'routes: {rns}, regions: {(a, b, c, d, e, f)}')

from itertools import combinations

# the set of primes less than 49

pr = {3, 5, 7}

pr |= {2} | {n for n in range(11, 49, 2) if all(n % p for p in pr)}

pr = sorted(pr, reverse=True)

# map numbers in 1..48 to their maximum prime factors

n2mf = {1:1}

for d in range(2, 49):

for p in pr:

if not d % p:

n2mf[d] = p

break

# routes (regions within routes are in numeric order)

routes = {'ABC', 'ADE', 'BFE', 'DFC', 'CEC'}

# hence possible orders for tram stop numbers

# A < B < D < F < C < E

# A < D < B < F < C < E

# nine routes: (AB, BC) (AD, DE) (BF, FE), (DF, FC), (CE)

# since all route numbers depend on differences between

# region numbers, we can set A equal to one

a = 1

# consider possible tram stop numbers for F, C and E

# D - A >= 5; F - D >= 7; |B - D| >= 1 ==> F >= A + 13

for f, c, e in combinations(range(14, 50), 3):

# check that routes CE, FC and FE are valid

if c >= e or (r5 := n2mf[e - c]) < 5:

continue

if f >= c or (r4 := n2mf[c - f]) < 5:

continue

if f >= e or (r3 := n2mf[e - f]) < 5:

continue

# route numbers must be different

if len({r3, r4, r5}) != 3:

continue

# consider possible tram stop numbers for B and D

for b, d in combinations(range(6, f - 4), 2):

for b, d in ((b, d), (d, b)):

# check that routes BF, DF, AB and AD are valid

if not (n2mf[f - b] == r3):

continue

if not (n2mf[f - d] == r4):

continue

if not ((r1 := n2mf[b - a]) == n2mf[c - b] >= 5):

continue

if not ((r2 := n2mf[d - a]) == n2mf[e - d] >= 5):

continue

# check that the route numbers are unique

if len(set((rns := (r1, r2, r3, r4, r5)))) == 5:

print(f'routes: {rns}, regions: {(a, b, c, d, e, f)}')

John Z permalink

or:

Python

n2mf = (0, 1) + tuple(max(p for p in pr if not d % p ) for d in range(2, 49))

1
2
3

n2mf = (0, 1) + tuple(max(p for p in pr if not d % p ) for d in range(2, 49))

Reply
John Z permalink

Could line 45 use permutations instead of combinations and remove line 46?

Reply
- BRG permalink
  
  Yes but it would be slower since, for the majority of the inputs, there will be
  many more permutations than there are twice the number of combinations.
  
  Reply
  - JohnZ permalink
    
    Permutations gives n.(n-1) iterations. Combinations followed by two
    way flip gives n.(n-1)/2 . 2: the same. I put in a count += 1 in the
    loop. Curiously at the point where a solution is found, there are
    14255 iterations with combinations (should be even but isn’t!) but
    14250 iterations with permutations. At the end of the run they have
    both done 86744 iterations. The difference in the count when the
    solution is found leaves me perplexed.
    
    Reply
    - BRG permalink
      
      HI John, You are right about this. The original line 45
      combined three items (a, b, d) which made the approach
      faster. But when I later removed the ‘a’ (by setting it
      to 1) the approach no longer offered a speed advantage.
      
      I think the odd count simply means that the solution
      is output on the first time the inner loop runs, not
      the second.

JohnZ permalink

Great solution Brian. I permit myself some “kibbitzing”:

A few lines could be saved (but no speed gain) by removing line 7 and replacing lines 10 – 15 with:

Python

n2mf = {1:1} | {d: max(p for p in pr if not d % p ) for d in range(2, 49)}

1
2
3

n2mf = {1:1} | {d: max(p for p in pr if not d % p ) for d in range(2, 49)}

Reply
- BRG permalink
  
  A nice suggestion, John. I often overlook the set like features of dictionaries
  since they are a relatively recent addition to Python.
  
  Reply

Sunday Times Teaser 3213 – A Streetcar Named Divisor

by Colin Vout

Published Friday April 19 2024 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta