Enigmatic Code

Programming Enigma Puzzles

Tantalizer 482: Lapses from grace

From New Scientist #1033, 6th January 1977 [link]

An air of rare humility pervades the Common Room at St. Aletheia’s tonight. The seven inmates overdid the post-prandial gin and rashly confessed their sins to one another. Each owned to a different pair of the deadly ones and each sin turned out to have claimed a different pair of victims.

Constance, Emily and Flavia have no sin in common to any two of them. Beatrice, Deborah, Emily and Gertrude confessed to all seven between them. Alice and Gertrude admitted to sloth; Deborah and Emily to lust. Alice is not given to pride nor Beatrice to avarice nor Flavia to either pride or intemperance. Constance, who owned to anger, has a sin in common with Deborah, who did not.

Which pair has fallen prey to intemperance and which pair to envy?

[tantalizer482]

Advertisements

3 responses to “Tantalizer 482: Lapses from grace

  1. Jim Randell 17 May 2017 at 8:33 am

    To save having to decide which constraints to consider first, I expressed the puzzle as a set of MiniZinc constraints and let the solver do the hard work.

    Here’s the MiniZinc model.

    % labels for people
    set of int: People = 1..7;
    
    int: A = 1; % Alice
    int: B = 2; % Beatrice
    int: C = 3; % Constance
    int: D = 4; % Deborah
    int: E = 5; % Emily
    int: F = 6; % Flavia
    int: G = 7; % Gertrude
    
    % labels for sins
    set of int: Sins = 1..7;
    
    int: Sl = 1; % sloth
    int: Lu = 2; % lust
    int: Pr = 3; % pride
    int: Av = 4; % avarice
    int: In = 5; % intemperance
    int: An = 6; % anger
    int: En = 7; % envy
    
    % decision table
    array[Sins, People] of var 0..1: x;
    
    % each person admits to two different sins
    constraint forall (j in People) ((sum (i in Sins) (x[i, j])) = 2);
    constraint forall (j, k in People where j < k) (exists (i in Sins) (x[i, j] != x[i, k]));
    
    % each sin claims two different people
    constraint forall (i in Sins) ((sum (j in People) (x[i, j])) = 2);
    constraint forall (i, k in Sins where i < k) (exists (j in People) (x[i, j] != x[k, j]));
    
    % C, E, F have no sin in common
    constraint forall (i in Sins) (x[i, C] + x[i, E] + x[i, F] < 2);
    
    % B, D, E, G include all sins
    constraint forall (i in Sins) (x[i, B] + x[i, D] + x[i, E] + x[i, G] > 0);
    
    % A, G admitted to sloth
    constraint x[Sl, A] = 1;
    constraint x[Sl, G] = 1;
    
    % D, E admitted to lust
    constraint x[Lu, D] = 1;
    constraint x[Lu, E] = 1;
    
    % A did not admit to pride
    constraint x[Pr, A] = 0;
    
    % B did not admit to avarice
    constraint x[Av, B] = 0;
    
    % F did not admit to pride or intemperance
    constraint x[Pr, F] = 0;
    constraint x[In, F] = 0;
    
    % C admitted to anger
    constraint x[An, C] = 1;
    
    % D did not admit to anger
    constraint x[An, D] = 0;
    
    % but C and D have a sin in common
    constraint exists (i in Sins) (x[i, C] + x[i, D] = 2);
    
    solve satisfy;
    

    On its own the model executes in 84ms (using the mzn-gecode -a solver), but the output of the decision table needs to be tidied up to make sense of it. I used the minizinc.py wrapper to let me format the solution using Python.

    This Python program executes in 152ms.

    from enigma import join, printf
    from minizinc import MiniZinc
    
    # labels for the people
    people = ( 'Alice', 'Beatrice', 'Constance', 'Deborah', 'Emily', 'Flavia', 'Gertrude' )
    
    # labels for the sins
    sins = ( 'sloth', 'lust', 'pride', 'avarice', 'intemperance', 'anger', 'envy' )
    
    # create the MiniZinc model
    p = MiniZinc("tantalizer482.mzn")
    
    # solve it
    for (x,) in p.solve(result='x', solver="mzn-gecode -a"):
      # output the solution table
      for (i, sin) in enumerate(sins, start=1):
        ps = list(p for (j, p) in enumerate(people, start=1) if x[i][j])
        printf("{sin:13s}: {ps}", ps=join(ps, sep=", "))
      printf()
    

    Solution: Alice and Emily admitted to intemperance. Beatrice and Flavia admitted to envy.

    The full results are:

    Alice: sloth and intemperance.
    Beatrice: anger and envy.
    Constance: pride and anger.
    Deborah: lust and pride.
    Emily: lust and intemperance.
    Flavia: avarice and envy.
    Gertrude: sloth and avarice.

    I found the constraints that each person has a different pair of sins (and each sin a different pair of people) the hardest to express. I expressed them as “different people cannot have the same values for the sins” (i.e. for each pair of people there must be a sin that one of them admits to and the other doesn’t), and the second constraint is handled similarly. Disappointingly we don’t get additional solutions if these constraints are not included in the model, so they are superfluous.

  2. arthurvause 18 May 2017 at 12:09 am
    from itertools import combinations, permutations
    
    inmates = ( 'Alice', 'Beatrice', 'Constance', 'Deborah', 'Emily', 'Flavia', 'Gertrude' )
    
    pairs = set(x for x in combinations(inmates,2))
    pairs -= set(x for x in combinations( ('Constance', 'Emily', 'Flavia'),2))
    pairs -= set( (('Alice','Gertrude' ),('Deborah','Emily'),('Constance','Deborah')))
    pairs -= set(x for x in combinations( ('Beatrice',  'Deborah', 'Emily', 'Gertrude'),2))
    
    unattributed_inmates = ['Alice','Beatrice','Beatrice','Constance','Emily','Flavia','Flavia','Gertrude']
    unattributed_sins = ( 'pride', 'avarice', 'intemperance', 'anger', 'envy' )
    
    for x in combinations(pairs,4):
      if sorted(sum(x,())) == unattributed_inmates:
        for si in permutations( unattributed_sins,4 ):
          if 'anger' not in si:
            continue
          d = {si[i]:x[i] for i in xrange(4)}
          if 'Constance' not in d['anger']:
            continue
          if 'pride' in d and 'Alice' in d['pride']:
            continue
          if 'avarice' in d and 'Beatrice'  in d['avarice']:
            continue
          if 'pride' in d and 'Flavia' in d['pride']:
            continue
          if 'intemperance' in d and 'Flavia' in d['intemperance']:
            continue
          
          CD_sin = [x for x in unattributed_sins if x not in d][0]
          d[CD_sin]= ('Constance','Deborah')
          for s in d:
            print d[s], "have fallen prey to", s
    
  3. Brian Gladman 19 May 2017 at 10:11 am
    from itertools import combinations, permutations, product
    
    # enumerate the names
    A, B, C, D, E, F, G = range(7)
    nms = dict(enumerate(('Alice', 'Beatrice', 'Constance', 'Deborah', 
                            'Emily', 'Flavia', 'Gertrude')))
    # enumerate the sins
    an, av, en, it, lu, pr, sl = range(7)
    sns = dict(enumerate(('anger', 'avarice', 'envy', 'intemperance', 
                           'lust', 'pride', 'sloth')))
    
    # all seven sins occur among Beatrice, Deborah, Emily, Gertrude so
    # we have the following arrangement of unknown sins (*), which must
    # be permutations of anger, avarice, envy, intemperance and pride
    #   Beatrice: *, *
    #   Deborah: lust, *
    #   Emily: lust, *
    #   Gertrude: sloth, *
    s1 = {an, av, en, it, pr}
    sol_g1 = set()
    for p in permutations(s1, 3):
      # the set of sins for Beatrice, Deborah, Emily and Gertrude
      tb, td, te, tg = s1.difference(p), {lu, p[0]}, {lu, p[1]}, {sl, p[2]}
      sol_g1.add(tuple(frozenset(x) for x in (tb, td, te, tg)))
    
    # the arrangement of unknown sins among Alice, Constance and Flavia is:
    #   Alice: sloth, *
    #   Constance: anger, *
    #   Flavia: *, *
    # since each sin occurs against two names, there are 14 sins among all 
    # seven names; the first group above has all seven sins plus lust, so
    # this group must have all seven sins minus lust; so the four unknowns
    # here must be permutations of avarice, envy, intemperance and pride
    s2 = {av, en, it, pr}
    sol_g2 = set()
    for q in permutations(s2, 2):
      # the set of sins for Alice, Constance and Flavia
      ta, tc, tf = {sl, q[0]}, {an, q[1]}, s2.difference(q)
      sol_g2.add(tuple(frozenset(x) for x in (ta, tc, tf)))
      
    for (tb, td, te, tg), (ta, tc, tf) in product(sol_g1, sol_g2):
      # map names to pairs of sins
      p2s = dict(zip(range(7), (ta, tb, tc, td, te, tf, tg)))
    
      # Constance, Emily and Flavia have no sin shared by any pair
      if any(p2s[x] & p2s[y] for x, y in combinations((C, E, F), 2)):
        continue
      
      # Alice and Gertrude admit sloth, Deborah and Emily admit lust
      if not (sl in p2s[A] and sl in p2s[G] and lu in p2s[D] and lu in p2s[E]):
        continue
      
      # Alice is not proud and Beatrice is not avaricious
      if pr in p2s[A] or av in p2s[B]:
        continue
      
      # Flavia is neither intemperate nor proud
      if p2s[F].intersection([it, pr]):
        continue
      
      # Deborah shows no anger; Constance and Deborah share a sin 
      if an in p2s[D] or not p2s[C] & p2s[D]:
        continue
      
      u = [nms[x] for x in range(7) if it in p2s[x]]
      v = [nms[x] for x in range(7) if en in p2s[x]] 
      print('Intemperance: {} and {}; Envy: {} and {}.'.format(*u, *v))
      print()
      for n in range(7):
        print('{}: {}, {}'.format(nms[n], *(sns[s] for s in sorted(p2s[n]))))
    

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: