Enigmatic Code

Programming Enigma Puzzles

Enigma 271: Who knows whom?

From New Scientist #1418, 23rd August 1984 [link]

There were six people in the room. The farmer said “Of the remaining five people here the accountant and the chemist are friends, the accountant and the butcher are friends, the butcher and the chemist are friends, the chemist and the dentist are friends, and the butcher and the engineer are friends. No other pair of the five are friends”.

Mr Fox said: “of the five remaining people here Mr Allen and Mr Brown are friends, Mr Brown and Mr Cook are friends, Mr Cook and Mr Davies are friends, and Mr Davies and Mr Easton are friends. No other pair of the five are friends”.

Fred said: “of the five remaining people here Andrew and Brian are friends, Brian and Charles are friends, Charles and David are friends, Brian and David are friends, Andrew and Charles are friends, and David and Edward are friends. No other pair of the five are friends”.

The butcher is not called Charles nor Davies, and Charles’s surname is not Cook. Write down the names of the six people (christian name and surname) in alphabetical order of occupation.

[enigma271]

Advertisements

One response to “Enigma 271: Who knows whom?

  1. Jim Randell 7 April 2015 at 8:26 am

    This Python program runs in 79ms.

    from itertools import permutations
    from enigma import irange, printf
    
    # label the people (by occupation)
    people = (A, B, C, D, E, F) = irange(0, 5)
    
    # canonical representation of friendship relation
    def f(x, y):
      return ((x, y) if x < y else (y, x))
    
    # exclude relations that include a specific person
    def exclude(p, fs):
      return set(r for r in fs if p not in r)
    
    # friends excluding F (the farmer)
    friends1 = set(f(x, y) for (x, y) in ((A, C), (A, B), (B, C), (C, D), (B, E)))
    
    # map last name to occupation
    for ml in permutations(people):
    
      # "the Butcher is not called ... Davies"
      if ml[D] == B: continue
    
      # friends excluding Mr Fox
      friends2 = set(f(ml[x], ml[y]) for (x, y) in ((A, B), (B, C), (C, D), (D, E)))
    
      # exclude Mr Fox from friends1, and the farmer from friends2
      # and we should get the same set of friendships
      if exclude(ml[F], friends1) != exclude(F, friends2): continue
    
      # now map first name to occupation
      for mf in permutations(people):
    
        # "the Butcher is not called Charles"
        if mf[C] == B: continue
    
        # "Charles's last name is not Cook"
        if mf[C] == ml[C]: continue
    
        # friends excluding Fred
        friends3 = set(f(mf[x], mf[y]) for (x, y) in ((A, B), (B, C), (C, D), (B, D), (A, C), (D, E)))
    
        # exclude Fred from friends1, and the farmer from friends3
        if exclude(mf[F], friends1) != exclude(F, friends3): continue
    
        # exclude Fred from friends2 and Mr Fox from friends3
        if exclude(mf[F], friends2) != exclude(ml[F], friends3): continue
    
        # output the solution (as: "<job>: <first> <last>")
        s = 'ABCDEF'
        for (i, j) in enumerate(s):
          printf("{j}: {f} {l}", f=s[mf.index(i)], l=s[ml.index(i)])
        printf()
    

    Solution: Brian Cook (accountant), David Brown (butcher), Charles Fox (chemist), Fred Easton (dentist), Edward Allen (engineer), Andrew Davies (farmer).

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: