Sunday Times Teaser 2831 – Nine Ladies Dancing

by Victor Bryant

Published: 25 December 2016 (link)

On the ninth day of Christmas the ladies Anne, Bella, Cary, Debbie, Eileen, Fran, Gill, Honor and Iris entered a dancing competition. In some order they had labels ‘One’, ‘Two’, ‘Three’, ‘Four’, ‘Five’, ‘Six’, ‘Seven’, ‘Eight’ and ‘Nine’ on their backs. They each danced a different dance chosen from cha-cha, charleston, foxtrot, jive, polka, quickstep, samba, twist and waltz.

For any lady’s name and label there was just one letter of the alphabet that occurred (once or more) in both. The same was true for any lady’s name and their dance, and also for any lady’s label and dance.

In alphabetical order of their names, what are the numbers of the nine ladies?

2 Comments Leave one →

Brian Gladman permalink

A chance to play with Python 3.6 that was released couple of days ago.


from itertools import combinations, product

names = ( 'Anne', 'Bella', 'Cary', 'Debbie', 'Eileen', 
          'Fran',  'Gill',  'Honor', 'Iris' ) 


labels = ( 'One',  'Two',  'Three',  'Four',  'Five',  'Six', 
           'Seven', 'Eight', 'Nine' )

dances = ( 'cha-cha',  'charleston',  'foxtrot', 'jive', 'polka',
           'quickstep', 'samba', 'twist',  'waltz' )

# group names, one from the list <nm> and one each from the lists in 
# <lc> such that all pairs of names within each group return true
# for the function <fn>
def solve(nm, lc, fn, tr=[]):
  # if all groups have been composed
  if not nm:
    yield tr
  else:
    # list all the names in each of the lists in <lc> that are
    # compatible with the first name in <nm>
    ll = [[x for x in y if fn(nm[0], x)] for y in lc]
    # consider all combinations of these names
    for gr in product(*ll):
      # and then filter only those combinations in which all pairs of
      # names are compatible
      if all(fn(a, b) for a, b in combinations(gr, 2)):
        # for each match remove the matching names from <nm> and from 
        # from the lists in <lc> and continue to the next name in nm
        t = [[x for x in b if x != a]  for a, b in zip(gr, lc)]
        yield from solve (nm[1:], t, fn, tr + [(nm[0],) + gr])

# rtuen true if two names have only one letter in common
def fn(x, y):
  return len(set(x.lower()).intersection(y.lower())) == 1

for tr in solve(names, [labels, dances], fn):
  for t in tr:
    print(t)

from itertools import combinations, product

names = ( 'Anne', 'Bella', 'Cary', 'Debbie', 'Eileen',

'Fran', 'Gill', 'Honor', 'Iris' )

labels = ( 'One', 'Two', 'Three', 'Four', 'Five', 'Six',

'Seven', 'Eight', 'Nine' )

dances = ( 'cha-cha', 'charleston', 'foxtrot', 'jive', 'polka',

'quickstep', 'samba', 'twist', 'waltz' )

# group names, one from the list <nm> and one each from the lists in

# <lc> such that all pairs of names within each group return true

# for the function <fn>

def solve(nm, lc, fn, tr=[]):

# if all groups have been composed

if not nm:

yield tr

else:

# list all the names in each of the lists in <lc> that are

# compatible with the first name in <nm>

ll = [[x for x in y if fn(nm[0], x)] for y in lc]

# consider all combinations of these names

for gr in product(*ll):

# and then filter only those combinations in which all pairs of

# names are compatible

if all(fn(a, b) for a, b in combinations(gr, 2)):

# for each match remove the matching names from <nm> and from

# from the lists in <lc> and continue to the next name in nm

t = [[x for x in b if x != a] for a, b in zip(gr, lc)]

yield from solve (nm[1:], t, fn, tr + [(nm[0],) + gr])

# rtuen true if two names have only one letter in common

def fn(x, y):

return len(set(x.lower()).intersection(y.lower())) == 1

for tr in solve(names, [labels, dances], fn):

for t in tr:

print(t)

Wishing you all a Happy Christmas and New Year.

Jim Randell permalink

Recent examples of this kind of puzzle have been set by Graham Smithers, but this one is by Victor Bryant.

Back in September, when Teaser 2816 [ https://brg.me.uk/?page_id=4078#comment-685 ] came out, I wrote some generic code to solve this kind of puzzle. Here it is packaged into a module called grouping.py:


# routines for solving Sunday Times Teaser "grouping" problems

from itertools import product, combinations

# 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 to go with category 0
    for v in product(*(enumerate(x) for x in vs[1:])):
      # find indices and elements of the other categories
      (js, t) = zip(*v)
      # the full group is
      group = (vs[0][0],) + t
      # check the group
      if fn(*group):
        # solve for the remaining elements
        yield from groups([vs[0][1:]] + [x[:j] + x[j + 1:] for (x, j) in zip(vs[1:], js)], fn, s + [group])

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

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


# useful selection functions

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

# return a check function that checks each pair of values shares exactly <k> letters
def share_letters(k):
  fn = ((lambda x: x == k) if type(k) is int else k)
  # check each pair of values shares exactly <k> different letters
  def check(*vs):
    return all(fn(len(letters(a).intersection(letters(b)))) for (a, b) in combinations(vs, 2))
  return check

# routines for solving Sunday Times Teaser "grouping" problems

from itertools import product, combinations

# 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 to go with category 0

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

# find indices and elements of the other categories

(js, t) = zip(*v)

# the full group is

group = (vs[0][0],) + t

# check the group

if fn(*group):

# solve for the remaining elements

yield from groups([vs[0][1:]] + [x[:j] + x[j + 1:] for (x, j) in zip(vs[1:], js)], fn, s + [group])

# output a grouping

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

for g in gs:

print(sep.join(g))

print(end)

# output all groupings

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

for gs in groups(vs, fn):

output_groups(gs, sep, end)

# useful selection functions

# return the set of letters in a string

def letters(s):

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

# return a check function that checks each pair of values shares exactly <k> letters

def share_letters(k):

fn = ((lambda x: x == k) if type(k) is int else k)

# check each pair of values shares exactly <k> different letters

def check(*vs):

return all(fn(len(letters(a).intersection(letters(b)))) for (a, b) in combinations(vs, 2))

return check

And here is a program that uses this module to solve the Teaser in 114ms.


import grouping

# categories for this puzzle
names = ( 'Anne', 'Bella', 'Cary', 'Debbie', 'Eileen', 'Fran', 'Gill', 'Honor', 'Iris' )
labels = ( 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine' )
dances = ( 'cha-cha', 'charleston', 'foxtrot', 'jive', 'polka', 'quickstep', 'samba', 'twist', 'waltz' )

# match the categories into groups such that each pair in each group shares exactly 1 letter
grouping.solve([names, labels, dances], grouping.share_letters(1))

import grouping

# categories for this puzzle

names = ( 'Anne', 'Bella', 'Cary', 'Debbie', 'Eileen', 'Fran', 'Gill', 'Honor', 'Iris' )

labels = ( 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine' )

dances = ( 'cha-cha', 'charleston', 'foxtrot', 'jive', 'polka', 'quickstep', 'samba', 'twist', 'waltz' )

# match the categories into groups such that each pair in each group shares exactly 1 letter

grouping.solve([names, labels, dances], grouping.share_letters(1))

Sunday Times Teaser 2831 – Nine Ladies Dancing

by Victor Bryant

Published: 25 December 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta