You've been hired by Gemini Labs, the world leader in human cloning, to write decision support software. At Gemini, all clones are derived from "ADAM", a genetically perfect human. Something about his DNA makes him much easier to clone than normal humans. Not all the clones of Adam are the same, though, because geneticists introduce mutations, in the form of recessive genes, to learn more about genetics. For example, Bob might be a clone of Adam with a recessive gene for baldness added. Scientists would study Bob to see what subtle effects the gene may have. Clones of Bob would carry the recessive gene, as would clones of those clones, and so on. All is well as long as no clone derived from Bob is given a second recessive baldness gene. If that were to happen, a bald clone would be produced and the Cloning Board would shut Gemini down.

The software you are to write takes cloning requests from the research staff and evaluates them for consistency and safety. A collection of requests is "inconsistent" if it includes a clone that is not descended from Adam. A collection of requests is "unsafe" if it produces a clone with two identical recessive genes.

Input Format

Your program consumes a file of cloning requests, one per line. Here is the format of a cloning request:

<request> = clone_<name>_from_<name><genelist>
<genelist> = NULL | _mutating_<gene><genes>
<genes> = NULL | _<gene><genes>
<gene> = 3 upper case alphabetical characters
<name> = 1 to 10 upper case alphabetical characters
_ = one blank

A typical cloning request is

clone BOB from ADAM mutating BLD HEM

Note: there is always exactly one space between words; the last character on a line is immediately followed by EOLN. There can be zero to ten mutations in a request. If there are no mutations in the request, the keyword "mutating" does not appear, e.g.,

clone BOB from ADAM

The input is guaranteed to satisfy the syntactic format specifications, and it is guaranteed to contain at most one cloning request per clone, i.e., "clone BOB" will appear no more than once as the beginning of an input line. Furthermore, you are to process requests as though only those definitions which precede it are in effect. Therefore, if you have the following input segment

clone BOB from ADAM
clone MIKE from TIM
clone TIM from BOB

your output would include

clone MIKE from TIM has no connection to ADAM

because at the time MIKE was cloned, there was no connection to ADAM. If an clone is not consistent and safe, then all subsequent clones from that clone should be reported as having no connection to ADAM. For example, if you have the following input segment

clone BOB from ADAM mutating BLD
clone CHARLIE from BOB mutating BLD
clone DAVID from CHARLIE

your output would include

clone BOB from ADAM is consistent and safe
clone CHARLIE from BOB was at least twice mutated with BLD
clone DAVID from CHARLIE has no connection to ADAM

You are also guaranteed that no gene is listed twice in the same request.
 

Required Output Format

Your program produces a file of the processed requests, one per line,
in the same order as they were consumed. The requests are modified
according to the following rules.
 

Sample Input

clone JOE from ADAM
clone BOB from ADAM mutating HEM
clone SAM from BOB mutating BLD
clone ED from SAM mutating BLD
clone FRANK from ED mutating HEM
clone KAIN from ABEL
clone ABEL from KAIN

Sample Output

clone JOE from ADAM is consistent and safe
clone BOB from ADAM is consistent and safe
clone SAM from BOB is consistent and safe
clone ED from SAM was at least twice mutated with BLD
clone FRANK from ED has no connection to ADAM
clone KAIN from ABEL has no connection to ADAM
clone ABEL from KAIN has no connection to ADAM

Judge's Input

clone WILLIAM from ADAM
clone BOB from ADAM mutating BLD ELB
clone SAM from ADAM mutating EYE NOS EAR LEG
clone BILL from ANN mutating LEG
clone ANN from ADAM mutating LEG
clone WILL from ANN mutating EYE
clone SUE from SAM mutating LEG
clone HILDEGARDE from SUE mutating ARM HAI FIN
clone JERRY from ADAM
clone CHARLES from HILDEGARDE
clone ABEL from JERRY mutating ARM HAI FIN LEG NOS EAR
clone CAIN from WILL mutating ARM LEG
clone GEORGE from SID mutating EYE LEG
clone SID from CAIN mutating EYE LEG
clone ENOS from ABEL mutating ABC ABD ABE ABF ABG ABH ABI ABJ ABK ABL
clone ISRAEL from ENOS mutating ABL
clone HAIFA from ENOS mutating EAR
clone ABC from ENOS mutating CAB CBB
clone BCD from ABC mutating DCB DCC
clone CDE from BCD mutating EAR DCB CBA
clone EFD from BCD mutating CBA DCB
clone EFG from BCD mutating XYZ QRS DCC EAR

Judge's Output

clone WILLIAM from ADAM is consistent and safe
clone BOB from ADAM is consistent and safe
clone SAM from ADAM is consistent and safe
clone BILL from ANN has no connection to ADAM
clone ANN from ADAM is consistent and safe
clone WILL from ANN was at least twice mutated with EYE
clone SUE from SAM was at least twice mutated with LEG
clone HILDEGARDE from SUE has no connection to ADAM
clone JERRY from ADAM is consistent and safe
clone CHARLES from HILDEGARDE has no connection to ADAM
clone ABEL from JERRY was at least twice mutated with LEG
clone CAIN from WILL has no connection to ADAM
clone GEORGE from SID has no connection to ADAM
clone SID from CAIN has no connection to ADAM
clone ENOS from ABEL has no connection to ADAM
clone ISRAEL from ENOS has no connection to ADAM
clone HAIFA from ENOS has no connection to ADAM
clone ABC from ENOS has no connection to ADAM
clone BCD from ABC has no connection to ADAM
clone CDE from BCD has no connection to ADAM
clone EFD from BCD has no connection to ADAM
clone EFG from BCD has no connection to ADAM
clone  from BCD has no connection to ADAM

Judge's solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct gene_t   {
  char   mutation[4];
} gene_t;

typedef struct person_t {
  struct person_t *next, *source;
  char     name[11];
  gene_t   genes[11];     /* 11 for a end-of-genes marker */
} person_t;

struct person_t *persons = NULL;
struct person_t *new_person;
FILE *infp, *outfp;
char source_name[11];

 
void parse_a_line(void)
{ char clone_str[6], from_str[5], mutating_str[9], temp_str[80];
  int  lead, gene_dest, i;

  new_person=(person_t*)malloc(sizeof(person_t));
  memset(&(new_person->name), 0, 11);
  new_person->next = NULL;
  for (i=0; i<11; i++)
  { memset(&(new_person->genes[i]), 0, 4); }
 
  fscanf(infp, "%s %s %s %s", &clone_str, &(new_person->name), &from_str, &source_name);
  fgets(temp_str, 80, infp);
 
  lead=0; gene_dest=0;
  if ((temp_str[0]!='\n') && (temp_str[0]))
  { sscanf(&(temp_str[0]), "%s", &mutating_str);
    lead+=9;
  }
  else return;
 
  while ((temp_str[lead]!='\n') && (temp_str[lead]))
  { sscanf(&(temp_str[lead]), "%s", &(new_person->genes[gene_dest].mutation));
    lead+=4;
    gene_dest++;
  }
  return;
}
 

void check_consistency(person_t *source_person)
{ person_t *tp2;
  int      i,j;
 
  for (i=0; new_person->genes[i].mutation[0]; i++)
  { for (tp2 = source_person; tp2; tp2 = tp2->next)
    { for (j=0; tp2->genes[j].mutation[0]; j++)
      { if (!strcmp(new_person->genes[i].mutation, tp2->genes[j].mutation))
        { fprintf(outfp, "clone %s from %s was at least twice mutated with %s\n",
                  new_person->name, source_name, new_person->genes[i].mutation);
          return;
        }
      }
    }
  }
  fprintf(outfp, "clone %s from %s is consistent and safe\n", new_person->name, source_name);
  new_person->next = persons;
  persons = new_person;
  return;
}

 
void process_line(void)
{ int found = 0;
  person_t *tp;

  parse_a_line();
  tp=persons;
 
  if (!strcmp(source_name, "ADAM"))
  { new_person->next = persons;
    persons = new_person;
    fprintf(outfp, "clone %s from %s is consistent and safe\n",
            new_person->name, source_name);
    return;
  }
 
  while (!found)
  { if (tp == NULL)
    { found = 1; }
    else
    { if (!strcmp(source_name, tp->name))
      { new_person->source=tp;
        if (new_person->genes[0].mutation[0])
        { check_consistency(tp); }
        else
        { fprintf(outfp, "clone %s from %s is consistent and safe\n",
                  new_person->name, source_name);
          new_person->next = persons;
          persons = new_person;
        }
        return;
      }
      else
      { tp=tp->next; }
    }
  }
  fprintf(outfp, "clone %s from %s has no connection to ADAM\n", new_person->name, source_name);
  return;
}

int main(void)
{
  infp=fopen("genes.dat", "r");
  outfp=fopen("genes.out","w");
 
  while (!feof(infp))
  { process_line(); }
 
  fclose(infp);
  fclose(outfp);
  return(0);
}