Brain Teaser: Circular tour
From Sunday Times Brain Teasers 1974 [link]
Arley, Barley, Carley, Darley, Earley and Farley are six villages connected, in that order, by a circular bus service. A passenger is allowed to board at any village and alight at any other or complete the whole circuit. The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.
Arley to Barley is 1 mile. The distance from Farley to Arley is greater than that from Barley to Carley but less than that from Earley to Farley.
What is the distance from Earley to Farley?
This puzzle is taken from the book Sunday Times Brain Teasers (1974), but it is not a puzzle that originally appeared in The Sunday Times.
[teaser-book-1974-p95]
Frits, 
Ruud, 
Lise Andreasen, and 2 others are discussing. 
GeoffR and 
Mark Valentine, and 1 other are discussing. 
Hugh Casement and 
S2T2 
Jim Randell 11:20 am on 20 August 2024 Permalink |
We have encountered puzzles involving magic circles before (see: Teaser 1986, Enigma 985, Puzzle #171), and developed tools for generating them
This Python program considers magic circles of size 6, and then looks for ones that meet the specified requirements.
It runs in 75ms. (Internal runtime is 4.1ms).
Run: [ @replit ]
from magic_circles import magic_circle from enigma import printf # look for a size 6 magic circle (including reflections) for ds in magic_circle(6, refl=1): # distance AB = 1 assert ds[0] == 1 # distance EF > distance FA > distance BC if not (ds[4] > ds[5] > ds[1]): continue # output solution printf("distance EF = {ds[4]} [ds = {ds}]")Solution: The distance from Earley to Farley is 12 miles.
And we have the following distances around the circle:
LikeLike
Ruud 2:09 pm on 21 August 2024 Permalink |
A bit verbose and certainly very brute force:
import itertools ab = 1 for bc, cd, de, ef, fa in itertools.permutations(range(2, 20), 5): ac = ab + bc ad = ac + cd ae = ad + de af = ae + ef bd = bc + cd be = bd + de bf = be + ef ba = bf + fa ce = cd + de cf = ce + ef ca = cf + fa cb = ca + ab df = de + ef da = df + fa db = da + ab dc = db + bc ea = ef + fa eb = ea + ab ec = eb + bc ed = ec + cd fb = fa + ab fc = fb + bc fd = fc + cd fe = fd + de if ef > fa > bc and af+fa == 31: if {ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe} == set(range(1, 31)): print(ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe) print(ef)LikeLike
Lise Andreasen 10:27 pm on 20 August 2024 Permalink |
So… The bus travels 31 miles on 1 circuit. And there’s also 2 villages, 31 miles apart on the circuit. Is this the distance from a village to itself?
LikeLike
Jim Randell 8:14 am on 21 August 2024 Permalink |
That’s right. A complete circuit is 31 miles, but we can also travel all the distances between 1 and 30 miles.
LikeLike
Lise Andreasen 6:29 pm on 21 August 2024 Permalink |
Just an odd way to describe the 31 miles “distance”.
“The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.”
LikeLike
GeoffR 9:48 am on 21 August 2024 Permalink |
There are 6 single trips between villages and 6 trips for each of 2,3,4 and 5 bus stops between villages e.g. AB, BC, CD, DE, EF, FA for single stops between villages. There is only 1 circular bus trip visiting all 6 villages i.e. AB + BC + CD + DE + EF + FA.
In total, therefore, there are 5 X 6 + 1 = 31 total bus trips.
This MiniZinc solution enumerates all possible bus trips.
% A Solution in MiniZinc include "globals.mzn"; % Villages are A,B,C,D,E,F % Assumed upper bounds of six distances between villages var 1..15:AB; var 1..15:BC; var 1..15:CD; var 1..15:DE; var 1..15:EF; var 1..15:FA; constraint all_different ([AB, BC, CD, DE, EF, FA]); constraint FA > BC /\ FA < EF; constraint AB == 1; % There are 31 possible distances between villages, as shown below: var set of int: soln_nums == {AB, BC, CD, DE, EF, FA, % 1 stop AB+BC, BC+CD, CD+DE, DE+EF, EF+FA, FA+AB, % 2 stops AB+BC+CD, BC+CD+DE, CD+DE+EF, DE+EF+FA, EF+FA+AB, FA+AB+BC, % 3 stops AB+BC+CD+DE, BC+CD+DE+EF, CD+DE+EF+FA, DE+EF+FA+AB, EF+FA+AB+BC, FA+AB+BC+CD, % 4 stops AB+BC+CD+DE+EF, BC+CD+DE+EF+FA, CD+DE+EF+FA+AB, DE+EF+FA+AB+BC, % 5 stops EF+FA+AB+BC+CD, FA+AB+BC+CD+DE, AB+BC+CD+DE+EF+FA}; % 6 stops set of int: req_nums = 1..31; constraint soln_nums == req_nums; constraint card(soln_nums) == AB + BC + CD + DE + EF + FA; solve satisfy; output["[AB, BC, CD, DE, EF, FA] = " ++ show( [AB, BC, CD, DE, EF, FA] ) ++"\n" ++ "Distance from Earley to Farley = " ++ show(EF) ++ " miles."]; % [AB, BC, CD, DE, EF, FA] = [1, 2, 7, 4, 12, 5] % Distance from Earley to Farley = 12 miles. % ---------- % ==========LikeLike
Ruud 11:24 am on 22 August 2024 Permalink |
A bit less verbose:
import itertools succ = dict(zip("abcdef", "bcdefa")) for x5 in itertools.permutations(range(2, 20), 5): dist = dict(zip("ab bc cd de ef fa".split(), [1, *x5])) for d in "abcdef": d1 = succ[d] for _ in range(4): dist[d + succ[d1]] = dist[d + d1] + dist[d1 + succ[d1]] d1 = succ[d1] if dist["ef"] > dist["fa"] > dist["ac"] and set(dist.values()) == set(range(1, 31)): print(dist["ef"])LikeLike
Frits 4:10 pm on 22 August 2024 Permalink |
Using my Puzzle #171 code but now using decomposition.
from itertools import permutations # for a list with n numbers check if the set of sums of 1...n-1 adjacent items # (also circular) is complete (with n.(n-1) different sums) def allOccurOnce(s, ln): sms = set(s) for i in range(ln): for j in range(2, ln): if (sm := sum((s * 2)[i:i + j])) in sms: return False sms.add(sm) return True # decompose <t> into <k> increasing numbers from <ns> def decompose(t, k, ns, s=[]): if k == 1: if t in ns: yield s + [t] else: for i, n in enumerate(ns): # make sure we don't overshoot if 2 * t < (2 * n + k - 1) * k: break yield from decompose(t - n, k - 1, ns[i + 1:], s + [n]) N = 6 T = N**2 - N + 1 H = int(T // 2) # for a magic circle with N numbers and total sum T # the highest possible circle number is T - N(N-1)/2 which equals H + 1 # exclude mandatory numbers 1 and 2 from the decomposition for dc in decompose(T - 3, N - 2, range(3, H + 2)): # weave in the number 2 for p in permutations([2] + dc): p1 = (1, ) + p # distance EF > distance FA > distance BC if not (p1[4] > p1[5] > p1[1]): continue # can we make N.(N - 1) different sums? if not allOccurOnce(p1, N): continue print(f"answer: {p1[4]} miles")LikeLike