Enigmatic Code

Programming Enigma Puzzles

Enigma 2: Roots

From New Scientist #1144, 1st March 1979 [link]

In search of roots, Joe Soap hired a genealogist to trace his famiy tree. Results were plentiful but fragmentary. “You are descended from a Norfolk man, who died in 1692,” the expert reported expensively. “He was one of four brothers, the oldest of whom was named Absalom. The others were Benjamin, who lived at Garston, Caleb, who married a lady called Martha, and Daniel who died of scurvy.

“Beyond that, I have only a bundle of snippets, all certainly referring to one of the brothers. There was an apothecary, who died in 1694. There are mentions of a blacksmith, who died of quinsy, and of a cooper, who wed a spinster called Kate, and of a drover, who lived at Earlham. It was not Caleb who died of rheum in 1693 but someone did. Someone married Jane and lived at Halsted. Someone else lived at Felbrigg and died in 1691. Leah’s husband died of the palsy. No one lived in more than one place — very small world in those days. But I cannot tell you more than that, I’m afraid.”

I am sure you can, however. What is there to tell about Joe Soap’s particular ancestor?

[enigma2]

2 responses to “Enigma 2: Roots

  1. Jim Randell 2 December 2011 at 2:48 pm

    Quite a verbose Enigma, but it’s a small search space, so we can just generate all the permutations and reject the ones that contradict statements in the text.

    The following Python code runs in 30ms.

    from itertools import permutations
    from enigma import printf
    
    # people and indices
    name = ('Absalom', 'Benjamin', 'Caleb', 'Daniel')
    (a, b, c, d) = (0, 1, 2, 3)
    
    # jobs, places, wives, causes
    (A, B, C, D) = ('Apothecary', 'Blacksmith', 'Cooper', 'Drover')
    (E, F, G, H) = ('Earlham', 'Fellbrig', 'Garston', 'Halsted')
    (J, K, L, M) = ('Jane', 'Kate', 'Leah', 'Martha')
    (P, Q, R, S) = ('Palsy', 'Quinsy', 'Rheum', 'Scurvy')
    
    for place in permutations((E, F, G, H), 4):
      # "Benjamin lived at Garston"
      if place[b] != G: continue
      for wife in permutations((J, K, L, M), 4):
        # "Caleb married Martha"
        if wife[c] != M: continue
        # "Someone married Jane and lived at Halsted"
        if place[wife.index(J)] != H: continue
        for cause in permutations((P, Q, R, S), 4):
          # "Daniel died of scurvy"
          if cause[d] != S: continue
          # "It was not Caleb who died of rheum"
          if cause[c] == R: continue
          # "Leah's husband died of palsy"
          if wife[cause.index(P)] != L: continue
          for died in permutations((1691, 1692, 1693, 1694), 4):
            # "Someone died of rheum in 1693"
            if died[cause.index(R)] != 1693: continue
            # "Someone lived at Felbrigg and died in 1691"
            if died[place.index(F)] != 1691: continue
    
            job = ['?'] * 4
            # "an apothecary who died in 1694"
            job[died.index(1694)] = A
            # "a blacksmith who died of quinsy"
            job[cause.index(Q)] = B
            # "a cooper who wed Kate"
            job[wife.index(K)] = C
            # "a drover who lived at Earlham"
            job[place.index(E)] = D
            if '?' in job: continue
    
            for x in zip(name, place, wife, job, died, cause):
              printf("{x[0]}: place={x[1]} wife={x[2]} job={x[3]} died={x[4]} cause={x[5]}")
    

    Solution: Absalom lived in Earlham, married Leah, was a Drover, and died in 1692 of Palsy.

  2. geoffrounce 10 July 2016 at 8:20 pm

    This Enigma and the Zebra puzzle seemed to have a similar number of logic constraints.
    I amended Hakan’s model for the Zebra puzzle to find a solution for this Enigma.
    It solves this Enigma in a reasonable run- time and agrees with Jim’s solution.

     % Based on a  MiniZinc solution by Hakan for the "Who owns the zebra ?" puzzle.
    % include "globals.mzn"; 
    
    % converts a binary matrix to a number array
    predicate binmatrix2num(array[int,int] of var int: x, array[int] of var int: nums) =
      forall(i in index_set_1of2(x), j in index_set_2of2(x)) (
         nums[i] = j <-> x[i,j] = 1
      );
    
    % NAMES 
    int: Absalom = 1;
    int: Benjamin = 2;
    int: Caleb = 3;
    int: Daniel = 4;
    set of int: NAME = 1..4;  
    array[1..4] of var 1..4: names;
    
    % JOBS 
    int: Apothecary = 1;
    int: Blacksmith = 2;
    int: Cooper = 3;
    int: Drover = 4;
    
    set of int: JOB = 1..4;      
    array[1..4] of var 1..4: jobs;
    
    % PLACES 
    int: Earlham = 1;
    int: Fellbrig = 2;
    int: Garston = 3;
    int: Halstead = 4;
    
    set of int: PLACE = 1..4;      
    array[1..4] of var 1..4: places;
    
    % WIVES
    int: Jane = 1;
    int: Kate = 2;
    int: Leah = 3;
    int: Martha = 4;
    
    set of int: WIFE = 1..4;      
    array[1..4] of var 1..4: wives;
    
    % CAUSES  
    int: Palsy = 1;
    int: Quinsy = 2;
    int: Rheum = 3;
    int: Scurvy = 4;
    
    set of int: CAUSE = 1..4;      
    array[1..4] of var 1..4: causes;
    
    % YEARS 
    int: Y1691 = 1;
    int: Y1692 = 2;
    int: Y1693 = 3;
    int: Y1694 = 4;
    
    set of int: YEAR = 1..4;      
    array[1..4] of var 1..4: years;
    
    % Set up the 2d binary arrays
    %
    % names/places
    array[NAME, PLACE] of var 0..1: place;
    constraint forall(n in NAME) (sum(p in PLACE) (place[n,p]) = 1)
    /\ forall(p in PLACE) (sum(n in NAME) (place[n,p]) = 1);
    
    % names/jobs
    array[NAME, JOB] of var 0..1: job;
    constraint forall(n in NAME) (sum(j in JOB) (job[n,j]) = 1)
    /\ forall(j in JOB) (sum(n in NAME) (job[n,j]) = 1);
    
    % names/wives
    array[NAME, WIFE] of var 0..1: wife;
    constraint forall(n in NAME) (sum(w in WIFE) (wife[n,w]) = 1)
    /\ forall(w in WIFE) (sum(n in NAME) (wife[n,w]) = 1);
    
    % names/causes
    array[NAME, CAUSE] of var 0..1: cause;
    constraint forall(n in NAME) (sum(c in CAUSE) (cause[n,c]) = 1)
    /\ forall(c in CAUSE) (sum(n in NAME) (cause[n,c]) = 1);
    
    % names/years
    array[NAME, YEAR] of var 0..1: year;
    constraint forall(n in NAME) (sum(y in YEAR) (year[n,y]) = 1)
    /\ forall(y in YEAR) (sum(n in NAME) (year[n,y]) = 1);
    
    % Specific constraints
    % --------------------
    % Benjamin lived in Garston 
    constraint place[2, Garston] = 1;  
    
    % Caleb married Martha;
    constraint wife[3, Martha] = 1;   
    
    % Someone married Jane and lived at Halstead
    constraint forall(n in NAME) (wife[n,1] = place[n,4]);
    
    % Daniel died of scurvy
    constraint cause[4,Scurvy] = 1;   
    
    % It was not Caleb who died of Rheum
    constraint cause[3,Rheum] = 0;
    
    % Leah's husband died of palsy
    constraint forall(n in NAME) (wife[n,3] = cause[n,1]);
    
    % Someone died of rheum in 1693
    constraint forall(n in NAME) (cause[n,3] = year[n,3]);
    
    % Someone lived in Fellbrig and died in 1691
    constraint forall(n in NAME) (place[n,2] = year[n,1]);
    
    % An apothecary, who died in 1694
    constraint forall(n in NAME) (job[n,1] = year[n,4]);
    
    % A blacksmith, who died of quinsy 
    constraint forall(n in NAME) (job[n,2] = cause[n,2]);
    
    % A cooper, who wed a spinster called Kate
    constraint forall(n in NAME) (job[n,3] = wife[n,2]);
    
    % A drover, who lived at Earlham
    constraint forall(n in NAME) (job[n,4] = place[n,1]);
    
    % for displaying the result
    constraint binmatrix2num(place, places) /\ binmatrix2num(job, jobs)
    /\ binmatrix2num(wife, wives) /\binmatrix2num(cause, causes)
    /\ binmatrix2num(year, years);
    
    solve satisfy;
    
    output [ 
      "Places   : ", show(places), "\n",
      "Jobs     : ", show(jobs), "\n",
      "Wives    : ", show(wives), "\n",
      "Causes   : ", show(causes), "\n",
      "Years    : ", show(years), "\n",
           ];
    
    % Output
    % ------ 
    % Places   : [1, 3, 2, 4] 
    % Jobs     : [4, 3, 2, 1] 
    % Wives    : [3, 2, 4, 1]
    % Causes   : [1, 3, 2, 4]
    % Years    : [2, 3, 1, 4]
    % ----------
    % Finished in 80msec
    
    % Vertical columns translate to names/details as follows:
    % ------------------------------------------------------
    % ANSWER:
    %  Name      Place    Job  Wife  Cause  Year
    %  ----      -----    ---  ----  -----  ----
    % Absalom, Earlham, Drover,Leah, Palsy, 1692 
    
    % Other column name details below:
    % Benjamin, Garston, Cooper, Kate, Rheum, 1693
    % Caleb, Fellbrig, Blacksmith, Martha, Quinsy, 1691
    % Daniel, Halstead, Apothecary, Jane, Scurvy, 1694
    %
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: