Sunday Times Teaser 2816 – Chat Shows

by Graham Smithers

Published: 11 September 2016 (link)

Each day next week there will be a chat show on television and in each show the host will appear with an actress and an actor. The hosts will be (in order) Dimbleby, Evans, Mack, Marr, Norton, Peschardt and Ross. In no particular order, the actresses will be Arterton, Blunt, Carter, Jones, Knightley, Margolyes and Watson. Again in no particular order, the actors will be Bean, Caine, Cleese, Craig, De Niro, Neeson and Oldman. For any two people in the same show there are just two different letters of the alphabet that occur (perhaps more than once) in both their surnames.

List the actresses in the order in which they appear.

3 Comments Leave one →

Brian Gladman permalink

This is a second of this type from Graham Smithers in recent times (see Teaser 2800; Teaser 2704 also has similarities).


from itertools import permutations

hosts = ('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross')

actresses = ('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 
             'Margolyes', 'Watson')

actors = ('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# map the names to their sets of letters
h2sl = {h:set(h.lower()) for h in hosts}
s2sl = {s:set(s.lower()) for s in actresses}
r2sl = {r:set(r.lower()) for r in actors}
        
# permute the actresses names
for ps in permutations(actresses):
  
  # ensure that all hosts and actresses names share two letters 
  if all(len(h2sl[h] & s2sl[s]) == 2 for h, s in zip(hosts, ps)):

    # permute the actors names  
    for pr in permutations(actors):
      
      # ensure that all hosts and actors names share two letters 
      if all(len(h2sl[h] & r2sl[r]) == 2 for h, r in zip(hosts, pr)):
      
        # ensure that all actresses and actors names share two letters 
        if all(len(s2sl[s] & r2sl[r]) == 2 for s, r in zip(ps, pr)):
          
          # output the answer
          s = ', '.join(ps)
          f, s, l = s.rpartition(', ')
          print('{}.'.format(f + ' and ' + l))
          
          # output the three associations
          s = [', '.join(x) for x in zip(hosts, ps, pr)]
          print('\n{}\n'.format('\n'.join(s)))

from itertools import permutations

hosts = ('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross')

actresses = ('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley',

'Margolyes', 'Watson')

actors = ('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# map the names to their sets of letters

h2sl = {h:set(h.lower()) for h in hosts}

s2sl = {s:set(s.lower()) for s in actresses}

r2sl = {r:set(r.lower()) for r in actors}

# permute the actresses names

for ps in permutations(actresses):

# ensure that all hosts and actresses names share two letters

if all(len(h2sl[h] & s2sl[s]) == 2 for h, s in zip(hosts, ps)):

# permute the actors names

for pr in permutations(actors):

# ensure that all hosts and actors names share two letters

if all(len(h2sl[h] & r2sl[r]) == 2 for h, r in zip(hosts, pr)):

# ensure that all actresses and actors names share two letters

if all(len(s2sl[s] & r2sl[r]) == 2 for s, r in zip(ps, pr)):

# output the answer

s = ', '.join(ps)

f, s, l = s.rpartition(', ')

print('{}.'.format(f + ' and ' + l))

# output the three associations

s = [', '.join(x) for x in zip(hosts, ps, pr)]

print('\n{}\n'.format('\n'.join(s)))

Here is a different (and faster) approach


from collections import defaultdict
from itertools import product

hosts = ('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross')

actresses = ('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 
             'Margolyes', 'Watson')

actors = ('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# map the names to their sets of letters
h2sl = {h:set(h.lower()) for h in hosts}
s2sl = {s:set(s.lower()) for s in actresses}
r2sl = {r:set(r.lower()) for r in actors}

# filter a list of triplets into those that are unique for
# their first item and those that are not
def filter(t):
  d = defaultdict(list)
  for h, s, r in t:
    d[h].append((h, s, r))
  un, non_un = [], []
  for h, l_sr in d.items():
    (non_un if len(l_sr) > 1 else un).extend(l_sr)
  return un, non_un

# create triplets of (hosts, actresses, actors) for which any
# pair of names shares only two (possibly repeated) letters
triplets = []
for h, s in product(hosts, actresses):
  if len(h2sl[h] & s2sl[s]) == 2:
    for r in actors:
      if len(h2sl[h] & r2sl[r]) == len(s2sl[s] & r2sl[r]) == 2:
        triplets.append((h, s, r))

while True:
  # separate hosts into those who have only one 
  # possible (actress, actor) pair and those
  # that have mulltiple possibilities
  unique, non_unique = filter(triplets)
  # we are done if all hosts have only one possible
  # (actress, actor) pair
  if not non_unique:
    break
  # find the sets of actresses and actors who must
  # pair with unique hosts 
  ss = set(s for h, s, r in unique)
  sr = set(r for h, s, r in unique)
  # now remove any triplets from non unique hosts
  # that contain these names
  triplets = unique
  for h, s, r in non_unique:
    if not (s in ss or r in sr):
      triplets.append((h, s, r))

# output the answer
s = ', '.join([s for h, s, r in sorted(triplets)])
f, s, l = s.rpartition(', ')
print('{}.\n'.format(f + ' and ' + l))

# output the triplets
for t in sorted(triplets):
  print(', '.join(t))

from collections import defaultdict

from itertools import product

hosts = ('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross')

actresses = ('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley',

'Margolyes', 'Watson')

actors = ('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# map the names to their sets of letters

h2sl = {h:set(h.lower()) for h in hosts}

s2sl = {s:set(s.lower()) for s in actresses}

r2sl = {r:set(r.lower()) for r in actors}

# filter a list of triplets into those that are unique for

# their first item and those that are not

def filter(t):

d = defaultdict(list)

for h, s, r in t:

d[h].append((h, s, r))

un, non_un = [], []

for h, l_sr in d.items():

(non_un if len(l_sr) > 1 else un).extend(l_sr)

return un, non_un

# create triplets of (hosts, actresses, actors) for which any

# pair of names shares only two (possibly repeated) letters

triplets = []

for h, s in product(hosts, actresses):

if len(h2sl[h] & s2sl[s]) == 2:

for r in actors:

if len(h2sl[h] & r2sl[r]) == len(s2sl[s] & r2sl[r]) == 2:

triplets.append((h, s, r))

while True:

# separate hosts into those who have only one

# possible (actress, actor) pair and those

# that have mulltiple possibilities

unique, non_unique = filter(triplets)

# we are done if all hosts have only one possible

# (actress, actor) pair

if not non_unique:

break

# find the sets of actresses and actors who must

# pair with unique hosts

ss = set(s for h, s, r in unique)

sr = set(r for h, s, r in unique)

# now remove any triplets from non unique hosts

# that contain these names

triplets = unique

for h, s, r in non_unique:

if not (s in ss or r in sr):

triplets.append((h, s, r))

# output the answer

s = ', '.join([s for h, s, r in sorted(triplets)])

f, s, l = s.rpartition(', ')

print('{}.\n'.format(f + ' and ' + l))

# output the triplets

for t in sorted(triplets):

print(', '.join(t))

Although this is faster for this specific teaser, the approach suffers the rather serious flaw when adapted to provide a generic solver in that it does not guarantee to find solutions where they exist.

Jim Randell permalink

Graham Smithers seems to like this kind of puzzle, so I wrote some generic code that can solve this puzzle and other similar puzzles.

The same code (using exactly the same selection function) works for Teasers 2682, 2757, 2770, 2800 (all set by Smithers), only the category lists need to be changed.


from itertools import product, combinations
from enigma import printf

# group the lists of elements in <vs> into groups (one element from each list)
# such that the values in the groups satisfy the selection function <fn>
def groups(vs, fn=None, s=[]):
  # are we done?
  if not vs[0]:
    yield s
  else:
    # otherwise choose the next group
    for v in product(*(enumerate(x) for x in vs[1:])):
      g = (vs[0][0],) + tuple(x[1] for x in v)
      if fn(*g):
        # solve for the remaining elements
        yield from groups([vs[0][1:]] + [x[:i] + x[i + 1:] for (x, (i, _)) 
                                 in zip(vs[1:], v)], fn, s + [g])


# categories for this puzzle
hosts = ( 'Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross' )
actresses = ( 'Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 'Margolyes',
              'Watson' )
actors = ( 'Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# return the set of letters in a name
def letters(name):
  return set(x for x in name.lower() if x.isalpha())

# check each pair of names shares exactly two different letters
def check(*names):
  return all(len(letters(a).intersection(letters(b))) == 2 for (a, b) 
                                     in combinations(names, 2))

# match the categories into groups
for s in groups([hosts, actresses, actors], fn=check):
  # output a grouping
  for (host, actress, actor) in s:
    printf("{host}, {actress}, {actor}")
  printf()

from itertools import product, combinations

from enigma import printf

# group the lists of elements in <vs> into groups (one element from each list)

# such that the values in the groups satisfy the selection function <fn>

def groups(vs, fn=None, s=[]):

# are we done?

if not vs[0]:

yield s

else:

# otherwise choose the next group

for v in product(*(enumerate(x) for x in vs[1:])):

g = (vs[0][0],) + tuple(x[1] for x in v)

if fn(*g):

# solve for the remaining elements

yield from groups([vs[0][1:]] + [x[:i] + x[i + 1:] for (x, (i, _))

in zip(vs[1:], v)], fn, s + [g])

# categories for this puzzle

hosts = ( 'Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross' )

actresses = ( 'Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 'Margolyes',

'Watson' )

actors = ( 'Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

# return the set of letters in a name

def letters(name):

return set(x for x in name.lower() if x.isalpha())

# check each pair of names shares exactly two different letters

def check(*names):

return all(len(letters(a).intersection(letters(b))) == 2 for (a, b)

in combinations(names, 2))

# match the categories into groups

for s in groups([hosts, actresses, actors], fn=check):

# output a grouping

for (host, actress, actor) in s:

printf("{host}, {actress}, {actor}")

printf()

The selection function is applied only to completed potential groups, which means it is not as efficient as code that rejects partial potential groupings – but on problems of this size it hardly matters. All the puzzles mentioned above are solved instantaneously.

Brian Gladman permalink

Here is another generic solver using a different strategy


# Generic Solver for Sunday Times Teasers set by Graham Smithers
# that involve lists of words that have to be put into groups in 
# which all pairs share letters in common (e.g. 2682, 2757, 2770, 
# 2800 and 2816).

from itertools import combinations, product
from collections import defaultdict

# find combinations of words, one from each list in <seqs>, such that
# all pairs that can be formed from each combination share exactly <n>
# letters (case is ignored and letters may be repeated within words)
def compose(seqs, n):
  # map the words to their sets of letters
  l_ls = [{w:set(c.lower() for c in w if c.isalpha()) 
           for w in s} for s in seqs]
  # start with single item groups formed from the first sequence
  groups = [[x] for x in seqs[0]]
  # now consider each remaining sequence and try to combine
  # its words with the groups of words formed so far
  for i, s in enumerate(seqs[1:]):
    # now consider each word in the sequence with each group of 
    # words in <groups> and, if the word shares exactly <n> 
    # letters with all the words in a group, we can then form
    # an extended group by adding this sequence item to it
    g = []
    for t, a in product(groups, s):
      if all(len(l_ls[j][t[j]] & l_ls[i + 1][a]) == n for j in range(i + 1)):
        g.append(t + [a])
    # now continue to the next sequence with the new (extended) groups
    groups = g[:]
  return groups

# form groups with one word from each sequence in <seqs> (each of
# the same length) and look for a way of doing this in such a way
# that all items from all sequences are used and each group formed
# is unique with respect to items from the <ix>'th sequence in <seqs> 
def solve(seqs, ix):
  # find all possible groupings
  groups = compose(seqs, 2)
  d = defaultdict(list)
  # group the items for each item in the <ix>'th sequence in <seqs>
  for g in groups:
    d[g[ix]].append(g)
  # consider all possible arrangements of the grouped items
  for p in product(*(d[x] for x in seqs[ix])):
    # and check all items from each sequence are present
    if all(set(x) == set(y) for x, y in zip(zip(*p), seqs)):
      yield sorted(p, key=lambda x: x[ix])

if __name__ == "__main__":

  teasers = [
  [ 'Sunday Times Teaser 2682',
  ('Drax', 'Jaws', 'Krest', 'Largo', 'Morant', 'Moth', 'Sanguinette', 'Silva'),
  ('Earth', 'Jupiter', 'Mars', 'Mercury', 'Neptune', 'Saturn', 'Uranus', 'Venus'),
  ('Brosnan', 'Casenove', 'Connery', 'Craig', 'Dalton', 'Dench', 'Lazenby', 'Moore')
  ],
  [ 'Sunday Times Teaser 2757',
  ('Gerrard', 'Lambert', 'Lampard', 'Rooney', 'Smalling',  'Welbeck'),
  ('Carberry', 'Compton', 'Robson', 'Shahzad', 'Stokes', 'Tredwell'),
  ('Cipriani', 'Launchbury', 'Parling', 'Robshaw', 'Trinder', 'Twelvetrees')
  ],
  [ 'Sunday Times Teaser 2770',
  ('Barnet', 'Exeter', 'Gillingham', 'Plymouth', 'Southend', 'Walsall'),
  ('Aguero',  'Ibrahimovic',  'Lampard', 'Neymar', 'Schweinsteiger', 'Suarez'),
  ('Conte', 'Mourinho', 'Pellegrini', 'Terim', 'Van Gaal', 'Wenger')
  ],
  [ 'Sunday Times Teaser 2800',
  ('Eastmond', 'Morgan', 'Twelvetrees', 'Webber', 'Yarde', 'Youngs'),
  ('Allen', 'Clarke', 'Croker', 'McGilchrist', 'McLean', 'Thompson'),
  ('East Sussex', 'Hampshire',  'Isle of Wight', 'Norfolk', 'Suffolk', 'Surrey')
  ],
  [ 'Sunday Times Teaser 2816',
  ('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross'),
  ('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 'Margolyes', 'Watson'),
  ('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman') 
  ] ]
  
  for t in teasers:
    print('\n{}:'.format(t[0]))
    for s in solve(t[1:], 0):
      for w in s:
        print('  ', ', '.join(w))

# Generic Solver for Sunday Times Teasers set by Graham Smithers

# that involve lists of words that have to be put into groups in

# which all pairs share letters in common (e.g. 2682, 2757, 2770,

# 2800 and 2816).

from itertools import combinations, product

from collections import defaultdict

# find combinations of words, one from each list in <seqs>, such that

# all pairs that can be formed from each combination share exactly <n>

# letters (case is ignored and letters may be repeated within words)

def compose(seqs, n):

# map the words to their sets of letters

l_ls = [{w:set(c.lower() for c in w if c.isalpha())

for w in s} for s in seqs]

# start with single item groups formed from the first sequence

groups = [[x] for x in seqs[0]]

# now consider each remaining sequence and try to combine

# its words with the groups of words formed so far

for i, s in enumerate(seqs[1:]):

# now consider each word in the sequence with each group of

# words in <groups> and, if the word shares exactly <n>

# letters with all the words in a group, we can then form

# an extended group by adding this sequence item to it

g = []

for t, a in product(groups, s):

if all(len(l_ls[j][t[j]] & l_ls[i + 1][a]) == n for j in range(i + 1)):

g.append(t + [a])

# now continue to the next sequence with the new (extended) groups

groups = g[:]

return groups

# form groups with one word from each sequence in <seqs> (each of

# the same length) and look for a way of doing this in such a way

# that all items from all sequences are used and each group formed

# is unique with respect to items from the <ix>'th sequence in <seqs>

def solve(seqs, ix):

# find all possible groupings

groups = compose(seqs, 2)

d = defaultdict(list)

# group the items for each item in the <ix>'th sequence in <seqs>

for g in groups:

d[g[ix]].append(g)

# consider all possible arrangements of the grouped items

for p in product(*(d[x] for x in seqs[ix])):

# and check all items from each sequence are present

if all(set(x) == set(y) for x, y in zip(zip(*p), seqs)):

yield sorted(p, key=lambda x: x[ix])

if __name__ == "__main__":

teasers = [

[ 'Sunday Times Teaser 2682',

('Drax', 'Jaws', 'Krest', 'Largo', 'Morant', 'Moth', 'Sanguinette', 'Silva'),

('Earth', 'Jupiter', 'Mars', 'Mercury', 'Neptune', 'Saturn', 'Uranus', 'Venus'),

('Brosnan', 'Casenove', 'Connery', 'Craig', 'Dalton', 'Dench', 'Lazenby', 'Moore')

[ 'Sunday Times Teaser 2757',

('Gerrard', 'Lambert', 'Lampard', 'Rooney', 'Smalling', 'Welbeck'),

('Carberry', 'Compton', 'Robson', 'Shahzad', 'Stokes', 'Tredwell'),

('Cipriani', 'Launchbury', 'Parling', 'Robshaw', 'Trinder', 'Twelvetrees')

[ 'Sunday Times Teaser 2770',

('Barnet', 'Exeter', 'Gillingham', 'Plymouth', 'Southend', 'Walsall'),

('Aguero', 'Ibrahimovic', 'Lampard', 'Neymar', 'Schweinsteiger', 'Suarez'),

('Conte', 'Mourinho', 'Pellegrini', 'Terim', 'Van Gaal', 'Wenger')

[ 'Sunday Times Teaser 2800',

('Eastmond', 'Morgan', 'Twelvetrees', 'Webber', 'Yarde', 'Youngs'),

('Allen', 'Clarke', 'Croker', 'McGilchrist', 'McLean', 'Thompson'),

('East Sussex', 'Hampshire', 'Isle of Wight', 'Norfolk', 'Suffolk', 'Surrey')

[ 'Sunday Times Teaser 2816',

('Dimbleby', 'Evans', 'Mack', 'Marr', 'Norton', 'Peschardt', 'Ross'),

('Arterton', 'Blunt', 'Carter', 'Jones', 'Knightley', 'Margolyes', 'Watson'),

('Bean', 'Caine', 'Cleese', 'Craig', 'De Niro', 'Neeson', 'Oldman')

] ]

for t in teasers:

print('\n{}:'.format(t[0]))

for s in solve(t[1:], 0):

for w in s:

print(' ', ', '.join(w))

Sunday Times Teaser 2816 – Chat Shows

by Graham Smithers

Published: 11 September 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta