A Solver for “Grouping” Teasers

Graham Smithers seems to specialise in teasers in which names have to be grouped together based on shared letters. Here is my solver for puzzles of this type (you can download it here grouping.py).


# Routines for solving Sunday Times Teaser "grouping" problems

from itertools import product, combinations

# combine the sequences of elements in list  into groups, one element
# from each sequence, such that the grouping function  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 into groups, one element

# from each sequence, such that the grouping function 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))

A Solver for “Grouping” Teasers

Recent Posts

Recent Comments

Archives

Categories

Meta