Enigmatic Code

Programming Enigma Puzzles

Enigma 396: The hostess’s problem

From New Scientist #1546, 5th February 1987 [link]

At a recent dinner party five men and their wives sat at the 10 places around the table. Men and women alternated around the table and no man sat next to his own wife. No man’s Christian name had the same initial as his surname.

Mrs Collins sat between Brian and David. Colin’s wife sat between Mr Briant and Mr Edwards. Mr Allen sat between Edward’s wife and Mrs Davidson. Brian’s wife sat next to Alan.

In the information which I’ve just given you, if two people were sitting next to each other then I have not told you about it more than once.

Which two men (Christian name and surname of each) sat next to Mrs Edwards?

[enigma396]

Advertisements

One response to “Enigma 396: The hostess’s problem

  1. Jim Randell 19 May 2017 at 9:09 am

    This Python program runs in 422ms.

    from itertools import permutations
    from enigma import irange, join, ordered, printf
    
    # check positions are next to each other
    def next_to(x, y):
      return abs(x - y) in (1, 9)
    
    # x is between y and z
    def between(x, y, z):
      return y != z and next_to(x, y) and next_to(x, z)
    
    # find a key in dictionary d that has value v
    def find(d, v):
      for (k, x) in d.items():
        if x == v: return k
      return None
    
    # first names and last names use the same initials
    names = 'ABCDE'
    
    # assign last names to the even places
    # (to eliminate duplicate solutions place Mr A at place 0 and suppose
    # place 2 is alphabetically before place 8)
    for s in permutations((2, 4, 6, 8)):
      # h: <last_name> -> <place>
      h = dict((x, p) for (x, p) in zip(names, (0,) + s))
      if find(h, 2) > find(h, 8): continue
    
      # assign first names to the even places
      for s in permutations((0, 2, 4, 6, 8)):
        # n: <first_name> -> <place>
        n = dict((x, p) for (x, p) in zip(names, s))
    
        # check no first name shares an initial with a last name
        if any(h[x] == n[x] for x in names): continue
    
        # assign the wives to the odd places
        for s in permutations((1, 3, 5, 7, 9)):
          # w: <last_name> -> <place>
          w = dict((x, p) for (x, p) in zip(names, s))
    
          # check none of the wives are sitting next to their husbands
          if any(next_to(w[x], h[x]) for x in names): continue
    
          # check the remaining conditions:
    
          # "Mrs C sat between B and D"
          (x1, y1, z1) = (w['C'], n['B'], n['D'])
          if not between(x1, y1, z1): continue
    
          # "C's wife sat between Mr B and Mr E"
          (x2, y2, z2) = (w[find(h, n['C'])], h['B'], h['E'])
          if not between(x2, y2, z2): continue
    
          # "Mr A sat between E's wife and Mrs D"
          (x3, y3, z3) = (h['A'], w[find(h, n['E'])], w['D'])
          if not between(x3, y3, z3): continue
    
          # "B's wife sat next to A"
          (x4, y4) = (w[find(h, n['B'])], n['A'])
          if not next_to(x4, y4): continue
    
          # no adjacent pair is mentioned twice
          pairs = list(ordered(x, y) for (x, y) in (
            (x1, y1), (x1, z1),
            (x2, y2), (x2, z2),
            (x3, y3), (x3, z3),
            (x4, y4),
          ))
          if len(set(pairs)) != 7: continue
    
          # make the seating plan
          t = list()
          for i in irange(0, 9):
            if i % 2 == 0:
              p = find(n, i) + ' ' + find(h, i)
            else:
              p = 'Mrs ' + find(w, i)
            t.append(p)
          printf("[table = [{t}]]", t=join(t, sep=', '))
    
          # who is sitting either side of Mrs E?
          k = 'Mrs E'
          i = t.index(k)
          (p1, p2) = (t[(i - 1) % 10], t[(i + 1) % 10])
    
          printf("{k} is between {p1} and {p2}")
          printf()
    

    Solution: Mrs Edwards sat between Alan Collins and Edward Briant.

    The positions occupied going round the table are as follows:

    Colin Allen
    Mrs Davidson
    Alan Collins
    Mrs Edwards
    Edward Briant
    Mrs Allen
    David Edwards
    Mrs Collins
    Brian Davidson
    Mrs Briant

    No information is given about the first names of the wives.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: