/* Jason Grout, grout@math.byu.edu */
/* 11 July 2002 */
/* Noweb sources may be obtained by emailing Jason Grout */



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

int SEQUENCE_LENGTH;
int MAX_VALUE;
int *sequence;
int *gamma;

#define CANCELED -1
#define MAX_DIVISORS 10

int NUM_DIVISORS;
int divisors[MAX_DIVISORS];
int cosetElements[MAX_DIVISORS];

int
checkGamma (void)
{
  int gammaElementsLeft = SEQUENCE_LENGTH;
  int currentDivisor;
  int cosetElementsLeft;
  int i;
  int j;

  for (i = 0; i < SEQUENCE_LENGTH; i++)
    {
      if (gamma[i] == CANCELED)
	continue;

      /*
       * Loop through all divisors 
       */
      for (currentDivisor = 0; currentDivisor < NUM_DIVISORS; currentDivisor++)
	{
	  /*
	   * Check to see if we have a full coset with this
	   * divisor
	   */
	  cosetElementsLeft = MAX_VALUE / divisors[currentDivisor] - 1;
	  cosetElements[0] = i;

	  bzero (cosetElements, sizeof (int) * MAX_DIVISORS);

	  /*
	   * Search through the rest of [[gamma]] for
	   * cancellation
	   */
	  for (j = i + 1; j < SEQUENCE_LENGTH; j++)
	    {
	      if (gamma[j] == CANCELED)
		continue;

	      if (gamma[i] != gamma[j] &&
		  ((gamma[i] - gamma[j] +
		    MAX_VALUE) % (divisors[currentDivisor]) == 0))
		{
		  /*
		   * We have a divisor 
		   */
		  /*
		   * If we do not have one for this
		   * slot of the coset, then store this
		   * information in [[cosetElements]]
		   */
		  if (cosetElements[((gamma[i] -
				      gamma[j] +
				      MAX_VALUE) % MAX_VALUE)
				    / (divisors[currentDivisor])] == 0)
		    {
		      cosetElements[((gamma[i] -
				      gamma[j] +
				      MAX_VALUE) %
				     MAX_VALUE)
				    / (divisors[currentDivisor])] = j;
		      cosetElementsLeft--;
		      if (cosetElementsLeft == 0)
			break;
		    }
		}
	    };

	  /*
	   * If we have a full coset, then cancel the elements
	   * and break
	   */
	  if (cosetElementsLeft == 0)
	    {
	      for (j = 0; j < MAX_VALUE / divisors[currentDivisor]; j++)
		{
		  gamma[cosetElements[j]] = CANCELED;
		  gammaElementsLeft--;
		  cosetElements[j] = 0;
		};
	      break;
	    }
	}

      /*
       * If we have reached the end of the divisor list without
       * canceling, then we must have failed
       */
      if (currentDivisor == NUM_DIVISORS)
	{
	  return -1;
	}
    }

  /*
   * The Hardcoded Check Condition is much faster, but needs to be
   * modified depending on what roots of unity we are considering.
   */
  /*
   * <Hardcoded Check Condition>> 
   */

  /*
   * If we have canceled all the elements, then we are successful. If
   * there are elements left to cancel, then we failed.
   */
  if (gammaElementsLeft == 0)
    return 0;
  else
    return -1;
}


int
main (int argc, char **argv)
{
  int i;
  int shift = 1;
  int index;


  if (argc < 3)
    {
      printf
	  ("Usage: %s <Root of Unity> <Sequence Length> <Starting Sequence Values>\n\n",
	   argv[0]);

      printf
	  ("<Root Of Unity> and <Sequence Length> must each be greater than 2.\n");
      printf
	  ("<Starting Sequence Values> is a space delimited listing \n"
	   "of length <Sequence Length> of nonnegative integers \n"
	   "less than <Root of Unity>.\n");;
      exit (-1);
    }
  MAX_VALUE = atoi (argv[1]);
  SEQUENCE_LENGTH = atoi (argv[2]);

  if (MAX_VALUE < 3 || SEQUENCE_LENGTH < 3)
    {
      printf
	  ("Usage: %s <Root of Unity> <Sequence Length> <Starting Sequence Values>\n\n",
	   argv[0]);

      printf
	  ("<Root Of Unity> and <Sequence Length> must each be greater than 2.\n");
      printf
	  ("<Starting Sequence Values> is a space delimited listing \n"
	   "of length <Sequence Length> of nonnegative integers \n"
	   "less than <Root of Unity>.\n");;
      exit (-1);
    }
  if (argc < (SEQUENCE_LENGTH + 3))
    {
      printf
	  ("Usage: %s <Root of Unity> <Sequence Length> <Starting Sequence Values>\n\n",
	   argv[0]);

      printf
	  ("<Root Of Unity> and <Sequence Length> must each be greater than 2.\n");
      printf
	  ("<Starting Sequence Values> is a space delimited listing \n"
	   "of length <Sequence Length> of nonnegative integers \n"
	   "less than <Root of Unity>.\n");;
      exit (-1);
    }
  sequence = (int *) malloc (sizeof (int) * SEQUENCE_LENGTH);
  gamma = (int *) malloc (sizeof (int) * SEQUENCE_LENGTH);

  bzero (sequence, sizeof (int) * SEQUENCE_LENGTH);
  bzero (gamma, sizeof (int) * SEQUENCE_LENGTH);


  /*
   * Populate the sequence 
   */

  NUM_DIVISORS = 0;
  for (i = MAX_VALUE / 2 + 1; i > 0; i--)
    {
      if (MAX_VALUE % i == 0)
	{
	  divisors[NUM_DIVISORS] = i;
	  NUM_DIVISORS++;

	  if (NUM_DIVISORS == MAX_DIVISORS)
	    {
	      fprintf (stderr,
		       "Error: Cannot store all divisors"
		       "of %d (there are at least %d of them)\n",
		       MAX_VALUE, NUM_DIVISORS);
	      assert (NUM_DIVISORS < MAX_DIVISORS);

	    }
	}
    }

  sequence[0] = sequence[1] = 0;

  /*
   * Get starting sequence from command line 
   */
  for (i = 0; i < SEQUENCE_LENGTH; i++)
    {
      sequence[i] = atoi (argv[i + 3]);
    }

  while (1)
    {
      sequence[SEQUENCE_LENGTH - 1]++;
      sequence[SEQUENCE_LENGTH - 1] %= MAX_VALUE;

      /*
       * Check to see if we are wrapped around 
       */
      index = SEQUENCE_LENGTH - 1;
      while (sequence[index] == 0)
	{
	  index--;
	  sequence[index]++;
	  sequence[index] %= MAX_VALUE;
	  if (sequence[index] != 0)
	    break;

	  if (index == (SEQUENCE_LENGTH / 2))
	    {
	      printf ("Finished sequences starting with ");

	      for (i = 0; i < SEQUENCE_LENGTH; i++)
		{
		  printf ("%d ", sequence[i]);
		};

	      printf ("\n");
	    }
	  if (index == 1)
	    {
	      /*
	       * We are done. We have wrapped around the
	       * first index
	       */
	      goto DONE;
	    }
	}
      {
	for (shift = 1; shift < (SEQUENCE_LENGTH / 2 + 1); shift++)
	  {
	    for (i = 0; i < SEQUENCE_LENGTH; i++)
	      {
		gamma[i] =
		    ((sequence[i] - sequence[((i -
					       shift) +
					      SEQUENCE_LENGTH) %
					     SEQUENCE_LENGTH])
		     + MAX_VALUE) % MAX_VALUE;
	      };

	    if (checkGamma ())
	      {
		/*
		 * Print out where we have failed 
		 */
		if (shift > 5)
		  {
		    printf ("FAILED: ");

		    for (i = 0; i < SEQUENCE_LENGTH; i++)
		      {
			printf ("%d ", sequence[i]);
		      }
		    printf (" at shift %d\n", shift);
		  }
		/*
		 * Since we failed, go to the next
		 * sequence
		 */
		goto NEXT;
	      }
	  };

	/*
	 * If we get to here, then the sequence passes 
	 */
	printf ("PASSED: ");

	for (i = 0; i < SEQUENCE_LENGTH; i++)
	  {
	    printf ("%d ", sequence[i]);
	  }
	printf ("\n");

      NEXT:
      }
    }

DONE:

  free (sequence);
  free (gamma);

  exit (0);
}