Brain-Teaser 380: [Feeler gauges]
From The Sunday Times, 18th August 1968 [link]
“Feeler gauges”, says Bell at the pub, “are remarkably interesting things. You’ve all seen garage men use them — fingers of steel fastened together at one end and you can fan them out if you want. When you measure a space you find out which lot of fingers fits in. The thicknesses are marked in thous, that’s thousandths of an inch”.
“I’ve got a set of five gauges here which will measure any number up to 13 thous, always using either a single gauge or a touching set of them. You don’t need to use gauges which aren’t touching for a measurement like you do with the usual gauges. So mine’s better. I might patent it and make a packet”.
Clark examined it for few minutes and said “Not bad at all. I notice you could add an extra gauge in front and then your set would give all measurements up to 18 thous”.
How would the six gauges then read starting at the top?
This puzzle was originally published with no title.
[teaser380]
Frits are discussing. 
John Crabtree and 
Hugh Casement and 
S2T2 
Jim Randell 9:08 am on 15 April 2025 Permalink |
See also: Teaser 119, Teaser 560, Teaser 777, BrainTwister #61.
I reused the code to generate sparse rulers that I wrote for Teaser 119.
This Python 3 program runs in 81ms. (Internal runtime is 4.1ms).
from enigma import (irange, diff, append, tuples, csum, subsets, printf) # generate sparse rulers # L = length # M = number of marks # ms = existing marks (set) # k = number of remaining marks # xs = distances not yet satisfied (ordered list) # zl = left zone # zr = right zone def rulers(L, M, ms, k, xs, zl, zr): if k == 0: if not xs: yield sorted(ms) else: # perform some early termination checks: # are there too many unsatisfied differences remaining? if xs and len(xs) > (k * (k - 1)) // 2 + k * (M - k): return # is max distance too big? if xs and xs[-1] > max(zr, L - zl): return # can we fit k marks in the gaps? if zr - zl + 1 < k: return # extend left zone? if not (zl > L - zr): # try with mark at zl ds = set(abs(m - zl) for m in ms) yield from rulers(L, M, append(ms, zl), k - 1, diff(xs, ds), zl + 1, zr) # try without mark at zl yield from rulers(L, M, ms, k, xs, zl + 1, zr) else: # try without mark at zr yield from rulers(L, M, ms, k, xs, zl, zr - 1) # try with mark at zr ds = set(abs(m - zr) for m in ms) yield from rulers(L, M, append(ms, zr), k - 1, diff(xs, ds), zl, zr - 1) # generate rulers that can measure 1..N sparse_rulers = lambda L, M, N: rulers(L, M, {0, L}, M - 2, diff(irange(1, N), [L]), 1, L - 1) # consider possible sparse rulers with length L, to measure 1 - 13 for L in irange(13, 19): for ss in sparse_rulers(L, 6, 13): # calculate gauge thicknesses ts = list(b - a for (a, b) in tuples(ss, 2)) # look for an additional gauge to make all thicknesses up to 18 for x in irange(max(18 - L, 1), 17): ts_ = [x] + ts # calculate all measures ms_ = set(y - x for (x, y) in subsets(csum(ts_, empty=1), size=2)) if ms_.issuperset(irange(1, 18)): # output solution printf("[1..13] = {ts} -> [1..18] = {ts_}")Solution: The six gauges are: 14, 1, 3, 6, 2, 5.
Gauges [1, 3, 6, 2, 5] can be use to measure 1..13 (as well as 16, 17). It corresponds to a sparse ruler of length 17 with 6 marks.
Adding a gauge of 14 we get the set [14, 1, 3, 6, 2, 5], which can measure 1..18 (as well as 24, 26, 31). Which corresponds to a sparse ruler of length 31 with 7 marks.
Each of the gauges in the original 5-set has a different thickness, and there is another 5-set that would also work:
[1, 7, 3, 2, 4], which can measure 1..13 (as well as 16, 17).
But it cannot be extended to a 6-set that measures 1..18.
LikeLike
Frits 12:19 pm on 17 April 2025 Permalink |
@Jim, you are allowing negative gauges in line 48.
LikeLike
Jim Randell 2:39 pm on 17 April 2025 Permalink |
@Frits: Thanks. Fixed now.
LikeLike
Frits 12:08 pm on 17 April 2025 Permalink |
Assuming that the first five gauges are single digit.
Instead of “SubstitutedExpression” also “decompose” could have been used to find five numbers that add up to “L”.
from enigma import SubstitutedExpression from itertools import combinations, accumulate # can we make numbers 1 - <n> with sequence <s> using "touching" sets def check(s, n): # calculate all measures s_ = set(y - x for (x, y) in combinations(accumulate([0] + s), 2)) return s_.issuperset(range(1, n + 1)) # the alphametic puzzle p = SubstitutedExpression( [ # we have to make numbers 1 - 13 with a touching set of gauges A, B, C, D, E "A + B + C + D < 19", "12 < A + B + C + D + E < 20", # Jim: 13 <= L <= 19 "check([A, B, C, D, E], 13)", # we have to make numbers 1 - 18 with a touching set of gauges XY, A, B, C, D, E "XY < 18", # Jim: 18 - L <= XY <= 17 "check([XY, A, B, C, D, E], 18)" ], answer="[XY, A, B, C, D, E]", d2i=dict([(0, "ABCDE")] + [(k, "X") for k in range(2, 10)]), distinct="", env=dict(check=check), reorder=0, verbose=0, # use 256 to see the generated code ) # print answers for ans in p.answers(): print(f"{ans}")LikeLike
Frits 12:41 pm on 17 April 2025 Permalink |
The decomposition version (without assuming single digits).
from itertools import combinations, accumulate # can we make numbers 1 - <n> with sequence <s> using "touching" sets def check(s, n): # calculate all measures s_ = set(y - x for (x, y) in combinations(accumulate([0] + s), 2)) return s_.issuperset(range(1, n + 1)) # decompose <t> into <k> numbers from <ns> so that sum(numbers) equals <t> def decompose(t, k, ns, s=[]): if k == 1: if t in ns: yield s + [t] else: for n in ns: # <ns> must be a sorted list if n > t - (k - 1) * ns[0]: break yield from decompose(t - n, k - 1, ns, s + [n]) # consider possible sparse rulers with length L, to measure 1 - 13 for L in range(13, 20): # find five numbers that up to <L> for s in decompose(L, 5, range(1, L - 3)): # can we make numbers 1 - 13 with sequence <s> using "touching" sets if not check(s, 13): continue # look for an additional gauge to make all thicknesses up to 18 for x in range(max(1, 18 - L), 18): # can we make numbers 1 - 18 using "touching" sets if not check([x] + s, 18): continue # output solution print(f"[1..13] = {s} -> [1..18] = {[x] + s}")LikeLike