Sunday Times Teaser 3110 – Many a Slip

by BRG on April 29, 2022

by Victor Bryant

Published Sunday May 01 2022 (link)

I have written down three 3-figure numbers in decreasing order and added them up to give their 4-figure sum, which is a perfect square: the digit 0 occurred nowhere in my sum.

Now I have attempted to replace digits consistently by letters and I have written the sum as

CUP + AND + LIP = SLIP

However, there’s “many a slip twixt cup and lip” and unfortunately one of those thirteen letters is incorrect. If you knew which letter was incorrect then you should be able to work out the three 3-figure numbers.

What are they?

From → Uncategorized

2 Comments Leave one →

Brian Gladman permalink

My first attempt was hopeless and ran in around 8 seconds! My second attempt was faster but was very long and not a great deal faster. But this one is Ok and runs in less than 100 milliseconds with profile based timing.


from itertools import permutations
from collections import defaultdict

# set to True to include non-unique output
full = True

def output(p, uvw, r):
  for l, x in zip((8, 5, 2), (9, 6, 3)):
    if p > l:
      p += x
      break
  print(f"{' + '.join(str(x) for x in uvw)} = {r}")
  print(f"CUP + AND + LIP = SLIP")
  print(' ' * (p - 1), '^')
  
# four digit squares below 3000 with no zeros and no repeated digits
sq4d = tuple(x * x for x in range(32, 55) 
             if '0' not in str(x * x) and len(set(str(x * x))) == 4)

text = 'CUPANDLIPSLIP'

# for mapping the errooneous letter positions to solutions
p2s = defaultdict(set)

# consider the position of the erroneous letter
for p, ltr in enumerate(text):
  
  # substitute each of the letters it could be (including Z!)
  for z in set(text).union('Z').difference([ltr]):
    t = text[:p] + z + text[p+1:]
    
    # consider possible results of the addition (a perfect square)
    for r in sq4d:
      
      # map the right hand side letters to the result digits
      l2di = dict(zip(t[9:], (int(x) for x in str(r))))
      
      # find letters and digits not on the right hand side ...
      rtxt = ''.join(set(c for c in t if c not in l2di))
      dset = set(range(1, 10)).difference(int(x) for x in str(r))
      
      # ... and map these letters to these digits
      for pm in permutations(dset, len(rtxt)):
        l2d = l2di.copy()
        l2d.update(zip(rtxt, pm))
        
        # form and check that the sum is correct
        u = 100 * l2d[t[0]] + 10 * l2d[t[1]] + l2d[t[2]]
        v = 100 * l2d[t[3]] + 10 * l2d[t[4]] + l2d[t[5]]
        w = 100 * l2d[t[6]] + 10 * l2d[t[7]] + l2d[t[8]]
        if u > v > w and u + v + w == r:
          p2s[p].add(((u, v, w), r))
          if full:
            output(p, (u, v, w), r)

# look for an erroneous position that gives a unique result
for p, v in p2s.items():
  if len(v) == 1:
    output(p, *(v.pop()))

from itertools import permutations

from collections import defaultdict

# set to True to include non-unique output

full = True

def output(p, uvw, r):

for l, x in zip((8, 5, 2), (9, 6, 3)):

if p > l:

p += x

break

print(f"{' + '.join(str(x) for x in uvw)} = {r}")

print(f"CUP + AND + LIP = SLIP")

print(' ' * (p - 1), '^')

# four digit squares below 3000 with no zeros and no repeated digits

sq4d = tuple(x * x for x in range(32, 55)

if '0' not in str(x * x) and len(set(str(x * x))) == 4)

text = 'CUPANDLIPSLIP'

# for mapping the errooneous letter positions to solutions

p2s = defaultdict(set)

# consider the position of the erroneous letter

for p, ltr in enumerate(text):

# substitute each of the letters it could be (including Z!)

for z in set(text).union('Z').difference([ltr]):

t = text[:p] + z + text[p+1:]

# consider possible results of the addition (a perfect square)

for r in sq4d:

# map the right hand side letters to the result digits

l2di = dict(zip(t[9:], (int(x) for x in str(r))))

# find letters and digits not on the right hand side ...

rtxt = ''.join(set(c for c in t if c not in l2di))

dset = set(range(1, 10)).difference(int(x) for x in str(r))

# ... and map these letters to these digits

for pm in permutations(dset, len(rtxt)):

l2d = l2di.copy()

l2d.update(zip(rtxt, pm))

# form and check that the sum is correct

u = 100 * l2d[t[0]] + 10 * l2d[t[1]] + l2d[t[2]]

v = 100 * l2d[t[3]] + 10 * l2d[t[4]] + l2d[t[5]]

w = 100 * l2d[t[6]] + 10 * l2d[t[7]] + l2d[t[8]]

if u > v > w and u + v + w == r:

p2s[p].add(((u, v, w), r))

if full:

output(p, (u, v, w), r)

# look for an erroneous position that gives a unique result

for p, v in p2s.items():

if len(v) == 1:

output(p, *(v.pop()))

John Z. permalink

I used the initial part of the first version of your solution, Brian, and replaced your mismatch search with my own which I think is is simpler and easier to understand.


from collections import defaultdict
from itertools import permutations

# key is the mismatched letter, value: the possible solution + 2 mm digits
l2s = dict()
# key is 1/2 letters linked to twice used digit, value: the other letter, digit
d2s = dict()
# key is the mismatched letter, value: the count of possible solutions
mmc = defaultdict(int)

az = 'CUPANDLIPSLIP'

# four digit squares below 3000 with no zeros or repeated digits
sq4d = tuple(x * x for x in range(32, 55)
             if '0' not in str(x * x) and len(set(str(x * x))) == 4)

#consider the possible values of 'SLIP'
for slip in sq4d:
  
  # consider values for non repeated letters and one repeated letter: 'P'
  # L & I are derived below
  for C, U, P, A, N, D in permutations(set(range(1, 10)) - {slip // 1000}, 6):

    cup = C * 100 + U * 10 + P
    anD = A * 100 + N * 10 + D

    if anD > cup:
     continue
    
    lip = slip - cup - anD

    if lip < 100 or '0' in str(lip) or lip >= anD:
      continue
    
    # map digits to characters
    digits = ''.join(str(x) for x in (cup, a nD, lip, slip))

    # all nine digits 1 - 9 must be used or there will be multiple mismatches
    if len(set(digits)) != 9:
      continue
    
    # pair letters to digits: zip; remove matches: set; and sort by letters
    wd = sorted(set(zip(az, digits)))

    # Teaser statement says 'the incorrect letter' so it must be a repeated
    # letter, otherwise there would be 2 'incorrect letters'
    # check if 1 mismatch only in L I P: {(I, 1), (I, 1)} -> {(I, 1)} etc.
    # len(wd) > 10 means there is more than 1 mismatch
    if len(wd) != 10:
      continue
    
    # scan wd to find the mismatch (same letter, diff digits)
    mml, mmd = [(v[0], (v[1], wd[i][1])) for i, v in enumerate(wd[1:])
          if v[0] == wd[i][0]][0]
    
    # increase mismatch count for the unique mismatched letter  
    mmc[mml] += 1
    
    # save last and possibly only solution & the 2 mismatched digits: mmd
    l2s[mml] = (cup, anD, lip, slip, mmd)
                                         
    # find the possible 'other' letter involved when L I or P are linked
    # to 2 different digits
    d2s[mml] = [(a, n) for a, n in wd if a != mml and n in mmd]
    
     
# get mismatched repeated letter that occurs the fewest times (in theory once)   
ltr = min(mmc.items(), key = lambda c : c[1])[0]
# the other letter sharing one of its digits
lpr = d2s[ltr][0][0]
os = "CUP + AND + LIP = SLIP" # output string

print(ltr, '&', lpr, 'share the digit', d2s[ltr][0][1])
print(ltr, "is the 'incorrect' repeated letter with", *l2s[ltr][4])
print(os)
print(' + '.join(str(x) for x in l2s[ltr][:3]),'=', l2s[ltr][3])
print(''.join('|' if c in (lpr, ltr) else ' ' for c in os))

from collections import defaultdict

from itertools import permutations

# key is the mismatched letter, value: the possible solution + 2 mm digits

l2s = dict()

# key is 1/2 letters linked to twice used digit, value: the other letter, digit

d2s = dict()

# key is the mismatched letter, value: the count of possible solutions

mmc = defaultdict(int)

az = 'CUPANDLIPSLIP'

# four digit squares below 3000 with no zeros or repeated digits

sq4d = tuple(x * x for x in range(32, 55)

if '0' not in str(x * x) and len(set(str(x * x))) == 4)

#consider the possible values of 'SLIP'

for slip in sq4d:

# consider values for non repeated letters and one repeated letter: 'P'

# L & I are derived below

for C, U, P, A, N, D in permutations(set(range(1, 10)) - {slip // 1000}, 6):

cup = C * 100 + U * 10 + P

anD = A * 100 + N * 10 + D

if anD > cup:

continue

lip = slip - cup - anD

if lip < 100 or '0' in str(lip) or lip >= anD:

continue

# map digits to characters

digits = ''.join(str(x) for x in (cup, a nD, lip, slip))

# all nine digits 1 - 9 must be used or there will be multiple mismatches

if len(set(digits)) != 9:

continue

# pair letters to digits: zip; remove matches: set; and sort by letters

wd = sorted(set(zip(az, digits)))

# Teaser statement says 'the incorrect letter' so it must be a repeated

# letter, otherwise there would be 2 'incorrect letters'

# check if 1 mismatch only in L I P: {(I, 1), (I, 1)} -> {(I, 1)} etc.

# len(wd) > 10 means there is more than 1 mismatch

if len(wd) != 10:

continue

# scan wd to find the mismatch (same letter, diff digits)

mml, mmd = [(v[0], (v[1], wd[i][1])) for i, v in enumerate(wd[1:])

if v[0] == wd[i][0]][0]

# increase mismatch count for the unique mismatched letter

mmc[mml] += 1

# save last and possibly only solution & the 2 mismatched digits: mmd

l2s[mml] = (cup, anD, lip, slip, mmd)

# find the possible 'other' letter involved when L I or P are linked

# to 2 different digits

d2s[mml] = [(a, n) for a, n in wd if a != mml and n in mmd]

# get mismatched repeated letter that occurs the fewest times (in theory once)

ltr = min(mmc.items(), key = lambda c : c[1])[0]

# the other letter sharing one of its digits

lpr = d2s[ltr][0][0]

os = "CUP + AND + LIP = SLIP" # output string

print(ltr, '&', lpr, 'share the digit', d2s[ltr][0][1])

print(ltr, "is the 'incorrect' repeated letter with", *l2s[ltr][4])

print(os)

print(' + '.join(str(x) for x in l2s[ltr][:3]),'=', l2s[ltr][3])

print(''.join('|' if c in (lpr, ltr) else ' ' for c in os))

Sunday Times Teaser 3110 – Many a Slip

by Victor Bryant

Published Sunday May 01 2022 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta