Sunday Times Teaser 3201 – Spare Routes

by BRG on 26 January 2024

by Colin Vout

Published Friday January 26 2024 (link)

Three companies run scenic coach trips either way between some pairs of towns in my holiday destination. Each route between two towns is served by just one company, but has one or more alternatives via another town. In particular, every Redstart route could be replaced by a unique combination of two Bluetail routes, every Bluetail by a unique combination of two Greenfinches, and every Greenfinch by a unique combination of a Redstart and a Greenfinch. This wouldn’t be possible with fewer towns or fewer routes.

I toured one route each day, starting from the town I’d arrived at the previous day but changing the company, never repeating a route in either direction, and involving as many of the routes as I could.

Which companies did I use, in order (as initials, eg, R,B,G,B)?

From → Uncategorized

4 Comments Leave one →

BRG permalink

The teaser took a lot of effort over most of the week since publication!


from itertools import count, product

# dictionary for the specified alternative routes
dar = dict(zip('RBG', [('B', 'B'), ('G', 'G'), ('R', 'G')]))

sort = lambda a, b: (a, b) if a < b else (b, a)

# for route <ab>, check for a unique alternative route in the map 
# <r2c> that uses the companies in <cps> (credit: Frits)
def check_alt(r2c, nt, ab, cps):
  return sum(1 for t in set(range(nt)) - set(ab) 
         if {r2c[sort(t, x)] for x in ab} == cps) == 1

# generate possible routes between <nt> towns
def gen_routes(nt):
  # the possible routes 
  rts = [(a, b) for a in range(nt) for b in range(a + 1, nt)]

  # assign routes to companies (' ' for routes without companies)
  for cps in product('RBG ', repeat=len(rts) - 1):
    cps = ('R', ) + cps
    
    # numbers of routes: nR < nB < nG 
    if cps.count('R') < cps.count('B') < cps.count('G'):
      
      # form the map of the routes
      r2c = dict(zip(rts, cps))

      # check that it meets the unique alternative route requirements
      if all(check_alt(r2c, nt, rt, set(dar[cp]))
                    for rt, cp in r2c.items() if cp in 'RBG'):
        
        # return the map for connected towns  
        yield r2c
                  
# generate complete tours (in <tour>) through the map <r2c>;
# the tour must return to its starting town if cyclic = True
def tours(r2c, tour, cyclic=False):
  # the last (or first) route 
  (la, lb), lcp = (td := list(tour.items()))[-1]
  # is the tour cyclic?
  if not cyclic or lb == td[0][0][0]:
    yield tour 
  # conisder possible next routes 
  for (a, b), cp in r2c.items():
    # chose a new company
    if cp not in (lcp,' ') and not {(a, b), (b, a)}.intersection(tour):
      # can we connect to the previous town?
      td = tour.copy()
      if lb in {a, b}:
        if lb == a:
          td[a, b] = cp
        else:
          td[b, a] = cp
        yield from tours(r2c, td)

# consider an increasing number of towns
for nt in count(4):

  # collect maps indexed on their number of routes
  nr2m = dict()
  for r2c in gen_routes(nt):
    nr = sum(1 for r, c in r2c.items() if c != ' ')
    nr2m[nr] = nr2m.get(nr, []) + [r2c]
  
  # consider maps with the minimum number of routes 
  if nr2m:
    # collect tours based on the number of routes used
    nr2t = dict()  
    for r2c in nr2m[min(nr2m)]:
      # the starting route for the tour
      for (a, b), cp in r2c.items():
        for tour in tours(r2c, {(a, b):cp}):
          nr2t[nr] = nr2t.get((nr := len(tour)), set()) | {tuple(tour.items())}
    
    # output tours that use the most routes
    if nr2t:
      print(f"Towns Map: {r2c}\nTours:")
      for tr in nr2t[max(nr2t)]:
        print(f"  {''.join(p[1] for p in tr)} ==> {tr}")
      break

from itertools import count, product

# dictionary for the specified alternative routes

dar = dict(zip('RBG', [('B', 'B'), ('G', 'G'), ('R', 'G')]))

sort = lambda a, b: (a, b) if a < b else (b, a)

# for route <ab>, check for a unique alternative route in the map

# <r2c> that uses the companies in <cps> (credit: Frits)

def check_alt(r2c, nt, ab, cps):

return sum(1 for t in set(range(nt)) - set(ab)

if {r2c[sort(t, x)] for x in ab} == cps) == 1

# generate possible routes between <nt> towns

def gen_routes(nt):

# the possible routes

rts = [(a, b) for a in range(nt) for b in range(a + 1, nt)]

# assign routes to companies (' ' for routes without companies)

for cps in product('RBG ', repeat=len(rts) - 1):

cps = ('R', ) + cps

# numbers of routes: nR < nB < nG

if cps.count('R') < cps.count('B') < cps.count('G'):

# form the map of the routes

r2c = dict(zip(rts, cps))

# check that it meets the unique alternative route requirements

if all(check_alt(r2c, nt, rt, set(dar[cp]))

for rt, cp in r2c.items() if cp in 'RBG'):

# return the map for connected towns

yield r2c

# generate complete tours (in <tour>) through the map <r2c>;

# the tour must return to its starting town if cyclic = True

def tours(r2c, tour, cyclic=False):

# the last (or first) route

(la, lb), lcp = (td := list(tour.items()))[-1]

# is the tour cyclic?

if not cyclic or lb == td[0][0][0]:

yield tour

# conisder possible next routes

for (a, b), cp in r2c.items():

# chose a new company

if cp not in (lcp,' ') and not {(a, b), (b, a)}.intersection(tour):

# can we connect to the previous town?

td = tour.copy()

if lb in {a, b}:

if lb == a:

td[a, b] = cp

else:

td[b, a] = cp

yield from tours(r2c, td)

# consider an increasing number of towns

for nt in count(4):

# collect maps indexed on their number of routes

nr2m = dict()

for r2c in gen_routes(nt):

nr = sum(1 for r, c in r2c.items() if c != ' ')

nr2m[nr] = nr2m.get(nr, []) + [r2c]

# consider maps with the minimum number of routes

if nr2m:

# collect tours based on the number of routes used

nr2t = dict()

for r2c in nr2m[min(nr2m)]:

# the starting route for the tour

for (a, b), cp in r2c.items():

for tour in tours(r2c, {(a, b):cp}):

nr2t[nr] = nr2t.get((nr := len(tour)), set()) | {tuple(tour.items())}

# output tours that use the most routes

if nr2t:

print(f"Towns Map: {r2c}\nTours:")

for tr in nr2t[max(nr2t)]:

print(f" {''.join(p[1] for p in tr)} ==> {tr}")

break

John Z permalink

With a number of improvements to my previous versions suggested by Brian (line 16) or inspired by his code (line 7 and line 53: pump priming) and a few of my own such as completing alternate route verification in one pass rather than three and moving the function out of the body of the main program

The order of routes ‘BGRX’ in the ‘product’ function (line 49) gives a much faster execution time than ‘RGBX’ or ‘XRGB’.


from itertools import combinations, product, count
from sys import exit

ts = lambda x, y : (x, y) if x < y else (y, x) # tuple, smaller number first

altrtd = {'R': 'BB', 'B': 'GG', 'G': 'RG'} # alt route dictionary

# function returns true if one and only one alternate route with the correct
# combination is available for all direct routes 
def altrtcheck():

  # consider all town pairs (routes)
  for (sp, fp), cmpy in rm.items():
    
    if cmpy != 'X': # Redstart, Greenfinch or Bluetail but not 'X'

      # count valid two-hop alternative routes from <sp> to <fp>
      # via all other towns; must equal 1
      if sum({rm[ts(sp, vp)], rm[ts(vp, fp)]} == set(altrtd[cmpy])
                for vp in set(range(1, n + 1)) - {sp, fp}) != 1:
        return False
      
  return True

# recursive town touring function
# arguments: previous town, previous company, itinerary so far
def tour(prevt, prevc = 0, itin = []):
  
  # consider next town to visit: all except the previous town
  for nt in set(range(1, n + 1)) - {prevt}:
    
    route = ts(prevt, nt) # smaller town number first

    # can't have already used route; must change carrier; route exists
    if route not in itin and prevc != rm[route] != 'X':
      yield from tour(nt, rm[route], itin + [route])
      
  yield itin

# ---------------------------- Main Program ---------------------------- #
# consider number of towns <n>, minimum = 4 (R + 2B + 2G routes = 5 routes)
for n in count(4):

  # town to town combinations
  t2t = tuple(combinations(range(1, n + 1), 2))
  
  # consider all possible town pair interconnections (less 1 for initial 'R')
  for rc in product('BGRX', repeat = n * (n - 1) // 2 - 1):
    
    # make a (dictionary) route map of all town pairs assigning a bus 
    # company (B, R, G) or none (X) to each pair of towns in the route map
    rm = dict(zip(t2t, ('R',) + rc)) # initial 'R' to reduce exec time (~ /4)
    
    # verify that the alternative route rules are respected
    if not altrtcheck() :
      continue

    # Part Two: travel around the first network found that obeys all the Teaser
    # rules; following all itineraries using each town in turn as a start point
    itys = sorted((iti for s in range(1, n + 1) for iti in tour(s)), key = len)
    
    print(rm, '\n') # print route map

    # consider itineraries from longest
    for ity in itys[::-1]:
      if len(ity) < len(itys[-1]): #stop if a shorter than max itinerary length
        exit()
      print(ity) # print longest itineraries (some steps are backwards)
      print(' '.join(rm[yy] for yy in ity), '\n')

from itertools import combinations, product, count

from sys import exit

ts = lambda x, y : (x, y) if x < y else (y, x) # tuple, smaller number first

altrtd = {'R': 'BB', 'B': 'GG', 'G': 'RG'} # alt route dictionary

# function returns true if one and only one alternate route with the correct

# combination is available for all direct routes

def altrtcheck():

# consider all town pairs (routes)

for (sp, fp), cmpy in rm.items():

if cmpy != 'X': # Redstart, Greenfinch or Bluetail but not 'X'

# count valid two-hop alternative routes from <sp> to <fp>

# via all other towns; must equal 1

if sum({rm[ts(sp, vp)], rm[ts(vp, fp)]} == set(altrtd[cmpy])

for vp in set(range(1, n + 1)) - {sp, fp}) != 1:

return False

return True

# recursive town touring function

# arguments: previous town, previous company, itinerary so far

def tour(prevt, prevc = 0, itin = []):

# consider next town to visit: all except the previous town

for nt in set(range(1, n + 1)) - {prevt}:

route = ts(prevt, nt) # smaller town number first

# can't have already used route; must change carrier; route exists

if route not in itin and prevc != rm[route] != 'X':

yield from tour(nt, rm[route], itin + [route])

yield itin

# ---------------------------- Main Program ---------------------------- #

# consider number of towns <n>, minimum = 4 (R + 2B + 2G routes = 5 routes)

for n in count(4):

# town to town combinations

t2t = tuple(combinations(range(1, n + 1), 2))

# consider all possible town pair interconnections (less 1 for initial 'R')

for rc in product('BGRX', repeat = n * (n - 1) // 2 - 1):

# make a (dictionary) route map of all town pairs assigning a bus

# company (B, R, G) or none (X) to each pair of towns in the route map

rm = dict(zip(t2t, ('R',) + rc)) # initial 'R' to reduce exec time (~ /4)

# verify that the alternative route rules are respected

if not altrtcheck() :

continue

# Part Two: travel around the first network found that obeys all the Teaser

# rules; following all itineraries using each town in turn as a start point

itys = sorted((iti for s in range(1, n + 1) for iti in tour(s)), key = len)

print(rm, '\n') # print route map

# consider itineraries from longest

for ity in itys[::-1]:

if len(ity) < len(itys[-1]): #stop if a shorter than max itinerary length

exit()

print(ity) # print longest itineraries (some steps are backwards)

print(' '.join(rm[yy] for yy in ity), '\n')

John Z permalink

I kept fiddling with this and finally decide to go for stict application of the “This wouldn’t be possible with fewer towns or fewer routes.” criterion. My code was already applying ‘fewer towns’ it now ensures ‘fewest routes’ even though I don’t think this is strictly necessary. The result is the same except that it takes longer to produce.


from itertools import combinations, product, count

ts = lambda x, y : (x, y) if x < y else (y, x) # tuple, smaller number first

# recursive town touring function
# arguments: previous town, previous company, itinerary so far
def tour(prevt, prevc = 0, itin = ()):
  
  # consider next town to visit: all except the previous town
  for nt in set(range(1, n + 1)) - {prevt}:
    
    route = ts(prevt, nt) # smaller town number first

    # can't have already used route; must change carrier; route exists
    if route not in itin and prevc != rm[route] != 'X':
      yield from tour(nt, rm[route], itin + (route,))
      
  yield itin

# ---------------------------- Main Program ---------------------------- #
altrtd = {'R': set('BB'), 'B': set('GG'), 'G': set('RG')} # alt route dictionary
                
# consider number of towns , minimum = 4 (R + 2B + 2G routes = 5 routes)
for n in count(4):

  sols = [] # store potential solutions

  # town to town combinations
  t2t = tuple(combinations(range(1, n + 1), 2))
  
  # consider all possible town pair interconnections (less 1 for initial 'R')
  for rc in product('BGRX', repeat = len(t2t) - 1):
    
    # make a (dictionary) route map of all town pairs assigning a bus 
    # company (B, R, G) or none (X) to each pair of towns in the route map
    rm = dict(zip(t2t, ('R',) + rc)) # initial 'R' to reduce exec time (~ /4)
    
    # verify that the alternate route rules are respected
    # count valid two-hop alternative routes from  to 
    # via all other towns:  via point; must equal 1
    if (all(sum({rm[ts(sp, vp)], rm[ts(vp, fp)]} == altrtd[cmpy]
                for vp in set(range(1, n + 1)) - {sp, fp}) == 1
            for (sp, fp), cmpy in rm.items() if cmpy != 'X')):

      sols += [rm]

  if sols:
    # find the route map with the least number of routes, i.e. most X's
    rm = max(sols, key = lambda _ : tuple(_.values()).count('X'))
    print(rm, '\n')

    # travel around the network found that obeys all the Teaser rules
    # following all itineraries using each town in turn as a start point
    ity = max((iti for s in range(1, n + 1) for iti in tour(s)), key = len)

    # For legibility, invert steps <s> that are 'backwards'
    ityb = [ity[0][::-1] if ity[0][0] in ity[1] else ity[0]] # first step
    ityb += [s[::-1] if s[1] in r else s for r, s in zip(ity, ity[1::])]

    
   # print longest itinerary
    print(''.join(str(a) + ' -> 'for (a, b) in ityb) + str(ity[-1][1]))
    print('  ' + '    '.join(rm[yy] for yy in ity), '\n')
    
    break

from itertools import combinations, product, count

ts = lambda x, y : (x, y) if x < y else (y, x) # tuple, smaller number first

# recursive town touring function

# arguments: previous town, previous company, itinerary so far

def tour(prevt, prevc = 0, itin = ()):

# consider next town to visit: all except the previous town

for nt in set(range(1, n + 1)) - {prevt}:

route = ts(prevt, nt) # smaller town number first

# can't have already used route; must change carrier; route exists

if route not in itin and prevc != rm[route] != 'X':

yield from tour(nt, rm[route], itin + (route,))

yield itin

# ---------------------------- Main Program ---------------------------- #

altrtd = {'R': set('BB'), 'B': set('GG'), 'G': set('RG')} # alt route dictionary

# consider number of towns , minimum = 4 (R + 2B + 2G routes = 5 routes)

for n in count(4):

sols = [] # store potential solutions

# town to town combinations

t2t = tuple(combinations(range(1, n + 1), 2))

# consider all possible town pair interconnections (less 1 for initial 'R')

for rc in product('BGRX', repeat = len(t2t) - 1):

# make a (dictionary) route map of all town pairs assigning a bus

# company (B, R, G) or none (X) to each pair of towns in the route map

rm = dict(zip(t2t, ('R',) + rc)) # initial 'R' to reduce exec time (~ /4)

# verify that the alternate route rules are respected

# count valid two-hop alternative routes from to

# via all other towns: via point; must equal 1

if (all(sum({rm[ts(sp, vp)], rm[ts(vp, fp)]} == altrtd[cmpy]

for vp in set(range(1, n + 1)) - {sp, fp}) == 1

for (sp, fp), cmpy in rm.items() if cmpy != 'X')):

sols += [rm]

if sols:

# find the route map with the least number of routes, i.e. most X's

rm = max(sols, key = lambda _ : tuple(_.values()).count('X'))

print(rm, '\n')

# travel around the network found that obeys all the Teaser rules

# following all itineraries using each town in turn as a start point

ity = max((iti for s in range(1, n + 1) for iti in tour(s)), key = len)

# For legibility, invert steps <s> that are 'backwards'

ityb = [ity[0][::-1] if ity[0][0] in ity[1] else ity[0]] # first step

ityb += [s[::-1] if s[1] in r else s for r, s in zip(ity, ity[1::])]

# print longest itinerary

print(''.join(str(a) + ' -> 'for (a, b) in ityb) + str(ity[-1][1]))

print(' ' + ' '.join(rm[yy] for yy in ity), '\n')

break

John Z permalink

Replacing ‘max’ in line 50 with ‘min’ gives exactly the same result indicating that the ‘fewest routes’ criterion is superfluous. About 4 extra lines of code were required to apply this criterion not a huge burden.

Reply

Sunday Times Teaser 3201 – Spare Routes

by Colin Vout

Published Friday January 26 2024 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta