Teaser 3161: Going through the hoops
From The Sunday Times, 23rd April 2023 [link] [link]
I arrived very late to watch the croquet game. Someone had listed the times when the four balls (blue, black, red and yellow) had run through hoops 1 to 12; none had yet hit the central peg to finish. Blue had run each hoop earlier than black, and every hoop had been run by colours in a different order. The only change in running order from one hoop to the next-numbered hoop was that two colours swapped positions. These swapping pairs (to obtain the order for the next-numbered hoop) were in non-adjacent positions for hoops 5 and 10, but no others. For one particular colour, all the hoops where it passed through earlier than the yellow were before all those where it passed through later than the yellow.
In what order had the balls run the twelfth hoop?
[teaser3161]
Frits and 
GeoffR, and 
Hugo, and 
Brian Gladman are discussing. 
S2T2 
Jim Randell 4:44 pm on 21 April 2023 Permalink |
This Python program runs in 60ms. (Internal runtime is 4.9ms).
Run: [ @replit ]
from enigma import (subsets, update, join, filter2, irange, printf) # the colours (K = black) colours = "BKRY" # x before y before = lambda s, x, y: s.index(x) < s.index(y) # is there a colour where all "before yellow" < all "after yellow" def check(ss, n): for k in colours: if k == "Y": continue (bY, aY) = filter2((lambda i: before(ss[i], k, 'Y')), irange(n)) if bY[-1] < aY[0]: return True return False # solve the puzzle def solve(ss): n = len(ss) # are we done? if n == 12: if check(ss, n): yield ss else: # choose 2 indices to swap s = ss[-1] for ((i, x), (j, y)) in subsets(enumerate(s), size=2): if (j == i + 1) == (n in {5, 10}): continue s_ = update(s, [(i, y), (j, x)]) # blue before black, and no repeats if before(s_, 'B', 'K') and s_ not in ss: # move on to the next hoop yield from solve(ss + [s_]) # choose an order for the first hoop, with blue before black for s in subsets(colours, size=len, select='P', fn=join): if not before(s, 'B', 'K'): continue # solve for the remaining hoops for ss in solve([s]): # output solution printf("hoop 12 = {s12} [{ss}]", s12=ss[-1], ss=join(ss, sep=" "))Or [here] is a (longer) version that verifies the “yellow” condition as it goes along (instead of just checking it at the end).
Solution: The order for the 12th hoop was: Red, Yellow, Blue, Black.
The full list of orders is (B = Blue, K = Black, R = Red, Y = Yellow):
And we see the non-adjacent swaps are between hoops 5 & 6 and 10 & 11.
LikeLike
Frits 11:44 pm on 21 April 2023 Permalink |
Without recursion.
from itertools import permutations, product from collections import defaultdict # the colours (K = black) colours = "BKRY" # possible running orders (blue before black) ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1)) adj_moves = defaultdict(list) nonadj_moves = defaultdict(list) # determine all possible next running orders for a specific running order for (x, y) in product(ps, repeat=2): if x == y: continue swaps = [i for i, (a, b) in enumerate(zip(x, y)) if a != b] # only one swap took place ... if len(swaps) != 2: continue # .. and store for adjacent fields and non-adjacent fields (adj_moves if abs(swaps[0] - swaps[1]) == 1 else nonadj_moves)[x].append(y) # first hoop ss = [(x, ) for x in ps] # process remaining hoops after first hoop for n in range(1, 12): ss_ = [] for s in ss: # determine next running order for ro in (adj_moves if n not in {5, 10} else nonadj_moves)[s[-1]]: if ro not in s: ss_.append(s + (ro, )) ss = ss_ # is there a colour where all "before yellow" < all "after yellow" for s in ss: for k in range(3): # make string with only digits 3 and k # (like k3-k3-3k-3k-3k-3k-k3-k3-3k-3k-3k-3k) s_3k = '-'.join([''.join(str(x) for x in y if x in {k, 3}) for y in s]) f_3k = s_3k.index('3' + str(k)) # first 3k string if f_3k == 0: continue # all k3 strings must occur before first 3k string if s_3k[f_3k + 3:].find(str(k) + '3') >= 0: continue print("answer:", ''.join(colours[x] for x in s[-1])) breakLikeLike
Frits 4:21 pm on 25 April 2023 Permalink |
John Crabtree said that it was not hard to determine the “particular colour”.
The following code will reject two out of three colours.
from itertools import permutations # the colours (K = black) colours = "BKRY" # possible running orders (blue before black) ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1)) # return possible outcomes after a non-adjacent swap def n_adj(s): return set(((s[2], s[1], s[0], s[3]), (s[3], s[1], s[2], s[0]), (s[0], s[3], s[2], s[1]))) particular_colours = [] for k in range(3): a, b = [], [] # after/before for p in ps: (b if p.index(k) < p.index(3) else a).append(p) # the "after" group has at least 3 elements # with at least one non-adjacent move if all(n_adj(e).isdisjoint(a) for e in a): continue particular_colours.append(colours[k]) print("possible particular colours:", particular_colours)LikeLike