Sunday Times Teaser 2860 – Cricketing Greats

by Graham Smithers

Published July 16 2017 (link)

On each of the next seven evenings a different media pundit will advocate the merits of two cricketers. The pundits are Agnew, Blofeld, Dagnall, Mann, Mitchell, Norcross and Smith. The fourteen cricketers to be discussed are Ali, Anderson, Ball, Ballance, Broad, Carberry, Compton, Hales, Kerrigan, Patel, Stokes, Tredwell, Trescothick and Woakes. Each evening, looking at the names of the pundit and the two cricketers, then for any two out of the three names there are just two letters of the alphabet that occur (once or more) in both.

(a) Which cricketers will Dagnall advocate?

(b) Which cricketers will Norcross advocate?

One Comment Leave one →

Brian Gladman permalink

Here is a generic solver for grouping problems of this kind (this needs to be saved with the name grouping.py):


# Routines for solving Sunday Times Teaser "grouping" problems

from itertools import product, combinations

# combine the sequences of elements in list <seqs> into groups, one element
# from each sequence, such that the grouping function <fn> applied to every
# group returns true
def groups(seqs, fn=None, s=[]):
  # if we have completed all groups
  if not seqs[0]:
    # return the list of completed groups
    yield s
  else:
    # otherwise choose the next group of items to go with the first
    # item in the first sequence
    for grp in product(*seqs[1:]):
      # add the first item from the first sequence
      group = (seqs[0][0],) + grp
      # check that the group meets the requirements of the grouping function
      if fn(*group):
        # remove the items in this group from their respective sequences
        # and try to group the reduced length sequences
        yield from groups([seqs[0][1:]] + [tuple(z for z in x if z != y) 
                                for x, y in zip(seqs[1:], grp)], fn, s + [group])

# output a grouping
def output_groups(grp, sep=", ", end=""):
  for g in grp:
    print(sep.join(g))
  print(end)

# output all groupings
def solve(seqs, fn, sep=", ", end=""):
  for grp in groups(seqs, fn):
    output_groups(grp, sep, end)

# useful selection functions

# return the set of letters in a string, ignoring both case
# and non alphabetic characters
def ltrs(s):
  return set(x for x in s.lower() if x.isalpha())

# create a function that will check that all pairs of strings
# formed from a sequence of strings share exactly <k> letters
class shared_letters(object):
  def __init__(self, k):
    self.k = k
    
  def __call__(self, *arg):
    return all(len(ltrs(a) & ltrs(b)) == self.k 
                 for (a, b) in combinations(arg, 2))

# Routines for solving Sunday Times Teaser "grouping" problems

from itertools import product, combinations

# combine the sequences of elements in list <seqs> into groups, one element

# from each sequence, such that the grouping function <fn> applied to every

# group returns true

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

# if we have completed all groups

if not seqs[0]:

# return the list of completed groups

yield s

else:

# otherwise choose the next group of items to go with the first

# item in the first sequence

for grp in product(*seqs[1:]):

# add the first item from the first sequence

group = (seqs[0][0],) + grp

# check that the group meets the requirements of the grouping function

if fn(*group):

# remove the items in this group from their respective sequences

# and try to group the reduced length sequences

yield from groups([seqs[0][1:]] + [tuple(z for z in x if z != y)

for x, y in zip(seqs[1:], grp)], fn, s + [group])

# output a grouping

def output_groups(grp, sep=", ", end=""):

for g in grp:

print(sep.join(g))

print(end)

# output all groupings

def solve(seqs, fn, sep=", ", end=""):

for grp in groups(seqs, fn):

output_groups(grp, sep, end)

# useful selection functions

# return the set of letters in a string, ignoring both case

# and non alphabetic characters

def ltrs(s):

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

# create a function that will check that all pairs of strings

# formed from a sequence of strings share exactly <k> letters

class shared_letters(object):

def __init__(self, k):

self.k = k

def __call__(self, *arg):

return all(len(ltrs(a) & ltrs(b)) == self.k

for (a, b) in combinations(arg, 2))

And here is a solution using it:


from itertools import combinations
from grouping import groups, output_groups, share_letters

pundits = ('Agnew',  'Blofeld',  'Dagnall',  'Mann', 'Mitchell', 'Norcross', 'Smith')

players = ('Ali',  'Anderson', 'Ball',  'Ballance', 'Broad',  'Carberry',  'Compton', 
           'Hales', 'Kerrigan', 'Patel', 'Stokes', 'Tredwell', 'Trescothick', 'Woakes')

for p1 in combinations(players, 7):
  p2 = tuple(x for x in players if x not in p1)
  for s in groups([pundits, p1, p2], share_letters(2)):
    output_groups(s)
    exit()

from itertools import combinations

from grouping import groups, output_groups, share_letters

pundits = ('Agnew', 'Blofeld', 'Dagnall', 'Mann', 'Mitchell', 'Norcross', 'Smith')

players = ('Ali', 'Anderson', 'Ball', 'Ballance', 'Broad', 'Carberry', 'Compton',

'Hales', 'Kerrigan', 'Patel', 'Stokes', 'Tredwell', 'Trescothick', 'Woakes')

for p1 in combinations(players, 7):

p2 = tuple(x for x in players if x not in p1)

for s in groups([pundits, p1, p2], share_letters(2)):

output_groups(s)

exit()

However a dedicated solution is much faster:


from collections import defaultdict
from itertools import combinations

pundits = ('Agnew',  'Blofeld',  'Dagnall',  'Mann', 'Mitchell', 
           'Norcross', 'Smith')

players = ('Ali',  'Anderson', 'Ball',  'Ballance', 'Broad',  
           'Carberry',  'Compton', 'Hales', 'Kerrigan', 'Patel', 
           'Stokes', 'Tredwell', 'Trescothick', 'Woakes')

# return the set of letters in a string, ignoring both case
# and non alphabetic characters
def ltrs(s):
  return set(x for x in s.lower() if x.isalpha())

# for each pundit compile the set of players whose
# names share two letters with the pundit's name
pu2pls = defaultdict(set)
for pu in pundits:
  pu_set = ltrs(pu)
  for pl in players:
    if len(pu_set & ltrs(pl)) == 2:
      pu2pls[pu].add(pl)

# find solutions for the pundits in <pu>, compiling groups
# in <grps> and the players so far associated in <plyrs>
def groups(pu, pu2pls, grps=[], plyrs=set()):
  # if we completed all pundits
  if not pu:
    # ... return the resulting groups
    yield grps
  else:
    # try all combinations of two players for this pundit
    for p1, p2 in combinations(pu2pls[pu[0]] - plyrs, 2):
      # check that the players names share two letters
      if len(ltrs(p1) & ltrs(p2)) == 2:
        # continue to the next pundit
        yield from groups(pu[1:], pu2pls, grps + [(pu[0], p1, p2)], 
                          plyrs.union([p1, p2]))

# output mappings from pundits to two players      
for grp in groups(pundits, pu2pls):
  for g in grp:
    print(', '.join(g))

from collections import defaultdict

from itertools import combinations

pundits = ('Agnew', 'Blofeld', 'Dagnall', 'Mann', 'Mitchell',

'Norcross', 'Smith')

players = ('Ali', 'Anderson', 'Ball', 'Ballance', 'Broad',

'Carberry', 'Compton', 'Hales', 'Kerrigan', 'Patel',

'Stokes', 'Tredwell', 'Trescothick', 'Woakes')

# return the set of letters in a string, ignoring both case

# and non alphabetic characters

def ltrs(s):

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

# for each pundit compile the set of players whose

# names share two letters with the pundit's name

pu2pls = defaultdict(set)

for pu in pundits:

pu_set = ltrs(pu)

for pl in players:

if len(pu_set & ltrs(pl)) == 2:

pu2pls[pu].add(pl)

# find solutions for the pundits in <pu>, compiling groups

# in <grps> and the players so far associated in <plyrs>

def groups(pu, pu2pls, grps=[], plyrs=set()):

# if we completed all pundits

if not pu:

# ... return the resulting groups

yield grps

else:

# try all combinations of two players for this pundit

for p1, p2 in combinations(pu2pls[pu[0]] - plyrs, 2):

# check that the players names share two letters

if len(ltrs(p1) & ltrs(p2)) == 2:

# continue to the next pundit

yield from groups(pu[1:], pu2pls, grps + [(pu[0], p1, p2)],

plyrs.union([p1, p2]))

# output mappings from pundits to two players

for grp in groups(pundits, pu2pls):

for g in grp:

print(', '.join(g))

Sunday Times Teaser 2860 – Cricketing Greats

by Graham Smithers

Published July 16 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta