NOTE: I owe Erling an apology since the omission of the constraint you mention is NOT a bug. The whole point of Erling’s code it that he doesn’t need to include this constraint because he explicitly generates and counts all valid sets of of digits. As you say, it is a very slow approach when compared with others but it nice to see a different approach being used, which is why I wanted to see it published in a corrected form.

]]>
1 2 3 4 5 6 7 8 9 |
L2NM = dict() for L in range(14, 23): s = set() for N in range(1, 10): if is_regno(N, L): s.update(ranks(N, L)) L2NM[L] = s |

I also realize that itertools product function is a better alternative for producing all the 4-digit numbers than my nested loops. But I have not yet grasped in detail what goes on in the rather compact way that L2NM is built.

]]>It is a treacherous encouragement to get the answer you expect to be the right one. It weakens the judgement.

I do not right away see how my program fail, but I shall study your alternative to find out. ]]>

I like your approach because, in contrast to my own and Frits’ solutions, you produce sets of permitted digits directly.

But I think it goes slightly wrong because your rnks() subroutine (on line 18) only returns the first set of permitted digits it finds when it is necessary to consider all valid sets of permitted digits for each number of permitted letters.

Here is a version that follows your approach but is modified to overcome this issue:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
from itertools import combinations, product # The numbers of permitted Numerals and Letters are respectively # N (<= 8) and L (<= 22); M is the maximum numeral # The numbers of permitted Numerals and Letters are respectively # N (<= 8) and L (<= 22); M is the maximum numeral # Accept only (N, L) combinations that give 8-digit numeral/letter # registrations and can form cherished registrations for less than # half the letter registrations def is_regno(N, L): u, v = N ** 4, L ** 3 return 10 ** 7 <= u * v and 2 * u < v # compile (and return) all the sets of N permitted digits that can # enumerate all letter registrations with L permitted letters def ranks(N, L): for z in combinations(range(1, 10), N): if sum(1000 * a + 100 * b + 10 * c + d <= L ** 3 for a, b, c, d in product(z, repeat=4)) == N ** 4: # return the number of permitted digits and the maximum digit yield len(z), max(z) # map the number of permitted registration letters to the # sets of permitted digits that can enumerate them L2NM = {L:set().union(*(ranks(N, L) for N in range(1, 10) if is_regno(N, L))) for L in range(14, 23)} # consider the possible numbers of permitted letters for L, l_NM in L2NM.items(): # there must be only two numbers of permitted digits # so that the wrong answer identifies the right one pdgts = tuple(n for n, m in l_NM) if len(set(pdgts)) == 2: # find a unique number of permitted digits that also # allows all the permitted digits to be identified for N, M in l_NM: if pdgts.count(N) == 1 and N == M: print(f"Digits 1..{M} (with {L} letters).") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from itertools import combinations # N is the number of numerals allowed in the tetrad and A is the # number of letters allowed in the triad part, Alphabet-part # The program uses a minimum of ‘analytics’, it tests constrictions S = dict() # For mapping acceptable combinations if A and N # Accept only combinations of A and N that give 8-digit volume def regno(N, A): test1 = 9999999 < N ** 4 * A ** 3 < 100000000 test2 = A ** 3 > 2 * N ** 4 return test1 and test2 # Find (and return) instances of actual permitted sets of digits # that keep the number-part within the range from 1 to A^3. def rnks(N, A): for z in combinations(range(1, 10), N): n = 0 for a in z: for b in z: for c in z: for d in z: if 1000 * a + 100 * b + 10 * c + d <= A ** 3: n += 1 if n == N**4: return z # Feed ‘regno()’ and ‘rnks()’ above with combinations of A and N # that produce 8-digit registrations and map those which comply for A in range(14, 24): W = list() for N in range(5, 10): if regno(N, A): W.append(rnks(N, A)) S[A] = W # Fewer acceptable numerals than maximum of allowed cannot be unique.. for s in S: if len(S[s]) == 2: print("The accepted digits are:", max(list(S[s])[0], list(S[s])[1])) |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# ceil a positive number ceil = lambda n: int(n) if n == int(n) else int(n) + 1 # --- assume "some letters" means "at least 2 letters" etc --- # the maximum possible car registration has at least 8 characters: # so ndigits ** 4 times nletters ** 3 >= 10 ** 7 # choose the highest number of permitted numerals (eight) # for the lowest number of permitted letters min_nletters = ceil((10 ** 7 // (8 ** 4)) ** (1 / 3)) # consider the number of permitted letters (< 23) for nl in range(min_nletters, 23): ntriads = nl ** 3 # consider the maximum 4-digits numbers (1111 * highest digit) # the smallest must not be greater than the number of letter triads # 1111 * nd <= ntriads, so nd <= ntriads / 1111 max_ndigits = min(8, ntriads // 1111) min_ndigits = ceil((10 ** 7 // (nl ** 3)) ** 0.25) li = [] # consider the number of permitted numerals (< 9) for nd in range(min_ndigits, max_ndigits + 1): ntetrads = nd ** 4 # fewer than half the letter triads correspond to number tetrads if not(ntriads > 2 * ntetrads): continue li.append(nd) # if you rightly guess the number of permitted letters and you wrongly # guess the number of permitted numerals you can only know the numerals # if there were 2 options for the number of permitted numerals if len(li) == 2: # "I deduced the permitted numerals" # you can only know the permitted numerals if they are 1...nd # this must be the last stored <li> entry # check that nd+1 is not permitted as a numeral if 1111 * (li[1] + 1) > ntriads: print(f"answer 1...{li[1]}") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
from collections import defaultdict # map the number of permitted letters (L) used to solutions as # the number of permitted digits (N) and the maximum digit (M) L2NM = defaultdict(list) # consider the number of permitted letters (24 - 'some') # (14 is the L value below which no 4-digit registration # numbers can produce 8-digit numbers of registrations) for L in range(14, 23): # the number of possible Letter Registration Sequences (LRS) l_regs = L ** 3 # now consider the number of permitted digits (10 - 'some') for N in range(1, 9): # the number of Digit Registration Sequences (DRS) d_regs = N ** 4 # the maximum possible number of combined digit and # letter registrations has at least eight digits; the # number of DRS is less than half the number of LRS if d_regs * l_regs >= 10 ** 7 and 2 * d_regs < l_regs: # consider the maximum digit in use (which is at least # the number of digits in use since zero is not allowed) for M in range(N, 10): # every DRS is the index of an LRS, so the maximum DRS # cannot be greater than the number of LRS if 1111 * M <= l_regs: # index potential solutions on the number of letters used L2NM[L].append((N, M)) # consider the number of permitted letters ... for L, l_NM in L2NM.items(): # ... for which there must be two numbers of permitted digits # in order that the wrong answer identifies the right one pdgts = tuple(N for N, M in l_NM) if len(set(pdgts)) == 2: # find a unique solution for N, M in l_NM: if pdgts.count(N) == 1 and N == M: print(f"Digits 1..{M} (with {L} letters).") |