Sunday Times Teaser 3048 – Nero Scrag from Carregnos

by BRG on February 20, 2021

by Stephen Hogg

Published Sunday February 21 2021 (link)

Our holiday rep, Nero, explained that in Carregnos an eight-digit total of car registrations results from combinations of three Greek capital letters after four numerals (eg 1234 ΩΘΦ), because some letters of the 24-letter alphabet and some numerals (including zero) are not permitted.

For his own “cherished” registration the number tetrad is the rank order of the letter triad within a list of all permitted letter triads ordered alphabetically. Furthermore, all permitted numeral tetrads can form such “cherished” registrations, but fewer than half of the permitted letter triads can.

Nero asked me to guess the numbers of permitted letters and numerals. He told me that I was right and wrong respectively, but then I deduced the permitted numerals.

List these numerals in ascending order

From → Uncategorized

13 Comments Leave one →

Brian Gladman permalink


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).")

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).")

Tony Smith permalink

Brian
The Teaser does not state that the tourist did any analysis before his 2 initial guesses.

It is conceivable that there are numbers of permitted letters which allow exactly one possible number of permitted digits.

The tourist could have guessed such a number of permitted letters and an incorrect number of permitted digits. Once he knew the correct number of permitted letters he could then deduce the correct number of permitted digits, and maybe the actual digits.

I suspect that some or all of the programs here do not rule out this possibility.

Reply
- Brian Gladman permalink
  
  Hi Tony,
  
  When we do a manual analysis of the situation in which the tourist finds
  themselves, we obtain the following possibilities for L (the number of
  letters), D (the number of digits) and M (the maximum digit):
  
  L => (D, M) pairs
  20 [(6, 6), (6, 7), (7, 7)]
  21 [(6, 6), (6, 7), (6, 8), (7, 7), (7, 8), (8, 8)]
  22 [(6, 6), (6, 7), (6, 8), (6, 9), (7, 7), (7, 8), (7, 9), (8, 8), (8, 9)]
  
  So we know that the situation you postulate doesn’t exist.
  
  And, since the programs do the same analysis, they too will rule it out.
  
  Reply
  - Tony Smith permalink
    
    It seems to me that my hypothetical number would survive the
    analysis up to line 36 of your program and fail at line 44.
    
    Obviously if there was a test before line 44 that each number
    of possible permitted letters gave at least 2 possible numbers
    of permitted digits we could be sure that there is, in fact,
    no hypothetical number. Of course the manual analysis shows
    that the test would be passed.
    
    Although, essentially, this Teaser only needs the solution to
    three inequalities applying to a small range of numbers, it is
    very interesting.
    
    Reply
    - Brian Gladman permalink
      
      Sadly (or maybe not) simple programs don’t deal with
      hypothetical numbers, only concrete ones. The only
      numbers of letters that reach lines 39 and above are
      20, 21 and 22. This can be confirmed by inserting a
      print statement before line 36.

Frits permalink

The “fewer than half ” constraint is not needed to limit the solution.


# 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]}")

# 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]}")

Erling Torkildsen permalink


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]))

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]))

Brian Gladman permalink

@Erling

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:


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).")

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).")

Erling Torkildsen permalink

Tanks Brian,
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.

Erling Torkildsen permalink

I now realize what Brian’s disapproval is about. When restricted to cases with two alternatives (len(S) == 2) my dict S above is {20: [(1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7)]}. While those values contain information to pick the answer, they are not answer-alternatives in themselves. To use the one that only indirectly is, to display the answer, is ‘opportunistic’ and not proper programming.

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.

Brian Gladman permalink

Yes, my apologies for line 25, which is beyond reasonable. Here is is done in a sane way:


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

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

Frits permalink

Although Erling said he tried to use a a minimum of ‘analytics’ using “product” in lines 18-19 seems to be overkill as we only have to check that the highest possible number (highest digit in z * 1111) is less equal to L ** 3.

Reply
- Brian Gladman permalink
  
  @Frits Yes, I am sure you are right. But my concern was getting it to work correctly so I left it alone except for those parts of it that I thought were bugs. However the test you mention is missing from lines 10-11 so this is a bug I should have noticed!
  
  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.
  
  Reply

Sunday Times Teaser 3048 – Nero Scrag from Carregnos

by Stephen Hogg

Published Sunday February 21 2021 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta