/*

 main-A171884.c

 20100311 Copy from A097486
 20100312 Add -l, -s and -h options

 */

#include <stdio.h>        // defines size_t
#include <stdlib.h>       // defines malloc
#include <string.h>

#define DEFAULT_SIZE_LIM 100

long * g_l;
long g_alloc;
long g_lowestval;
long g_startval;

/* Search for an item, return a negative result if it is not found */
long cw2010_seek(long * haystack, long size, long needle);
long cw2010_seek(long * haystack, long size, long needle)
{
  long i;

  for(i=0; i<size; i++) {
    if(haystack[i] == needle) {
      return(i);
    }
  }
  return(-1);
}

/* Return the value of the largest element of a list */
long cw2010_largest(long * l, long size);
long cw2010_largest(long * l, long size)
{
  long best, i;

  best = -1;
  for(i=0; i<size; i++) {
    if(l[i] > best) {
      best = l[i];
    }
  }
  return(best);
}

/* Return true if there is a direct "escape route" by going up each time.
   Non-recursive and a little faster than a general escape search. */
long cw2010_escdir_p(long * l, long size);
long cw2010_escdir_p(long * l, long size)
{
  long largest;
  long i, n;
  if (size==0) {
    return(1);
  }
  largest = cw2010_largest(l, size);
  if (l[size-1] == largest) {
    return(1);
  }
  i = size;
  n = l[i-1];
  while(n < largest) {
    n = n + i; i = i+1;
    if (cw2010_seek(l, size, n)) {
      return(0);
    }
  }
  return(1);
}

/* Return true if the "down" next term option is legal */
long cw2010_down_p(long * l, long size);
long cw2010_down_p(long * l, long size)
{
  long t;

  t = l[size-1] - size;
  if ((t < g_lowestval) || (cw2010_seek(l, size, t) >= 0)) {
    return(0);
  }
  return(1);
}

/* Return true if the "up" next term option is legal */
long cw2010_up_p(long * l, long size);
long cw2010_up_p(long * l, long size)
{
  long t;

  t = l[size-1] + size;
  if (cw2010_seek(l, size, t) >= 0) {
    return(0);
  }
  return(1);
}

/* Recursive algorithm, seeks an escape route preferring the "upper path"
   at each choice in order to find an exit quickly. */
long cw2010_escape_p(long * l, long size);
long cw2010_escape_p(long * l, long size)
{
  long i;

  /* First try the direct route, which will save time on the recursive
     backtracking */
  if (cw2010_escdir_p(l, size)) {
    return(1);
  }
  if (size >= g_alloc) {
    fprintf(stderr, "cw2010_esc_p: Reached allocation limit.");
    exit(-1);
  }
  if (cw2010_up_p(l, size)) {
    l[size] = l[size-1] + size;
//    if(cw2010_escape_p(l, size+1)) {
//      return(1);
//    }
return(cw2010_escape_p(l, size+1));
  }
  if (cw2010_down_p(l, size)) {
    l[size] = l[size-1] - size;
    return(cw2010_escape_p(l, size+1));
  }
  return(0);
}

/* Report the holes in a list */
void cw2010_holes(long * l, long size);
void cw2010_holes(long * l, long size)
{
  long largest, i, first, prev;

  first = 1; prev = -1;
  printf("Holes: ");
  largest = cw2010_largest(l, size);
  for(i=g_lowestval; i<largest; i++) {
    if (cw2010_seek(l, size, i) < 0) {
      if (first) {
        printf("%ld-", i);
      } else if (i == prev+1) {
      } else {
        printf("%ld, %ld-", prev, i);
      }
      prev = i;
      first = 0;
    }
  }
  printf("?, ...\n");
}

/* Main algorithm, seeks a limited-size initial subsequence of the (presumed
   unique) lexicographically earliest permutation of integers a(n) such
   that |a(n+1)-a(n)|=n for all n. */   
void cw2010_a(void);
void cw2010_a(void)
{
  long i;
  long * l;

  l = g_l;

  i = 0;
  l[i] = g_startval;
  printf("%ld, ", l[i]);
  while(i < g_alloc/2) {
    i++;
    /* First try the "down" option */
    if (cw2010_down_p(l, i)) {
      l[i] = l[i-1] - i;
      /* Is there any way to "escape to infinity" based on this choice? */
      if (cw2010_escape_p(l, i+1)) {
        /* Yes, we can continue with this choice */
        printf("%ld, ", l[i]);
      } else {
        /* Down failed, so try going up */
        l[i] = l[i-1] + i;
        if (cw2010_escape_p(l, i+1)) {
          /* Yes, up worked, so we'll go with that. */
          printf("%ld, ", l[i]);
        } else {
          /* Error! there is no solution at all */
          fprintf(stderr, "cw2010_a: got stuck after %ld terms.\n", i);
          exit(-1);
        }
      }
    } else if (cw2010_up_p(l, i)) {
      l[i] = l[i-1] + i;
      if (cw2010_escape_p(l, i+1)) {
        /* Yep, up worked */
        printf("%ld, ", l[i]);
      } else {
        /* Error: there is no solution */
        fprintf(stderr, "cw2010_a: stuck after %ld terms.\n", i);
        exit(-1);
      }
    } else {
      /* Error: there is no solution */
      fprintf(stderr, "cw2010_a: stuck after %ld terms.\n", i);
      exit(-1);
    }
  }
  printf("\n");
  printf("Computed %ld terms.\n", i+1);
  cw2010_holes(l, i);
}

void help(void);
void help(void)
{
  printf("A171884 options:\n");
  printf("  500     A number without an option-letter tells how many terms to compute\n");
  printf("          (default is 100)\n");
  printf("  -s 2    Start the sequence at the given value (default is 0)\n");
  printf("  -l 1    Specify lowest permissible value (default is 0)\n");
}

int main(int argc, char** argv)
{
  int i;
  char c;

  g_alloc = DEFAULT_SIZE_LIM;
  g_lowestval = 0;
  g_startval = 0;
  for(i=1; i<argc; i++) {
    if (argv[i]) {
      c = argv[i][0];
      if (c == '-') {
        if (strcmp(argv[i], "-h") == 0) {
          help();
        } else if (strcmp(argv[i], "-l") == 0) {
          /* -l gives lowest legal value (usually 0 or 1) */
          i++;
          if (argv[i]) {
            sscanf(argv[i], "%ld", &g_lowestval);
          }
        } else if (strcmp(argv[i], "-s") == 0) {
          /* -s gives starting value (usually 0 or 1) */
          i++;
          if (argv[i]) {
            sscanf(argv[i], "%ld", &g_startval);
          }
        }
      } else if ((c >= '0') && (c <= '9')) {
        sscanf(argv[i], "%ld", &g_alloc);
      }
    }
  }
  if (g_alloc < 10) {
    fprintf(stderr, "A171884: max must be at least 10; I got %ld\n", g_alloc);
    exit(-1);
  }

  printf("Parameters: start %ld lowest %ld numterms %ld\n",
                                             g_startval, g_lowestval, g_alloc);

  /* Convert desired number of terms to array allocation size */
  g_alloc = 2 * (g_alloc - 1);
  
  g_l = (long *) malloc(sizeof(long) * g_alloc);

  cw2010_a();

  return(0);
}

/* end of main-A171884.c */