Teaser 3144: Beware the jabbers’ clock, my son!
From The Sunday Times, 25th December 2022 [link]
On the NHS vaccine booking website, my queue position updated every minute. My initial position was an odd value in the 9000s. This value had four different digits, and its leftmost digit and just two others in it were factors of it. Curiously, these properties applied to each of the decreasing four-figure values after the next eight updates. I also noticed that no value had a digit in common with its predecessor, no zeroes occurred before the fourth update and no nines after this.
My son, told just the above, found all the possible values from which a complete set could be selected. From these he was certain of more than one of the nine queue positions.
Give these certain positions in displayed order.
This completes the archive of puzzles from 2022.
[teaser3144]
Hugh Casement, 
Frits are discussing. 
NigelR, 
GeoffR, 
Tony Brooke-Taylor, 
Geoff, 
Robert Brown, and 1 other are discussing. 
S2T2 
Jim Randell 5:14 pm on 23 December 2022 Permalink |
I took “no zeroes occurred before the fourth update …” to mean there are no zeros in the first 4 numbers in the sequence (but it doesn’t imply that there necessarily is a zero digit in the 5th number in the sequence). And “… no nines after this” to mean that there are no nines in last 5 numbers of the sequence (and again, not implying that there is a 9 digit in 4th number in the sequence). Although I think that you can use a slightly different interpretation of these conditions and still come up with the same answer.
This Python program runs in 307ms.
Run: [ @replit ]
from enigma import (irange, subsets, nconcat, intersect, printf) # does <x> divide <n>? divides = lambda n, x: x != 0 and n % x == 0 # generate candidate numbers def generate(): for (A, B, C, D) in subsets(irange(0, 9), size=4, select="P"): if A == 0: continue n = nconcat(A, B, C, D) # n is divisible by A and exactly 2 of B, C, D if divides(n, A) and sum(divides(n, d) for d in (B, C, D)) == 2: yield (A, B, C, D) # find viable sequences from <ns> def solve(ns, ss=[]): k = len(ss) # are we done? if k == 9: yield ss else: # choose the next number for (i, n) in enumerate(ns, start=1): # there are no 0s before the 4th update if k < 4 and 0 in n: continue # there are no 9s after the 3rd update if k > 3 and 9 in n: continue if k == 0: # the first number is odd, and starts with 9 if n[0] < 9: break if n[-1] % 2 != 1: continue else: # subsequent numbers # have no digits in common with the previous number if len(set(n + ss[-1])) != 8: continue # looks good yield from solve(ns[i:], ss + [n]) # collect candidate numbers in decreasing order ns = list(generate()) ns.reverse() # what numbers occur in all possible sequences? ss = list(nconcat(x) for x in intersect(solve(ns))) # output solution printf("{ss}", ss=sorted(ss, reverse=1))Solution: The positions that are certain are: 7315 and 4728.
7315 must occur as the 3rd value in the sequence, and 4728 must occur as the 6th value in the sequence.
There are 5 positions where only one set of digits can occur. But for some of these it is possible to construct more than one valid number from the digits:
Only 7315 and 4728 are unique in their respective positions.
In total there are 8832 possible sequences of 9 numbers.
LikeLike
Jim Randell 7:38 am on 24 December 2022 Permalink |
With a little analysis we can get a much faster run time (and the program is only a little longer).
First we note that the numbers must be of the form:
And as long as there is valid number that can be constructed using the non-leading digits we don’t really care what order they appear in when we look for the next number. So we can just consider the collection of digits.
Also, as successive numbers share no digits, as we construct numbers we can exclude the leading digit of the next number (as we already know what it will be).
Then at the end we take the collections of digits we have found that we know must appear in each position, we can look for those that give just one valid number, and we have found an answer.
This Python program runs in 56ms. (Internal run time is 963µs).
Run: [ @replit ]
from enigma import (irange, subsets, nconcat, diff, intersect, singleton, printf) # does <x> divide <n>? divides = lambda n, x: x != 0 and n % x == 0 digits = list(irange(0, 9)) # is the number formed from (A, B, C, D) valid? def valid(A, B, C, D): n = nconcat(A, B, C, D) if A == 9 and n % 2 != 1: return if divides(n, A) and sum(divides(n, x) for x in (B, C, D)) == 2: return n # generate candidate digit sets # return digits (A, B, C, D) - A is leading digit; B, C, D are ordered def candidates(A, ds): # choose the three final digits for xs in subsets(ds, size=3): # can we find a valid number? if any(valid(A, B, C, D) for (B, C, D) in subsets(xs, size=len, select="P")): yield (A,) + xs # k = leading digit def solve(k, ss=[]): # are we done? if k == 0: yield ss else: if k == 9: # the first number is odd, and has no 0 digit cs = candidates(9, diff(digits, {0, 8, 9})) elif k > 5: # subsequent number with no 0 digit cs = candidates(k, diff(digits, ss[-1], {0, k - 1, k})) else: # subsequent number with no 9 digit xs = {k, 9} if k > 1: xs.add(k - 1) cs = candidates(k, diff(digits, ss[-1], xs)) for s in cs: yield from solve(k - 1, ss + [s]) # look for positions that must occur in all solutions for ss in sorted(intersect(solve(9)), reverse=1): # look for candidates with only a single valid number ns = (valid(ss[0], B, C, D) for (B, C, D) in subsets(ss[1:], size=len, select="P")) n = singleton(filter(None, ns)) if n: printf("{n}")LikeLike
Frits 12:48 am on 24 December 2022 Permalink |
A different approach. At the end only 39 candidate numbers remain.
from itertools import permutations from functools import reduce # convert digit sequences to number d2n = lambda s: reduce(lambda x, y: 10 * x + y, s) # return entry and column value where column <col> is unique def unique_col(seq, col=0): d = dict() for s in seq: d[s[col]] = s[col] in d return [(s[col], s) for s in seq if not d[s[col]]] # generate candidate numbers def generate(): for A, B, C, D in permutations(range(9, -1, -1), 4): if A == 0: break if (A == 9 and D % 2 == 0): continue n = d2n([A, B, C, D]) # n is divisible by A and exactly 2 of B, C, D if n % A or sum(n % d == 0 for d in (B, C, D) if d) != 2: continue # A has to connect with A - 1 and A + 1 so B, C and D # may not be equal to A - 1 or A + 1 if (A < 9 and (A + 1) in {B, C, D}) or \ (A > 1 and (A - 1) in {B, C, D}): continue # no zeroes occurred before the fourth update and no nines after this if (A < 6 or 0 not in {B, C, D}) and \ (A > 4 or 9 not in {B, C, D}): yield (A, B, C, D) # collect candidate numbers in decreasing order ns = list(generate()) # keep maintaining the list of candidate numbers while True: # determine which numbers always exist for a specific leftmost digit ... d = dict() for A, B, C, D in ns: if A not in d: d[A] = {B, C, D} else: d[A] &= {B, C, D} # we need nine queue positions (each with a unique leftmost digit) if len(d) != 9: print("no solution") exit(0) # ... and delete specific candidate numbers for k, vs in d.items(): for v in vs: if k < 9: ns = [n for n in ns if n[0] != (k + 1) or v not in n[1:]] if k > 1: ns = [n for n in ns if n[0] != (k - 1) or v not in n[1:]] delete = set() # for each candidate number check if valid adjacent queue positions exist for A, B, C, D in ns: bef, aft = 0, 0 for A2, B2, C2, D2 in ns: # skip if invalid if len(set([A, B, C, D, A2, B2, C2, D2])) != 8: continue if A == 1 or A2 == A - 1: bef = 1 if A == 9 or A2 == A + 1: aft = 1 # break if we find valid adjacent queue positions if bef == aft == 1: break else: # A, B, C, D has no (two) valid adjacent queue positions delete.add((A, B, C, D)) if not delete: break # delete specific candidate numbers ns = [n for n in ns if n not in delete] print("certain positions:", [d2n(x[1]) for x in unique_col(ns)])LikeLike
Frits 5:47 pm on 24 December 2022 Permalink |
Borrowing Jim’s “intersect” call.
from enigma import SubstitutedExpression, intersect from functools import reduce # we have nine 4-digit numbers = 36 variables # as the leftmost digits are known and the middle entry has to end on zero # we are left with 26 variables, so A-Z # 9ABC, 8DEF, 7GHI, 6JKL, 5MN0, 4OPQ, 3RST, 2UVW, 1XYZ nums = ['ABC', 'DEF', 'GHI', 'JKL', 'MN', 'OPQ', 'RST', 'UVW', 'XYZ'] # convert digit sequences to number d2n = lambda s: reduce(lambda x, y: 10 * x + y, s) # check validity 2nd argument and possible connection with 1st argument def check(s1, s2): n = d2n(s2) # it's leftmost digit and just two others in it were factors of it if n % s2[0] or sum(n % d == 0 for d in s2[1:] if d) != 2: return False if s1 and len(set(s1 + s2)) != 8: return False return True # invalid digit / symbol assignments d2i = dict() for d in range(0, 10): vs = set() if d: vs.update(nums[9 - d]) if d < 9: vs.update(nums[8 - d]) if d > 1: vs.update(nums[10 - d]) # no zeroes occurred before the fourth update and no nines after this if d == 0: vs.update('ABCDEFGHIJKLMN') # as 5MN0 also delete 0 from 4OPQ entries vs.update('OPQ') if d == 9: vs.update('OPQRSTUVWXYZ') if d % 2 == 0: vs.update('C') d2i[d] = vs # the alphametic puzzle p = SubstitutedExpression( [ # only check validity of 9ABC "check([], [9, A, B, C])", # check validity 2nd argument and connection with 1st argument "check([9, A, B, C], [8, D, E, F])", "check([8, D, E, F], [7, G, H, I])", "check([7, G, H, I], [6, J, K, L])", "check([6, J, K, L], [5, M, N, 0])", "check([5, M, N, 0], [4, O, P, Q])", "check([4, O, P, Q], [3, R, S, T])", "check([3, R, S, T], [2, U, V, W])", "check([2, U, V, W], [1, X, Y, Z])", ], answer="(9000+ABC, 8000+DEF, 7000+GHI, 6000+JKL, 5000+10*MN, 4000+OPQ, \ 3000+RST, 2000+UVW, 1000+XYZ)", d2i=d2i, distinct=('ABC', 'DEF', 'GHI', 'JKL', 'MN', 'OPQ', 'RST', 'UVW', 'XYZ'), env=dict(check=check), denest=32, # [CPython] work around statically nested block limit verbose=0, # use 256 to see the generated code ) answs = [y for _, y in p.solve()] print("certain positions:", list(d2n([x]) for x in intersect(answs)))LikeLike
Jim Randell 4:41 pm on 26 December 2022 Permalink |
@Frits: That’s neat. I hadn’t thought of using the [[
SubstitutedExpression]] solver.Here’s a run file that solves the puzzle (it does generate all possible sequences though, so it is not as fast as my second program).
This run file executes in 98ms.
Run: [ @replit ]
#! python3 -m enigma -r SubstitutedExpression # the positions are: # 9xxx = ABCD # 8xxx = EFGH # 7xxx = IJKL # 6xxx = MNPQ # 5xxx = RSTU # 4xxx = VWXY # 3xxx = Zabc # 2xxx = defg # 1xxx = hijk # leading digits are known --assign="A,9" --assign="E,8" --assign="I,7" --assign="M,6" --assign="R,5" --assign="V,4" --assign="Z,3" --assign="d,2" --assign="h,1" # no number shares digits with its neighbour --distinct="ABCDEFGH,EFGHIJKL,IJKLMNPQ,MNPQRSTU,RSTUVWXY,VWXYZabc,Zabcdefg,defghijk" # each number is divisible by its leading digit and exactly 2 of the others --code="divides = lambda n, d: d > 0 and n % d == 0" --code="check = lambda n, A, B, C, D: divides(n, A) and sum(divides(n, x) for x in (B, C, D)) == 2" "check({ABCD}, {A}, {B}, {C}, {D})" "check({EFGH}, {E}, {F}, {G}, {H})" "check({IJKL}, {I}, {J}, {K}, {L})" "check({MNPQ}, {M}, {N}, {P}, {Q})" "check({RSTU}, {R}, {S}, {T}, {U})" "check({VWXY}, {V}, {W}, {X}, {Y})" "check({Zabc}, {Z}, {a}, {b}, {c})" "check({defg}, {d}, {e}, {f}, {g})" "check({hijk}, {h}, {i}, {j}, {k})" # 9xxx is odd "{D} % 2 == 1" # no 0's in 9xxx, 8xxx, 7xxx, 6xxx --invalid="0,ABCDEFGHIJKLMNPQ" # no 9's in 5xxx, 4xxx, 3xxx, 2xxx, 1xxx --invalid="9,RSTUVWXYZabcdefghijk" # collect numbers that occur in all sequences --answer="({ABCD}, {EFGH}, {IJKL}, {MNPQ}, {RSTU}, {VWXY}, {Zabc}, {defg}, {hijk})" --code="fn = lambda xs: sorted(intersect(xs), reverse=1)" --accumulate="fn" --template="({ABCD} {EFGH} {IJKL} {MNPQ} {RSTU} {VWXY} {Zabc} {defg} {hijk})" --solution="" --denest=1 # CPython workaroundLikeLike
Hugh Casement 11:49 am on 1 January 2023 Permalink |
I found, in addition to those mentioned by Jim,
6492, 6924, 6948
eight possible numbers starting with 3 and also containing 015 or 156 in some order
seven possible numbers starting with 2 and all containing 4 and 8
twelve possible numbers starting with 1 and all containing 5.
LikeLike