Sunday Times Teaser 2985 – What’s My (Land) Line?

by Angela Newing

Published December 8 2019 (link)

My telephone has the usual keypad:

1 2 3
4 5 6
7 8 9
0 0

My telephone number starts with 01 and ends in 0. All digits from 2 to 9 are used exactly once in between, and each pair of adjacent digits in the phone number appear in a different row and column of the keypad array.

The 4th and 5th digits are consecutive as are the 9th and 10th and the 8th digit is higher than the 9th.

What is my number?

5 Comments Leave one →

Brian Gladman permalink


from itertools import permutations

# the keypad rows and columns for digits 0..9
r = (4, 1, 1, 1, 2, 2, 2, 3, 3, 3)
c = (2, 1, 2, 3, 1, 2, 3, 1, 2, 3)

# return true if digits x and y do not share a keypad row or column
disjoint = lambda x, y: all(u[x] != u[y] for u in (r, c))

# try digits in 2..9 for the 4th and 5th digits (consecutive)
s8 = set(range(2, 10))
for d4 in s8:
  for d5 in (d4 - 1, d4 + 1):
    if d5 not in s8 or not disjoint(d4, d5):
      continue
      
    # try the remaining digits for the 9th and 10th digits (consecutive)
    s6 = s8.difference([d4, d5])
    for d9 in s6:
      for d10 in (d9 - 1, d9 + 1):
        if d10 not in s6 or not disjoint(d9, d10):
          continue
        
        # try the remaining digits for the 8th digit (higher than the 9th)
        s4 = s6.difference([d9, d10])
        for d8 in s4:
          if d8 < d9:
            continue
          
          # try the remaining digits for the 3rd, 6th and 7th digits
          for d3, d6, d7 in permutations(s4.difference([d8])):
            
            ds = [0, 1, d3, d4, d5, d6, d7, d8, d9, d10, 0]
            # check that consecutive digits do not share a keypad row or column
            if all(disjoint(p, q) for p, q in zip(ds, ds[1:])):
              print(f"Telepone number {''.join(str(x) for x in ds)}")

from itertools import permutations

# the keypad rows and columns for digits 0..9

r = (4, 1, 1, 1, 2, 2, 2, 3, 3, 3)

c = (2, 1, 2, 3, 1, 2, 3, 1, 2, 3)

# return true if digits x and y do not share a keypad row or column

disjoint = lambda x, y: all(u[x] != u[y] for u in (r, c))

# try digits in 2..9 for the 4th and 5th digits (consecutive)

s8 = set(range(2, 10))

for d4 in s8:

for d5 in (d4 - 1, d4 + 1):

if d5 not in s8 or not disjoint(d4, d5):

continue

# try the remaining digits for the 9th and 10th digits (consecutive)

s6 = s8.difference([d4, d5])

for d9 in s6:

for d10 in (d9 - 1, d9 + 1):

if d10 not in s6 or not disjoint(d9, d10):

continue

# try the remaining digits for the 8th digit (higher than the 9th)

s4 = s6.difference([d9, d10])

for d8 in s4:

if d8 < d9:

continue

# try the remaining digits for the 3rd, 6th and 7th digits

for d3, d6, d7 in permutations(s4.difference([d8])):

ds = [0, 1, d3, d4, d5, d6, d7, d8, d9, d10, 0]

# check that consecutive digits do not share a keypad row or column

if all(disjoint(p, q) for p, q in zip(ds, ds[1:])):

print(f"Telepone number {''.join(str(x) for x in ds)}")

Tony Smith permalink

The wording is loose and fails to rule out numbers with 0s & 1s “in between”.
I have found 2 such numbers. I think there may be more (even when sequences of multiple “01”s are excluded).
How much adjustment to the program would be needed to find the complete set?

Brian Gladman permalink

Hi Tony,

Here is an alternative solution that can answer your question:


exclude = {(1, 0, 1, 0), (0, 1, 0, 1)}

# the keypad rows and columns for digits 0..9
r = (4, 1, 1, 1, 2, 2, 2, 3, 3, 3)
c = (2, 1, 2, 3, 1, 2, 3, 1, 2, 3)

# return true if digits x and y do not share a keypad row or column
disjoint = lambda x, y: all(u[x] != u[y] for u in (r, c))

def solve(dgts, pn):
  ln = len(pn)
  
  # don't allow consecutive repeats of the 01 sequence
  if ln > 3 and pn[-4:] in exclude:
    return
  
  # digits 3 and 4 and digits 9 and 10 must be consecutive
  if ln in {5, 10} and abs(pn[-2] - pn[-1]) != 1:
    return
  
  # digit 8 must be higher than digit 9
  if ln == 9 and pn[-2] <= pn[-1]:
    return
  
  # if we have used all digits 2..9 exactly once
  if not dgts:
    if not pn[-1]:
      yield ''.join(str(x) for x in pn)

  # add a digit from (0, 1) or those remaining in 2..9 and continue
  for d in dgts | {0, 1}:
    if disjoint(pn[-1], d) and (pn + (d,))[-4:] not in exclude:
      yield from solve(dgts.difference([d]), pn + (d,))

nbrs = sorted(int(x) for x in solve(set(range(2, 10)), (0, 1)))
ln = len(nbrs)
print(f"{ln:,} solutions:")
for i, n in enumerate(nbrs, 1):
  if i > 10:
    break
  print(f"{i:6} 0{n}")
print("......")
for i in range(ln - 10, ln):
  print(f"{i + 1:6} 0{nbrs[i]}")

exclude = {(1, 0, 1, 0), (0, 1, 0, 1)}

# the keypad rows and columns for digits 0..9

r = (4, 1, 1, 1, 2, 2, 2, 3, 3, 3)

c = (2, 1, 2, 3, 1, 2, 3, 1, 2, 3)

# return true if digits x and y do not share a keypad row or column

disjoint = lambda x, y: all(u[x] != u[y] for u in (r, c))

def solve(dgts, pn):

ln = len(pn)

# don't allow consecutive repeats of the 01 sequence

if ln > 3 and pn[-4:] in exclude:

return

# digits 3 and 4 and digits 9 and 10 must be consecutive

if ln in {5, 10} and abs(pn[-2] - pn[-1]) != 1:

return

# digit 8 must be higher than digit 9

if ln == 9 and pn[-2] <= pn[-1]:

return

# if we have used all digits 2..9 exactly once

if not dgts:

if not pn[-1]:

yield ''.join(str(x) for x in pn)

# add a digit from (0, 1) or those remaining in 2..9 and continue

for d in dgts | {0, 1}:

if disjoint(pn[-1], d) and (pn + (d,))[-4:] not in exclude:

yield from solve(dgts.difference([d]), pn + (d,))

nbrs = sorted(int(x) for x in solve(set(range(2, 10)), (0, 1)))

ln = len(nbrs)

print(f"{ln:,} solutions:")

for i, n in enumerate(nbrs, 1):

if i > 10:

break

print(f"{i:6} 0{n}")

print("......")

for i in range(ln - 10, ln):

print(f"{i + 1:6} 0{nbrs[i]}")

If we allow consecutive repeats of the sequence ’01’ or ’10’ there are an infinite number of solutions but not allowing such repetitions gives 148,767 solutions starting and ending:

1 01867295340
2 0104351867290
3 0106729534810
4 0106751834290
5 0107629534810
6 0107681534290
7 0151034867290
8 0151043867290
9 0151072943860
10 0151076834290
……
148758 0191015101810162701030104010
148759 0191015101810162701040103010
148760 0191018101510160103010427010
148761 0191018101510160103010724010
148762 0191018101510160104270103010
148763 0191018101510160107240103010
148764 0191018101510162401030107010
148765 0191018101510162401070103010
148766 0191018101510162701030104010
148767 0191018101510162701040103010

Robert Brown permalink

UK landline telephone numbers cannot be longer than 11 digits total – that’s the area code starting 01 followed by the actual number.

Reply

Tony Smith permalink

Thanks Brian.
I had found 2 with 13 digits!

Reply

Sunday Times Teaser 2985 – What’s My (Land) Line?

by Angela Newing

Published December 8 2019 (link)

Leave a comment to Robert Brown Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta