Enigmatic Code

Programming Enigma Puzzles

Enigma 307: Seven a side

From New Scientist #1455, 9th May 1985 [link]

The team of seven has remained unchanged since 1981. The Chancellor described the annual team photographs to me as follows:

1981: Fred, Graham, Hermann, Jack; and men from Trinity, Unity and Varsity.
1982: Ken, Fred, Graham; and men from Unity, Varsity, Westminster and Sanctity.
1983: Graham, Hermann, Jack, Ken; and men from Varsity, Sanctity and Trinity.
1984: Jack, Ken, Fred; and men from Westminster, Unity, Trinity and Sanctity.

“Can you match up the names and colleges?”

“Surely”, I said, “there is some duplication, isn’t there?”

“Yes. There are three men of the same name. But there are not three men from one college”.

I found I still couldn’t do a complete matching, but I could say with certainty that ______ college had two men in the team.

Which college, and which two names?

[enigma307]

Advertisements

2 responses to “Enigma 307: Seven a side

  1. Jim Randell 2 September 2015 at 8:28 am

    This Python program examines all assignments of names to colleges. It runs in 1.4s.

    from itertools import product, combinations, permutations
    from enigma import uniq, printf
    
    # names
    names = 'FGHJK'
    
    # colleges
    colleges = 'STUVW'
    
    # statement templates
    templates = (
      ('F?', 'G?', 'H?', 'J?', '?T', '?U', '?V'),
      ('K?', 'F?', 'G?', '?U', '?V', '?W', '?S'),
      ('G?', 'H?', 'J?', 'K?', '?V', '?S', '?T'),
      ('J?', 'K?', 'F?', '?W', '?U', '?T', '?S'),
    )
    
    # generate pairs matching names <ns> to colleges <cs>
    def generate(ns, cs):
      for s in uniq(tuple(sorted(zip(ns, x))) for x in permutations(cs)):
        yield s
    
    # match the sequence <s> against the templates <ts>
    def match(s, ts):
      # are we done?
      if not ts:
        return True
      # match the next pair in the template
      (nt, ct) = ts[0]
      for (i, (ns, cs)) in enumerate(s):
        if (nt == '?' or nt == ns) and (ct == '?' or ct == cs) and match(s[:i] + s[i + 1:], ts[1:]):
          return True
      return False
    
    # choose one of the names to use three times and two of the colleges to be used twice
    for ((c1, c2), n3) in product(combinations(colleges, 2), names):
      # now assign names to colleges
      for s in generate(names + n3 * 2, colleges + c1 + c2):
        # do they match the templates
        if all(match(s, t) for t in templates):
          # output a solution
          printf("{s}", s=' '.join(n + c for (n, c) in s))
    

    Solution: It is certain that Westminster College has two men in the team. They are Graham and Jack.

    There are two possible scenarios:

    Fred (Sanctity)
    Fred (Trinity)
    Fred (Varsity)
    Graham (Westminster)
    Hermann (Unity)
    Jack (Westminster)
    Ken (Unity)

    Fred (Sanctity)
    Graham (Westminster)
    Hermann (Sanctity)
    Jack (Westminster)
    Ken (Trinity)
    Ken (Unity)
    Ken (Varsity).

    Each possibility has three men with the same name (three Freds in the first case and three Kens in the second one), and two colleges with two men (Westminster and Unity in the first case, Sanctity and Westminster in the second).

  2. arthurvause 7 September 2015 at 1:33 pm

    I found this quite an intricate Enigma to code. Some preliminary analysis can identify the colleges attended by the 3 men with the same name:

    If K is the triple name, then 1981 implies 3 K’s attend T,U,V

    If J is the triple name, then 1982 implies 3 J’s attend 3 of U,V,W,S
    1981 implies 2 J’s attend 2 of T,U,V, therefore U,V.
    1983 implies 2 J’s attend 2 of V,S,T, therefore V,S
    3 J’s must attend U,V,S

    If H is the triple name, 1982 implies 3 H’s attend 3 of U,V,W,S
    1981 implies 2 H’s attend 2 of T,U,V, therefore U,V
    1983 implies 2 H’s attend 2 of S,T,V, therefore S,V
    3 H’s attend S,U,V

    If F is the triple name, 1983 implies 3 F’s attend S,T,V

    If G is the triple name, 1984 implies 3 G’s attend 3 of S,T,U,W
    1981 implies 2 G’s attend 2 of T,U,V, therefore T,U
    1983 implies 2 G’s attend 2 of V,S,T, therefore S,T
    3 G’s must attend S,T,U

    So, some code:

    from itertools import permutations, combinations
    names = set(list('FGHJK'))
    colleges = set(list('STUVW'))
    
    triples = {'K':'TUV', 'J':'UVS', 'H':'SUV', 'F':'STV', 'G':'STU'}
    
    years = ( (set(list('FGHJ')),set(list('TUV'))),
              (set(list('FGK')),set(list('UVWS'))),
              (set(list('GHJK')),set(list('VST'))),
              (set(list('FJK')),set(list('STUW'))))
    
    def valid( pairs ):
    
      for (men,colleges) in years:
        namematch = [ (m,c) for (m,c) in pairs if m in men ]
        collmatch = [ (m,c) for (m,c) in pairs if c in colleges ]
    
        if all( set([ m for (m,c) in x ]) != men
                or set( [c for (m,c) in collmatch if (m,c) not in x]) != colleges
                for x in combinations(namematch,len(men)) ):
          return
        
      print pairs
    
    for tname in triples:
        singlenames = names - set((tname,))
        triplecolleges = set(list(triples[tname]))
        sevennames = list(singlenames) + [tname]*3
    
        singlenamecolleges = list(colleges - triplecolleges)*2 + list(triplecolleges)
        for c in set(permutations(singlenamecolleges,4)):
            pairs = zip( sevennames, list(c) + list(triplecolleges) )
            valid( pairs )
    

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: