/****** Problem 2--Cycles, Period. ************************************
 I thought this was the hardest problem of the bunch.  Others may
 disagree with me.  What made this problem hard was seeing all the
 checks that had to be made.  In particular, the sample data given in
 the problem description did not test all of these cases.
 First of all, there is no limit given on the number of observations,
 so this had to be handled dynamically; I used a linked list.
 Then, when all the data had been read in (and there is no guarantee
 that this data will be sorted in any particular order), possible
 cycle lengths are found by seeing which observations recorded the
 same value.  Since all values are unique within a period,
 the difference in observation times of the same value must be a
 multiple of the period.  Thus, to find the greatest possible period,
 you need to compute the greatest common factor of all of these
 potential periods.
 Finally, it is very possible that there is no period at all in the
 data.  Once you figure out what the period could be, you have to go
 through and make sure that all of the data does indeed abide by this
 period; if two observation times differ by a multiple of the cycle 
 length, yet the values observed are different, there is no observable
 cycle, and this should be reported.  Additionally, if there is no
 repetition in the data, there is also no observable cycle.  The test
 data supplied gives an example of the latter problem, but not one
 of the former.
 **********************************************************************/

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

typedef struct pairlist *pairlistptr;

typedef struct pairlist {   /* linked list for pairs */
 int t, v;
 pairlistptr next;
} pairlist;

int main (int argc, char **argv);
static pairlistptr readlist (void);
static int GCF (int a, int b);
static int maxcyclelength (pairlistptr p);
static int verify (pairlistptr p, int len);
static int cycle (pairlistptr p);
static void freelist (pairlistptr p);

FILE *in, *out;

/****** main **********************************************************
 This program repeatedly reads in a list of observation times and values
 and determines if a cycle is present.  If there is one, it prints the
 length of the greatest possible cycle.  If not, it prints a message
 to that effect.  The program ends when an empty list is provided.
 **********************************************************************/

int main (int argc, char **argv) {

  int c,          /* computed cycle length */
      cs;         /* case number */
      pairlistptr p;  /* the list of observations */

 in = fopen ("prob2.in","r");   /* redirect input and output */
 out = fopen ("prob2.out","w");
 for (cs=0;(p=readlist())!=NULL;) {
                         /* read in a list */
                         /* done if an empty list is read */
  if ((c = cycle (p))>0)   /* print computed cycle time */
   fprintf (out,"Case %d: cycle time = %d.\n",++cs,c);
  else
   fprintf (out,"Case %d: no cycle time can be determined.\n",++cs);
  freelist (p);    /* free up our linked list */
 }
 fclose (in);  /* close our files */
 fclose (out);
 return EXIT_SUCCESS;
}

/***** readlist *******************************************************
 readlist reads in a linked list of ordered pairs.  The routine is
 standard.  Note that we are not guaranteed any specific order
 of the pairs in the listing, thus it won't make any difference that
 they appear in the linked list in the opposite order of entry.
 **********************************************************************/

static pairlistptr readlist (void) {

  pairlistptr p,   /* The list of pairs (to be returned) */
              q;   /* temporary */
  int t, v;        /* The input values to be added to the list */

 for (p=NULL;;) {
  fscanf (in,"%d %d",&t,&v);
  if (t==0 && v==0) break;    /* if both are 0, then the list is done */
  q = malloc (sizeof (pairlist));
  q->t = t;                  /* add data to beginning of list */
  q->v = v;
  q->next = p;
  p = q;
 }
 return p;
}

/****** GCF ***********************************************************
 GCF compute the greatest common factor of two integers.  The algorithm
 below is Euclid's algorithm, the easiest method of computing it.
 **********************************************************************/

static int GCF (int a, int b) {

 return b==0 ? a : GCF (b, a%b);
}

/********* maxcyclelength *********************************************
 maxcyclelength accepts a list of pairs and returns the GCF of all
 potential cycles in the list.  If there is no repetition of data in
 the list, this function returns 0.
 This function simply uses nested loops to try every pair of values in
 the list to see if there is a potential cycle.
 **********************************************************************/

static int maxcyclelength (pairlistptr p) {

  int len;          /* the cycle length (to be returned) */
  pairlistptr q, r; /* loop iterators */

 len = 0;
 for (q=p;q!=NULL;q=q->next) /* q loops from p to the end */
  for (r=q->next;r!=NULL;r=r->next)
                     /* r loops from one past q to the end */
   if (q->v == r->v)   /* compute the GCF of this cycle with all */
    len = GCF (len,abs(q->t-r->t)); /* previously found cycles. */
 return len;
}

/******* verify *******************************************************
 verify accepts a list of pairs and a potential cycle length and
 determines whether that cycle length could possibly work.  What it
 does is check whether there are any pairs that are a full number of
 cycles apart but still have a different value.
 verify returns true if the cycle length is valid, false otherwise.
 This function simply uses nested loops to check whether all pairs
 of observations are consistent with this cycle length.
 **********************************************************************/

static int verify (pairlistptr p, int len) {

  int b;            /* boolean value (to be returned) */
  pairlistptr q, r; /* loop iterators */

 b = 1;
 for (q=p;q!=NULL && b;q=q->next)
              /* q goes from p to the end, but the loop will abort */
              /* early if b ever becomes 0 */
  for (r=q->next;r!=NULL && b;r=r->next)
             /* r goes from q to the end, but the loop will abort */
             /* early if b ever becomes 0 */
   b = abs(q->t-r->t)%len != 0 || q->v == r->v;
          /* check for validity of the pairs at q and r */
 return b;
}

/******* cycle ********************************************************
 cycle computes the maximum cycle length supported by input data in p.
 if no cycle is supported, this function returns 0.
 **********************************************************************/

static int cycle (pairlistptr p) {

  int c;  /* the cycle length */

 c = maxcyclelength (p);     /* the max cycle length */
 if (c > 0 && !verify (p,c))   /* if this length is not borne out */
  c = 0;                       /* by the data, we must assume there */
 return c;
}

/******* freelist *****************************************************
 freelist releases the data structure.  Since this routine provides no
 functionality and is included only to avoid memory leaks, you may
 wish to avoid coding this routine in a situation in which time is of
 the essence.
 **********************************************************************/

static void freelist (pairlistptr p) {

 if (p != NULL) {
  freelist (p->next);
  free (p);
 }
}