Sunday Times Teaser 2787 – Crime-Writers Convention

by Graham Smithers

Published: 21 February 2016 (link)

A group of twelve crime writers attended a convention. They were Bonfiglioli, Durrenmatt, Fyfield, Hiaasen, Highsmith, Hill, Innes, James, Knox, Le Carre, Rendell and Sayers, They sat in one long row on the stage, with Hiaasen further to the left than Hill. It turned out that, for any two sitting next to each other, there was just one letter of the alphabet that occurred (perhaps more than once) in both their surnames.

List the initial of each author from left to right along the row.

3 Comments Leave one →

Brian Gladman permalink


from itertools import combinations
from collections import defaultdict

names = ('Bonfiglioli', 'Durrenmatt', 'Fyfield', 'Hiaasen', 
         'Highsmith', 'Hill', 'Innes', 'James', 'Knox', 
         'Le Carre',  'Rendell', 'Sayers')

# map names to those with which a letter is shared
adj = defaultdict(list)
for a, b in combinations(names, 2):
  if len(set(a.lower()) & set(b.lower())) == 1:
    adj[a] += [b]
    adj[b] += [a]

# find a line of names matching the adjacency constraint
def solve(l):
  # are all placed?
  if len(l) == 12:
    yield l
  else:
    # find a name that can go next in the line
    for i in adj[l[-1]]:
      # and which has not yet been placed
      if i not in l:
        # place it and move on to the next place
        yield from solve(l + [i])

# try each name in the starting position
for name in names:
  # the leftmost name cannot be 'Hill'
  if name != 'Hill':
    # find possible sequences
    for seq in solve([name]):
      # check that 'Hiaasen' is to the left of 'Hill' 
      if seq.index('Hiaasen') < seq.index('Hill'):
        s = ' and '.join(x[0] for x in seq).replace(' and ', ', ', 10)
        print('The initial letters are {}.'.format(s))

from itertools import combinations

from collections import defaultdict

names = ('Bonfiglioli', 'Durrenmatt', 'Fyfield', 'Hiaasen',

'Highsmith', 'Hill', 'Innes', 'James', 'Knox',

'Le Carre', 'Rendell', 'Sayers')

# map names to those with which a letter is shared

adj = defaultdict(list)

for a, b in combinations(names, 2):

if len(set(a.lower()) & set(b.lower())) == 1:

adj[a] += [b]

adj[b] += [a]

# find a line of names matching the adjacency constraint

def solve(l):

# are all placed?

if len(l) == 12:

yield l

else:

# find a name that can go next in the line

for i in adj[l[-1]]:

# and which has not yet been placed

if i not in l:

# place it and move on to the next place

yield from solve(l + [i])

# try each name in the starting position

for name in names:

# the leftmost name cannot be 'Hill'

if name != 'Hill':

# find possible sequences

for seq in solve([name]):

# check that 'Hiaasen' is to the left of 'Hill'

if seq.index('Hiaasen') < seq.index('Hill'):

s = ' and '.join(x[0] for x in seq).replace(' and ', ', ', 10)

print('The initial letters are {}.'.format(s))

Jim Randell permalink

This is pretty easy puzzle to solve recursively. Here’s a Python 3 solution:


names = set((
  'bonfiglioli', 'durrenmatt', 'fyfield', 'hiaasen', 'highsmith',
  'hill', 'innes', 'james', 'knox', 'le carre', 'rendell', 'sayers',
))

# add names in rs to ns, so that adjacent names share exactly 1 letter
# ns - names assigned so far
# rs - remaining names
def solve(ns, rs):
  # are we done?
  if not rs:
    yield ns
  else:
    # consider one of the remaining names
    for n in rs:
      # don't add 'hill' before 'hiaasen'
      if n == 'hill' and 'hiaasen' not in ns: continue
      # check adjacent names share exactly 1 letter
      if not(ns) or len(set(n).intersection(ns[-1])) == 1:
        yield from solve(ns + [n], rs.difference([n]))

for ns in solve([], names):
  # output the names and the initals
  s = list(n[0].upper() for n in ns)
  print('{s} [{ns}]'.format(s=' '.join(s), ns=', '.join(ns)))

names = set((

'bonfiglioli', 'durrenmatt', 'fyfield', 'hiaasen', 'highsmith',

'hill', 'innes', 'james', 'knox', 'le carre', 'rendell', 'sayers',

))

# add names in rs to ns, so that adjacent names share exactly 1 letter

# ns - names assigned so far

# rs - remaining names

def solve(ns, rs):

# are we done?

if not rs:

yield ns

else:

# consider one of the remaining names

for n in rs:

# don't add 'hill' before 'hiaasen'

if n == 'hill' and 'hiaasen' not in ns: continue

# check adjacent names share exactly 1 letter

if not(ns) or len(set(n).intersection(ns[-1])) == 1:

yield from solve(ns + [n], rs.difference([n]))

for ns in solve([], names):

# output the names and the initals

s = list(n[0].upper() for n in ns)

print('{s} [{ns}]'.format(s=' '.join(s), ns=', '.join(ns)))

Arthur Vause permalink

My solution is similar to a mix of Brian’s and Jim’s solutions.

I thought it would be useful to write a general purpose function to find Hamiltonian paths in a graph. There are some functions already available on the web that do this, but the one that is most readily found with a google search, https://www.ieor.berkeley.edu/~faridani/python.htm, isn’t particularly efficient, as it searches all pairs of possible start and end points.


def gen_hamiltonian_paths(graph, pathsofar=[]):
  if len(pathsofar) == 0:
    for node in graph:
      for p in gen_hamiltonian_paths(graph, [node]):
        yield p
  else:      
    # attempt to extend pathsofar
    for node in graph[pathsofar[-1]]:
      if node not in pathsofar:
        if len(graph) - len(pathsofar) == 1:
          yield pathsofar + [node]
        else:
          for p in gen_hamiltonian_paths(graph, pathsofar + [node]):
            yield p
 
names = [ 'Bonfiglioli', 'Durrenmatt', 'Fyfield', 'Hiaasen', 'Highsmith', 
          'Hill', 'Innes', 'James', 'Knox', 'LeCarre', 'Rendell', 'Sayers' ]

graph = {x:[y for y in names if 
                  len(set(x.lower()) & set(y.lower())) == 1] for x in names}

for p in gen_hamiltonian_paths(graph):
  if p.index('Hill') > p.index('Hiaasen'):
    print p

def gen_hamiltonian_paths(graph, pathsofar=[]):

if len(pathsofar) == 0:

for node in graph:

for p in gen_hamiltonian_paths(graph, [node]):

yield p

else:

# attempt to extend pathsofar

for node in graph[pathsofar[-1]]:

if node not in pathsofar:

if len(graph) - len(pathsofar) == 1:

yield pathsofar + [node]

else:

for p in gen_hamiltonian_paths(graph, pathsofar + [node]):

yield p

names = [ 'Bonfiglioli', 'Durrenmatt', 'Fyfield', 'Hiaasen', 'Highsmith',

'Hill', 'Innes', 'James', 'Knox', 'LeCarre', 'Rendell', 'Sayers' ]

graph = {x:[y for y in names if

len(set(x.lower()) & set(y.lower())) == 1] for x in names}

for p in gen_hamiltonian_paths(graph):

if p.index('Hill') > p.index('Hiaasen'):

print p

Sunday Times Teaser 2787 – Crime-Writers Convention

by Graham Smithers

Published: 21 February 2016 (link)

Leave a comment to Jim Randell Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta