Teaser 3201: Spare routes
From The Sunday Times, 27th January 2024 [link] [link]
Three companies run scenic coach trips in both directions 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, e.g., R, B, G, B)?
[teaser3201]
Frits and 
GeoffR, and 
Brian Gladman, 
Guy, 
John Crabtree, and 1 other are discussing. 
NigelR and 
S2T2 
Jim Randell 8:51 pm on 26 January 2024 Permalink |
There is probably some (isomorphic) duplication in the minimal graphs found, and this is not an efficient approach for larger graphs (but fortunately the minimal graphs found are quite small).
Run: [ @replit ]
from enigma import (Accumulator, irange, inf, subsets, ordered, singleton, join, map2str, printf) # find routes between x and y via z def route(m, x, y, zs, ss): for z in zs: if z == x or z == y: continue if ordered(m.get(ordered(x, z), 'X'), m.get(ordered(y, z), 'X')) == ss: yield z # requirements: colour -> replacements reqs = { 'R': ('B', 'B'), # R can be replaced by B+B 'B': ('G', 'G'), # B can be replaced by G+G 'G': ('G', 'R'), # G can be replaced by G+R } # check the requirements on map <m> with nodes <ns> def check(m, ns): vs = set() for ((x, y), v) in m.items(): if v != 'X': vs.update((x, y)) ss = reqs.get(v) # look for unique replacement if ss and singleton(route(m, x, y, ns, ss)) is None: return False # check all nodes are non-trivial return vs.issuperset(ns) # find paths on map <m> without repeated edges, and different colours on adjacent edges # vs = visited vertices # ks = visited edges def paths(m, vs=list(), ks=list()): if ks and ks[0] < ks[-1]: yield (vs, ks) # can we extend the path? for (k, v) in m.items(): if v == 'X': continue if ks and (k in ks or v == m[ks[-1]]): continue if k[0] == vs[-1]: yield from paths(m, vs + [k[1]], ks + [k]) if k[1] == vs[-1]: yield from paths(m, vs + [k[0]], ks + [k]) # find minimal graphs (by (number of nodes, number of edges)) graphs = Accumulator(fn=min, collect=1) # consider increasing numbers of towns (at least 4) for n in irange(4, inf): # vertices (= towns) ns = list(irange(n)) # edges (= routes) rs = list(subsets(ns, size=2)) # assign colours to routes ('X' = no route) for ss in subsets("RBGX", size=len(rs) - 1, select='M', fn=list): # check minimum number of routes if ss.count('B') < 2: continue if ss.count('G') < 3: continue ss.insert(0, 'R') # make the map m = dict(zip(rs, ss)) # check requirements if check(m, ns): # record (number of nodes, number of edges) graphs.accumulate_data((n, len(ss) - ss.count('X')), m) if graphs.data: break # we only need the minimal number of vertices # collect answers ans = set() # process minimal graphs (n, e) = graphs.value ns = list(irange(n)) printf("minimal graph has {n} vertices, {e} edges") for m in graphs.data: printf("-> {m}", m=map2str(m)) # collect maximal paths on this map r = Accumulator(fn=max, collect=1) for v in ns: for (vs, ks) in paths(m, [v]): r.accumulate_data(len(ks), (vs, ks)) printf("max path len = {r.value}") # output paths for (vs, ks) in r.data: ss = join(m[k] for k in ks) printf("-> {vs} {ss}") ans.add(ss) printf() # output solution printf("tour = {t}", t=join(ans, sep=", "))Solution: The companies used are: G, B, R, B, R, B, G.
A minimal graph has 5 vertices and 9 edges:
The program finds 12 graphs in total, but they are all isomorphic to the one above.
We see that node 4 only has green edges (and all green edges lead to 4), so that can only act as the start/end of the path, and we can use a maximum of 7 of the 9 edges. Each path can be traversed in both directions, so there are essentially 3 different maximal paths that can be taken. And the fact that puzzle should have a unique solutions implies the answer should be palindromic (otherwise the reverse would also be a valid answer), even though the example given in the puzzle text is not.
LikeLiked by 1 person
Jim Randell 10:15 am on 27 January 2024 Permalink |
I augmented my code to detect isomorphic graphs [@replit], and there is essentially only one viable minimal layout.
from enigma import (Accumulator, irange, inf, subsets, ordered, singleton, join, map2str, printf) # find routes between x and y via z def route(m, x, y, zs, ss): for z in zs: if z == x or z == y: continue if ordered(m.get(ordered(x, z), 'X'), m.get(ordered(y, z), 'X')) == ss: yield z # requirements: colour -> replacements reqs = { 'R': ('B', 'B'), # R can be replaced by B+B 'B': ('G', 'G'), # B can be replaced by G+G 'G': ('G', 'R'), # G can be replaced by G+R } # check the requirements on map <m> with nodes <ns> def check(m, ns): vs = set() for ((x, y), v) in m.items(): if v != 'X': vs.update((x, y)) ss = reqs.get(v) # look for unique replacement if ss and singleton(route(m, x, y, ns, ss)) is None: return False # check all nodes are non-trivial return vs.issuperset(ns) # find paths on map <m> without repeated edges, and different colours on adjacent edges # vs = visited vertices # ks = visited edges def paths(m, vs=list(), ks=list()): if ks and ks[0] < ks[-1]: yield (vs, ks) # can we extend the path? for (k, v) in m.items(): if v == 'X': continue if ks and (k in ks or v == m[ks[-1]]): continue if k[0] == vs[-1]: yield from paths(m, vs + [k[1]], ks + [k]) if k[1] == vs[-1]: yield from paths(m, vs + [k[0]], ks + [k]) # check 2 graphs for isomorphism def is_isomorphic(vs, m1, m2): # choose a mapping of vs for ss in subsets(vs, size=len, select='P'): # remap m1 m3 = dict((ordered(ss[x], ss[y]), v) for ((x, y), v) in m1.items()) if m3 == m2: return True return False # find minimal graphs graphs = Accumulator(fn=min, collect=1) # consider increasing numbers of towns (at least 4) for n in irange(4, inf): # vertices (= towns) ns = list(irange(n)) # edges (= routes) rs = list(subsets(ns, size=2)) # assign colours to routes ('X' = no route) for ss in subsets("RBGX", size=len(rs) - 1, select='M', fn=list): # check minimum number of routes (nR, nB, nG) = (ss.count('R') + 1, ss.count('B'), ss.count('G')) if nB < 2 or nG < 3 or nB < nR or nG < nB: continue ss.insert(0, 'R') # make the map m = dict(zip(rs, ss)) # check requirements if check(m, ns): # record (number of nodes, number of edges) graphs.accumulate_data((n, len(ss) - ss.count('X')), m) if graphs.data: break # we only need the minimal number of vertices # collect answers ans = set() morphs = list() # process minimal graphs (n, e) = graphs.value ns = list(irange(n)) printf("minimal graph has {n} vertices, {e} edges") for m in graphs.data: printf("-> {m}", m=map2str(m)) # check morphs if any(is_isomorphic(ns, m, m1) for (j, m1) in enumerate(morphs)): continue printf("= isomorph {n}", n=len(morphs)) morphs.append(m) # collect maximal paths on this map r = Accumulator(fn=max, collect=1) for v in ns: for (vs, ks) in paths(m, [v]): r.accumulate_data(len(ks), (vs, ks)) printf("max path len = {r.value}") # output paths for (vs, ks) in r.data: ss = join(m[k] for k in ks) printf("-> {vs} {ss}") ans.add(ss) printf() # output solution printf("tour = {t}", t=join(ans, sep=", "))LikeLike
Frits 7:42 am on 27 January 2024 Permalink |
Similar, the tour also finishes where it started.
The generated routes and/or tours may contain duplicates.
from itertools import product # is route <k> doable by a unique combination via two routes of types <tps> def check_alt(m, n, k, tps): rem_towns = [i for i in range(n) if i not in k] alt = [a for a in rem_towns if {m[tuple(sorted([a, x]))] for x in k} == tps] return len(alt) == 1 def check(m, n): d = dict(zip(["R", "B", "G"], [{"B"}, {"G"}, {"R", "G"}])) # check for unique alternative combinations for k, v in m.items(): if v in "RBG": if not check_alt(m, n, k, d[v]): return False return True # generate routes that meet the requirements def gen_routes(n): # routes rs = [(i, j) for i in range(n - 1) for j in range(i + 1, n)] # assign company to a route (or not), (blank = no route) for cs in product("RBG ", repeat = n * (n - 1) // 2 - 1): cs = ("R", ) + cs # R < B < G if (cntR := cs.count('R')) >= (cntB := cs.count('B')): continue if cntB >= (cntR := cs.count('G')): continue # check requirements if check(d := dict(zip(rs, cs)), n): yield d # add route to tour def add_route(m, ss=[]): if not ss: # start for k, v in m.items(): yield from add_route(m, ss + [(k, v)]) else: yield ss # find a new unused route for a different company from the last rt, tp = ss[-1] for k, v in m.items(): if v == tp: continue # already added? if (k, v) in ss or (k[::-1], v) in ss: continue if k[0] == rt[1]: yield from add_route(m, ss + [(k, v)]) if k[1] == rt[1]: yield from add_route(m, ss + [(k[::-1], v)]) n = 4 # we need at least 6 routes (1 R, 2 B, 3 G) # increase number of towns until all alternative routes can be made while True: sols = set() mx = 0 # generate valid routes for r in gen_routes(n): # find longest tour mx = 0 for tour in add_route({k: v for k, v in r.items() if v in "RGB"}): lt = len(tour) if lt >= mx: if lt > mx: sols = set() mx = lt # finish where we have started (is this a feature of a tour?) if tour[0][0][0] != tour[-1][0][1]: continue sols.add(''.join(t for _, t in tour)) if mx: print(f"answer: {' or '.join(sols)}") break else: n += 1LikeLike
Jim Randell 11:35 am on 31 January 2024 Permalink |
@Frits: I don’t think it is required for the tour to start and finish at the same town. (Certainly this is not explicitly stated).
Also, how does your program ensure that the condition “this wouldn’t be possible with … fewer routes” is met?
LikeLike
Frits 3:55 am on 1 February 2024 Permalink |
Without demanding for cyclic tours and with minimal routes.
Program is also running a little bit faster (due to the extra “cntR” condition).
from itertools import product # is route <k> feasible by a unique combination via two routes of types <tps> def check_alt(m, n, k, tps): alt = [a for a in [i for i in range(n) if i not in k] if {m[(a, x) if a < x else (x, a)] for x in k} == tps] return len(alt) == 1 # perform checks for all routes def check(m, n): d = dict(zip(["R", "B", "G"], [{"B", "B"}, {"G", "G"}, {"R", "G"}])) # check for unique alternative combinations for r, c in m.items(): if c in "RBG": if not check_alt(m, n, r, d[c]): return False return True # generate routes that meet the requirements def gen_routes(n): # routes rs = [(i, j) for i in range(n - 1) for j in range(i + 1, n)] # assign company to a route (or not), (blank = no route) for cs in product("RBG ", repeat = n * (n - 1) // 2 - 1): cs = ("R", ) + cs # nR < nB < nG # 3 * r + 3 <= n * (n - 1) // 2 if not ((cntR := cs.count('R')) <= (n * (n - 1) - 6) // 6): continue if not (cntR < cs.count('B') < cs.count('G')): continue # check requirements if check(d := dict(zip(rs, cs)), n): yield d # generate all valid tours (credit: John Z) def tours(m, prevt, prevc="x", rts = []): # consider next town to visit for nt in set(range(n)) - {prevt}: route = (prevt, nt) if prevt < nt else (nt, prevt) if route not in rts and m[route] not in {" ", prevc}: yield from tours(m, nt, m[route], rts + [route]) # any route is linked to 2 other routes if len(rts) > 2: yield ''.join(m[x] for x in rts) n = 4 # we need at least 6 routes (1 R, 2 B, 3 G) # increase number of towns until all alternative routes can be made while True: mrts = dict() # generate valid routes and calculate number of blank routes for r in gen_routes(n): mrts[brts] = mrts.get(brts := list(r.values()).count(" "), []) + [r] if mrts: trs = set() # get minimimal routes by maximising the number of blank routes for r in mrts[max(mrts.keys())]: # find all valid tours trs |= set(tr for twn in range(n) for tr in tours(r, twn)) print("answer:", ' or '.join([tr for tr in trs if len(tr) == len(max(trs, key=len))])) break else: n += 1LikeLike