Teaser 3290: Omnibus additions
From The Sunday Times, 12th October 2025 [link] [link]
In our town centre the scheduled times taken for stages between bus stops are 5, 8 or 9 minutes. The only possible stages (in either direction) are between the following stops:
Market and Castle;
Market and Park;
Market and Hospital;
Station and Castle;
Station and University;
Castle and Park;
University and Park;
Park and Hospital.There are the following routes (with total time given):
Route 1: from Market to Castle; 5 stages; 29 minutes.
Route 2: from University to Market; 19 minutes.
Route 3: from University to Hospital; 4 stages; 31 minutes.
Route 4: from University to Station; 27 minutes.
Route 5: from Market to University; 4 stages; 24 minutes.No route visits a stop more than once.
What are the stage times (in order) for Route 1, and Route 4?
[teaser3290]
Frits, 
Ruud, and 
Alex.T.Sutherland, 
GeoffR and 
Alex T Sutherland, 
S2T2 
Jim Randell 7:49 am on 12 October 2025 Permalink |
The lengths of routes 2 and 4 are not given, but their times are, and there are only certain combinations of 5, 8, 9 minutes that allow a given time to be achieved.
This Python 3 program runs in 72ms. (Internal runtime is 1.5ms).
from enigma import (express, cproduct, update, unpack, printf) # adjacent stops adj = dict(C="MPS", H="MP", M="CHP", P="CHMU", S="CU", U="PS") # possible stage times stages = [5, 8, 9] # find a n-length path from src to tgt def path(n, src, tgt, vs=list()): # are we done if n == 1: if tgt in adj[src]: yield vs + [src + tgt] elif n > 1: # move from src (but not directly to tgt) for v in adj[src]: if v != tgt and not any(v in p for p in vs): yield from path(n - 1, v, tgt, vs + [src + v]) key = unpack(lambda x, y: (x + y if x < y else y + x)) # allocate times for each stage to sum to t def times(t, vs, d): # are we done? if not vs: if t == 0: yield d else: # next stage k = key(vs[0]) x = d.get(k) # is the time already chosen? if x is not None: if not (x > t): yield from times(t - x, vs[1:], d) else: # choose a time for this stage for x in stages: if not (x > t): yield from times(t - x, vs[1:], update(d, [(k, x)])) # solve a set of routes def solve(ks, rs, ns, ts, d=dict(), ps=dict()): # are we done? if not ks: yield (d, ps) else: # choose a remaining route k = ks[0] # find a path ((src, tgt), n) = (rs[k], ns[k]) for vs in path(n, src, tgt): # allocate times for d_ in times(ts[k], vs, d): yield from solve(ks[1:], rs, ns, ts, d_, update(ps, [(k, vs)])) # keys; routes; lengths; times ks = [1, 2, 3, 4, 5] rs = { 1: "MC", 2: "UM", 3: "UH", 4: "US", 5: "MU" } ns = { 1: 5, 3: 4, 5: 4 } # lengths for routes 2 and 4 are not given ts = { 1: 29, 2: 19, 3: 31, 4: 27, 5: 24 } # possible missing lengths (routes 2 and 4) (n2s, n4s) = (set(sum(qs) for qs in express(ts[k], stages)) for k in [2, 4]) # choose lengths for routes 2 and 4 for (n2, n4) in cproduct([n2s, n4s]): ns_ = update(ns, [(2, n2), (4, n4)]) for (d, ps) in solve(ks, rs, ns_, ts): # output routes for k in ks: printf("Route {k}: {n} stages; {t} min", n=ns_[k], t=ts[k]) for (src, tgt) in ps[k]: printf(" {src} -> {tgt} [{x} min]", x=d[key((src, tgt))]) printf()Solution: Stage times (in minutes) are: Route 1 = (5, 5, 9, 5, 5); Route 4 = (9, 5, 8, 5).
The complete solution is:
LikeLike
Frits 1:45 pm on 12 October 2025 Permalink |
from math import ceil from itertools import product, permutations # sorted tuple stup = lambda tup: tup if tup[0] < tup[1] else tup[::-1] # make total <t> with <k> elements taken from <m> numbers in list <ns> def decompose_(rest, m, t, k, ns, ss=[]): if m == 2: # example: # 5.A + 8.B + 9.C = t and A + B + C = k with t=29 and k=5 # (8 - 5).B + (9 - 5).C = t - 5.k ssrev = ss[::-1] # calculate 2nd quantity q2, r = divmod(t - ns[0] * k - sum([(x - ns[0]) * y for x, y in zip(ns[2:], ssrev)]), ns[1] - ns[0]) if not r and q2 >= 0: if (q1 := k - q2 - sum(ss)) >= 0: yield [a for g in [y * [x] for x, y in zip(ns, [q1, q2] + ssrev)] for a in g] else: n = ns[m - 1] for amt in range(min(n, k - sum(ss), rest // n) + 1): yield from decompose_(rest - amt * n, m - 1, t, k, ns, ss + [amt]) # make total <t> with <k> numbers from list <ns> def decompose(t, k, ns): yield from decompose_(t, len(ns), t, k, ns) # get path from <fr> to <to> in <k> steps visiting different towns def path(fr, to, k, ss=[]): if k == 0: if ss[-1] == to: yield ss else: for town in d[fr]: if town not in ss: yield from path(town, to, k - 1, ss + [town]) # solve route <n>, not contradicting settings in dictionary <d> def solve(n, d=dict(), ss=[]): if n < 0: yield ss[::-1] else: (fr, to), dur = routes[n], duration[n] rng = ([n_stops[n]] if n_stops[n] else range(ceil(dur / times[-1]), dur // times[0] + 1)) # make the route in <k> stages for k in rng: # combine possible times with possible paths for ts, ps in product(decompose(duration[n], k, times), path(fr, to, k, [fr])): # permutations of times for ts in set(permutations(ts)): # assign times <ts> to paths in <ps> d_ = dict(s := tuple(zip([stup(x) for x in zip(ps, ps[1:])], ts))) # is path, time already in dictionary? if all((k_ not in d or d[k_] == v_) for k_, v_ in d_.items()): yield from solve(n - 1, d | d_, ss + [s]) times = [5, 8, 9] stages = "MC MP MH SC SU CP UP PH".split() towns = {y for x in stages for y in x} routes = "MC UM UH US MU".split() n_stops = [5, 0, 4, 0, 4] duration = [29, 19, 31, 27, 24] # dictionary of visitable towns d = {t: [s[1 - s.index(t)] for s in stages if t in s] for t in towns} # solve all 5 routes for s in solve(len(routes) - 1): print("answer:", [y for x, y in s[0]], "and", [y for x, y in s[3]])LikeLike
Frits 4:25 am on 13 October 2025 Permalink |
We probably should assume that the scheduled time from A to B is the same as the scheduled time from B to A. This is not always true for towns in the mountains/hilly terrain.
LikeLike
Jim Randell 8:39 am on 13 October 2025 Permalink |
@Frits: Yes. I think we need to assume the times are the same in both directions to get a single solution.
I think changing the [[
key]] function in my code to just return [[x + y]] shows this.LikeLike
Ruud 3:12 pm on 13 October 2025 Permalink |
Brute force, but still instantaneous:
import peek import collections import itertools def route(stop0, stop1, nstops, called=None): if called is None: called = [stop0] if nstops in (0, -1): if called and called[-1] == stop1: yield called else: if nstops == 0: return for stop in next_stop[stop0]: if stop not in called: yield from route(stop, stop1, (-1 if nstops == -1 else nstops - 1), called + [stop]) stages = "mc mp mh sc su cp up ph".split() next_stop = collections.defaultdict(list) for stage in stages: stop0, stop1 = tuple(stage) next_stop[stop0].append(stop1) next_stop[stop1].append(stop0) routes = {1: list(route("m", "c", 5)), 2: list(route("u", "m", -1)), 3: list(route("u", "h", 4)), 4: list(route("u", "s", -1)), 5: list(route("m", "u", 4))} route_durations = {1: 29, 2: 19, 3: 31, 4: 27, 5: 24} for x in itertools.product((5,8,9), repeat=len(stages)): stage_duration = dict(zip(stages, x)) found_route = {} for i in range(1, 6): for route in routes[i]: if sum(stage_duration.get(stop0 + stop1, 0) + stage_duration.get(stop1 + stop0, 0) for stop0, stop1 in zip(route, route[1:])) == route_durations[i]: found_route[i] = route if len(found_route) == 5: peek(found_route)LikeLike
Frits 1:31 pm on 15 October 2025 Permalink |
Hi Ruud,
You don’t answer the question but that is an easy fix.
The program is even more instantaneous with the following line after line 38:
LikeLike
Frits 5:22 am on 16 October 2025 Permalink |
Only permuting times for unknown stages.
from math import ceil from itertools import product, permutations # sorted key of a stage key = lambda tup: tup[0] + tup[1] if tup[0] < tup[1] else tup[1] + tup[0] # t_ and k_ are being decremented, t and k remain the same def decompose_(t_, k_, t, k, ns, ns_0, ss=[]): if k_ == 2: # example: # 5.A + 8.B + 9.C = t and A + B + C = k with t=29 and k=5 # (8 - 5).B = t - 5.k - (9 - 5).C # calculate 2nd quantity q2, r = divmod(t - ns[0] * k - sum([x * y for x, y in zip(ns_0, ss)]), ns[1] - ns[0]) if not r and q2 >= 0: # calculate 1st quantity if (q1 := k - q2 - sum(ss)) >= 0: yield tuple(a for g in [y * [x] for x, y in zip(ns, [q1, q2] + ss)] for a in g) else: n = ns[k_ - 1] for x in range(min(n, k - sum(ss), t_ // n) + 1): yield from decompose_(t_ - x * n, k_ - 1, t, k, ns, ns_0, [x] + ss) # make total <t> with <k> numbers from list <ns> def decompose(t, k, ns): ns_0 = [x - ns[0] for x in ns[2:]] yield from decompose_(t, len(ns), t, k, ns, ns_0) # get paths from <fr> to <to> in <k> steps visiting different stops def paths(fr, to, k, ss): if k == 1: if to in d[fr]: ss = ss[1:] + [to] yield tuple(key(x) for x in zip(ss, ss[1:])) else: for stop in d[fr]: if stop not in ss: yield from paths(stop, to, k - 1, ss + [stop]) # remove elements of 2nd list from 1st list def list_diff(li1, li2): for x in li2: if x in li1: li1.remove(x) # solve route <n>, not contradicting settings in dictionary <d> def solve(n, d=dict(), ss=[]): if n < 0: yield ss[::-1] else: (fr, to), dur = routes[n], duration[n] rng = ([n_stops[n]] if n_stops[n] else range(ceil(dur / times[-1]), dur // times[0] + 1)) # make the route in <k> stages for k in rng: # combine possible times with possible paths for ts, pth in product(decompose(duration[n], k, times), paths(fr, to, k, [to, fr])): # determine times not yet used for this path (new_ts is updated) list_diff(new_ts := list(ts), pth_ := [d[x] for x in pth if x in d]) if new_ts == []: yield from solve(n - 1, d, ss + [tuple((k, v) for k, v in d.items() if k in pth)]) else: # number of new times must equal number of new stages if len(new_ts) != k - len(pth_): continue # permutations of new times for new_ts in set(permutations(new_ts)): d_, ts_ = dict(), [] for st in pth: if st in d: ts_.append(d[st]) else: # assign new time to stage <st> d_[st] = new_ts[0] ts_.append(new_ts[0]) new_ts = new_ts[1:] yield from solve(n - 1, d | d_, ss + [tuple(zip(pth, ts_))]) times = [5, 8, 9] stages = "MC MP MH SC SU CP UP PH".split() stops = {y for x in stages for y in x} routes = "MC UM UH US MU".split() n_stops = [5, 0, 4, 0, 4] duration = [29, 19, 31, 27, 24] # dictionary of visitable stops d = {stp: {s[1 - s.index(stp)] for s in stages if stp in s} for stp in stops} # solve all 5 routes for s in solve(len(routes) - 1): print("answer:", [y for x, y in s[0]], "and", [y for x, y in s[3]])LikeLike