/* Kevin Ryde, August 2023

   Usage: ./a.out [-v] maxn

   Find and print terms of A364882 which is

       a(n+1) = number of dead-ends in paths starting anywhere
                and step from i to i-a(i) or i+a(i) always within
                locations 1..n


   Algorithm
   ---------

   The strategy is to have terms 1..n and detect a dead-end "e" by
   a brute-force search of paths back through predecessors of e,
   seeking a path which visits its destinations e-a(e) and e+a(e)
   (those within 1..n), thus blocking the steps after e.

   If a+a(e) <= n then such a path makes e permanently dead-end.
   This is marked dead[e] = 2 and e is not checked again.

   If n < a+a(e) <= maxn then such a path makes e dead-end, but
   must be re-checked on reaching n = e+a(e).  This is marked
   dead[e] = 1.

   All other e are not dead ends and are marked dead[e] = 0.
   They're re-checked after every new term a(n).

   A full re-check of all not-dead-ends each time is not efficient,
   but later terms can affect much earlier terms.  Eg. location e=4
   is not a dead-end until a(33) is reached, at which point becomes
   permanently dead-end.


   Command Line
   ------------

   Parameter "maxn" is the maximum n term to find.
   Optional parameter "bfile" prints in b-file form "n a(n)".

       ./a.out bfile 80

   Optional parameter "-v" prints verbose output, including
   the blocking paths found.
*/


/* Set WANT_ASSERT to 1 to enable self-checks (slow).
   Set WANT_DEBUG to 1 for some rough development prints.
*/
#define WANT_ASSERT  0
#define WANT_DEBUG   0

#if ! WANT_ASSERT
#define NDEBUG
#endif

#include <assert.h>
#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdnoreturn.h>


/* ------------------------------------------------------------------------ */
/* Generic */

#if WANT_DEBUG
#define DEBUG(expr)  do { expr; } while (0)
#else
#define DEBUG(expr)  do {       } while (0)
#endif

#ifdef __GNUC__
#define LIKELY(cond)    __builtin_expect((cond) != 0, 1)
#define UNLIKELY(cond)  __builtin_expect((cond) != 0, 0)
#define ATTRIBUTE_PRINTF __attribute__ ((format (printf, 1, 2)))
#else
#define LIKELY(cond)    (cond)
#define UNLIKELY(cond)  (cond)
#define ATTRIBUTE_PRINTF
#endif

#define numberof(array)  (sizeof(array)/sizeof((array)[0]))

noreturn ATTRIBUTE_PRINTF void
error (const char *format, ...)
{
  va_list ap;
  va_start (ap, format);
  vfprintf (stderr, format, ap);
  va_end (ap);
  exit(1);
}

void
fflush_or_die (FILE *fp, const char *filename)
{
  if (fflush(fp) != 0)
    error("Error writing %s: %s", filename, strerror(errno));
}

void
ferror_die (FILE *fp, const char *filename, const char *action)
{
  if (ferror(fp))
    error("Error %s %s\n", action, filename);
}

/* with ptr==NULL allowed for initial malloc */
void *
realloc_or_die(void *ptr, size_t size)
{
  ptr = (ptr == NULL ? malloc(size) : realloc(ptr, size));
  if (UNLIKELY (ptr == NULL))
    error("Cannot realloc() to %zu bytes\n", size);
  return (ptr);
}


/* ------------------------------------------------------------------------ */

/* Some initial values, as a consistency check. */
static const int want[] = {
  -1,  /* no term a(0) */
  1,1,2,3,3,3,3,4,6,6,7,7,7,7,7,7,9,9,9,11,11,11,14,15,15,15,15,17,18,18,18,19,19,25,25,25,25,26,26,26,26,26,27,27,27,28,28,28,28,29,29
};

void
check_want (int n, int value)
{
  assert (n >= 1);
  if (n < numberof(want) && value != want[n])
    error("  oops, n=%d got %d want %d\n", n, value, want[n]);
}


/* ------------------------------------------------------------------------ */

/* brute-force is to slow to go much past maxn=300 actually */
#define MAXN_LIMIT  1000

static int a[MAXN_LIMIT+1];    /* sequence terms a[n] = a(n) */
static int dead[MAXN_LIMIT+1];
static struct predecessors {
  int num;
  int *list;   /* predecessors[i].list all who step to i */
} predecessors[MAXN_LIMIT+1];

static int hold_path[MAXN_LIMIT+1];
static int hold_pos[MAXN_LIMIT+1];
static int seen[MAXN_LIMIT+1];  /* flags for s and hold_path[] */

static int maxn = 30;
static int n;

/* mark new from -> to in predecessors of to */
static void
predecessors_add (int from, int to)
{
  DEBUG(printf("  predecessor %d -> %d\n", from, to));
  assert (1 <= from && from <= n);
  assert (1 <= to && to <= maxn);

  int num = predecessors[to].num;
  predecessors[to].list = realloc_or_die
    (predecessors[to].list, (num+1) * sizeof(predecessors[to].list[0]));
  predecessors[to].list[num] = from;
  predecessors[to].num = num+1;
}


/* ------------------------------------------------------------------------ */

/* command line options */
static int option_verbose = 0;
static int option_bfile = 0;

/* check path = s, hold_path[t-1], ..., hold_path[0]
   are all and only locations marked in seen[] */
int
check_seen (int s, int t)
{
  static int want_seen[MAXN_LIMIT+1];
  memset (want_seen,'\0',sizeof(want_seen));
  assert (1 <= s && s <= n);
  want_seen[s] = 1;
  int i;
  for (i=0; i<t; i++) {
    assert (1 <= hold_path[i] && hold_path[i] <= n);
    want_seen[hold_path[i]] = 1;
  }

  int bad = 0;
  for (i=1; i<=n; i++) {
    if (seen[i] != want_seen[i]) {
      fprintf(stderr, "seen wrong at i=%d got %d want %d\n",
              i, seen[i], want_seen[i]);
      bad++;
    }
  }
  return (bad==0);
}

/* about new dead[e] = is_dead */
void
output_dead (int e, int s, int t, int is_dead)
{
  if (option_verbose && is_dead==2) {
    printf("  e=%d permanent blocked,",e);
    if (e-a[e] < 1)
      printf(" destination %d", e+a[e]);
    else
      printf(" destinations %d,%d", e-a[e], e+a[e]);
    printf(" path %d", s);
    int i;
    for (i=t-1; i>=0; i--)
      printf(",%d", hold_path[i]);
    printf("\n");
  }
}

/* is_dead_end(e) checks whether location number e is a dead-end.
   Return 0 if not,
          1 if yes but must re-check when n = e+a[e] reached,
          2 if yes and is permanently dead-end
*/
int
is_dead_end (int e)
{
  /* This is a depth-first traversal of paths back from e.
     The current path is

         s -> hold_path[t-1] -> ... -> hold_path[0] = e

     The path extends back before s using predecessors[s].list
     (those elements <= n and not already in the path).
     "pos" is the next predecessor number of s to try,
     ie. predecessors[s].list[pos].

     predecessors[s].num is the number of predecessors so end when
     pos >= num.  In that case backtrack to s = hold_path[t-1] and
     its pos = hold_pos[t-1].

     seen[i] = 1 for each i in the path s .. hold_path[0] is used
     for checking whether e destinations to_small and to_big are in
     the path thereby blocking any step after e and so e is a
     dead-end.

     to_small and to_big are dummy values "e" itself if e-a[e] < 1
     or e+a[e] > n outside the indices 1..n so far.
     e itself is always seen[e]=1 so that ignores e destinations
     out of range.
  */

  DEBUG(printf("is_dead_end() e=%d\n", e));
  int to_small = (e-a[e] < 1 ? e : e-a[e]);
  int to_big   = (e+a[e] > n ? e : e+a[e]);
  DEBUG(printf("  e destinations to_small %d  to_big %d\n",
               to_small, to_big));

  memset (seen+1,'\0',sizeof(seen[0])*n);
  int t = 0;
  int s = e;    /* s start of path */
  int pos = 0;
  seen[s] = 1;

  for (;;) {
    assert (check_seen(s,t));
    if (UNLIKELY(seen[to_small] & seen[to_big])) {
      int is_dead = (n < e+a[e] ? 1 : 2);
      output_dead (e,s,t,is_dead);
      return (is_dead);
    }

  PRECEDE:
    /* next predecessor of s goes onto front of path */
    DEBUG(printf("  at t=%d  s=%d pos=%d of %d  hold_path = ",
                 t, s, pos, predecessors[s].num);
          {int j; for(j=t-1;j>=0;j--) printf("->%d",hold_path[j]);}
          printf("\n"));
    assert (1 <= s && s <= n);
    assert (0 <= t && t < numberof(hold_path));
    assert (check_seen(s,t));

    assert (0 <= pos && pos <= predecessors[s].num);
    if (UNLIKELY(pos >= predecessors[s].num)) {
      DEBUG(printf("    backtrack\n"));
      if (UNLIKELY(--t < 0))
        return(0);
      seen[s] = 0;
      s = hold_path[t];
      pos = hold_pos[t];
      goto PRECEDE;
    }
    int new = predecessors[s].list[pos++];
    DEBUG(printf("    s=%d predecessor %d\n", s,new));
    if (new > n || seen[new]) {
      DEBUG(printf("    seen or out of range\n"));
      goto PRECEDE;
    }

    hold_pos[t] = pos;
    hold_path[t] = s;
    seen[new] = 1;
    s = new;
    pos = 0;
    t++;
  }
}

void
term_setups (void)
{
  /* a[n] is a new term in the sequence.
     Put it into predecessors[] and recheck dead[].
  */
  DEBUG(printf("term_setups() n=%d  %d\n", n, a[n]));

  int sign;
  for (sign = -1; sign <= 1; sign += 2) {
    int to = n + sign*a[n];
    if (1<=to && to<=maxn)
      predecessors_add (n, to);
  }

  DEBUG(printf("update dead\n"));
  int e;
  for (e=1; e<=n; e++) {
    if (dead[e]==0 || (dead[e]==1 && e+a[e]<=n)) {
      dead[e] = is_dead_end(e);
      DEBUG(printf("  dead e=%d  %d\n", e, dead[e]));
    }
  }
}

int
count_dead (void)
{
  int i, ret=0;
  for (i=1; i<=n; i++) ret += (dead[i] != 0);
  return (ret);
}

void
output_info (void)
{
  if (option_verbose) {
    const char *join = "";
    int i;
    printf("  not dead-ends: ");
    for (i=1; i<=n; i++) {
      if (dead[i]==0) {
        printf("%s%d",join,i);
        join = ",";
      }
    }
    printf("\n");

    printf("  dead-end later re-check: ");
    join = "";
    for (i=1; i<=n; i++) {
      if (dead[i]==1) {
        printf("%s%d",join,i);
        join = ",";
      }
    }
    printf("\n");
  }
}
void
output_term (void)
{
  DEBUG(printf("\n"));

  if (option_verbose) {
    printf("\nn=%d term %d\n",n, a[n]);

  } else if (option_bfile) {
    printf("%d %d\n",n,a[n]);

  } else {
    printf("%d,",a[n]);
  }
  check_want(n,a[n]);
}

void
output_end (void)
{
  if (option_verbose) {
  } else if (option_bfile) {
  } else {
    printf("\n");
  }
}

void
search (void)
{
  n = 1;
  a[n] = 1;
  output_term();

  while (n < maxn) {
    term_setups();
    output_info();
    n++;
    a[n] = count_dead();
    output_term();
  }
}

int
main (int argc, char *argv[])
{
  int i, endpos;
  setbuf(stdout,NULL);

  for (i = 1; i < argc; i++) {
    const char *arg = argv[i];
    if (strcmp(arg,"-v")==0) {
      option_verbose++;
    } else if (strcmp(arg,"bfile")==0) {
      option_bfile = 1;
    } else if (sscanf(arg, "%u%n", &maxn, &endpos) == 1
               && endpos == strlen(arg)) {
      if (maxn > MAXN_LIMIT)
        error("maxn %d bigger than MAXN_LIMIT %d\n", maxn, MAXN_LIMIT);
    } else {
      error("Unrecognised command line option: %s\n", arg);
    }
  }

  search();
  output_end();
  fflush_or_die(stdout,"stdout");
  ferror_die(stdout,"stdout","writing");
  return(0);
}