/* Let's try it binary wize.  The probability of the next bit being a 1 and the probability that it will be a 0.  To start, they're dead even.  The first coefficient, c0, is .5.  The first bit will be a 0 or a 1.  This suggests that the guessed probability of each, i.e. .5, was wrong.  By how much, we don't know.  This could be because the c0 was wrong, or c1.  In fact, why don't we limit it.  There will be always 1000 coefficients.  Assume there are values going out to infinity and they conform to this probability function (however, an unlikely value may still occur.  But we allow such more in the past than the present.

   Perhaps store 1000 coefficients and the last 8000 bits.  For each, make the smallest change in the coefficients such that all 8000 bits are accounted for.  So calculate the delta for each coefficient that would have been neccessary to alone predict that value.  Sort by smallest needed delta.  Apply first delta.  Check remaining coefficients.  If they all match, done.  Otherwise undo, try next.  Repeat until on fits specifications.  If none do, ignore last bit and try again?  No.  When checking if something failed, determine how much failed by, sum those; that's its score.  Repeat finding the lowest score.  But only add to score if fails.

   One more thing: since there is no set periodicity, have to assume on the order of how many characters recieved, and expand as needed.  1 (c0) at 0, 3 at 1, 5 at 2, 7 at 4, 9 at 8, etc... */

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

#define CACHE 8000
#define LARGE_VAL 1e5

#define random() ((float) rand() / (float) RAND_MAX)

#define prederr(p) fabs(p - .5)
/*#define predfail(p, v) (p > 1.0 || p < 0.0 || (p > .5) != v)*/
#define predfail(p, v) ((p > .5) != v)

float preds[CACHE];

typedef struct tagCoeff {
  float csin;  /* Fourier coefficients */
  float ccos;
  struct tagCoeff *next;
} Coeff;

Coeff *Initialize() {
  Coeff *root = malloc(sizeof(Coeff));

  root->csin = 0;  /* c0 */
  root->ccos = 0;  /* c1 */
  root->next = NULL;

  return root;
}

void Deinitialize(Coeff *root) {
  Coeff *curr;
  while (root) {
    curr = root;
    root = root->next;
    free(curr);
  }
}

float FourierAt(Coeff *root, long loc) {
  float result = root->csin;
  double dloc = (double) loc * M_PI;

  do {
    result += root->ccos * cos(dloc) + root->csin * sin(dloc);
    dloc /= 2.0;
  } while (root = root->next);

  return result;
}

int CountNonZero(Coeff *root) {
  int num = 0;

  do {
    if (root->ccos != 0)
      num++;
    if (root->csin != 0)
      num++;
  } while (root = root->next);

  return num;
}

/* returns minimum disruption */
float FixCoeffs(Coeff *root, char data[CACHE], int cd, float presult, long loc)
{
  /* Change coefficient with fewest side effects, unless any with 0, then by
     smallest change */
  char c = data[cd];
  double dloc = (double) loc * M_PI;
  int d;

  float goal = (data[cd] ? .5 : 0) + random() / 2.0;

  float disrupts = 0;
  float minchnge = goal - presult;
  float bestpiper = 0;
  char besttype = 0;
  float *bestcoef = &(root->csin);

  float currchng, currdisr = 0;

  Coeff *curr = root;
  float predict;

  double piper = 1.0 / M_PI;

  /* Try change in root */
  for (d = cd - 1; d >= 0; d--) {
    predict = preds[d] + minchnge;
    if (predfail(predict, data[d])) /* Failed prediction */
      disrupts += prederr(predict);
  }

  if (data[CACHE - 1])
    for (d = CACHE - 1; d > cd; d--) {
      predict = preds[d] + minchnge;
      if (predfail(predict, data[d])) /* Failed prediction */
	disrupts += prederr(predict);
    }

  /* For each coeff, determine needed change */
  do {
    /* Cos Coefficient */
    if (cos(dloc) != 0) {
      currchng = (goal - presult) / cos(dloc) - curr->ccos;
      if (fabs(currchng) < .75) { /* Don't allow large changes */
	currdisr = 0;

	for (d = cd - 1; d >= 0; d--) {
	  predict = preds[d] + currchng * cos((double) (loc + d - cd) / piper);
	  if (predfail(predict, data[d])) /* Failed prediction */
	    currdisr += prederr(predict);
	}

	if (data[CACHE - 1])
	  for (d = CACHE - 1; d > cd; d--) {
	    predict = preds[d]
	      + currchng * cos((double) (loc - cd - (CACHE - d)) / piper);
	    if (predfail(predict, data[d])) /* Failed prediction */
	      currdisr += prederr(predict);
	  }

	if (currdisr < disrupts ||
	    (currdisr == disrupts && fabs(currchng) < fabs(minchnge))) {
	    disrupts = currdisr;
	    minchnge = currchng;
	    bestpiper = piper;
	    besttype = 2;
	    bestcoef = &(curr->ccos);
	  }
      }
    }

    /* Sin Coefficient */
    if (sin(dloc) != 0) {
      currchng = (goal - presult) / sin(dloc) - curr->csin;
      if (fabs(currchng) < .75) { /* Don't allow large changes */
	currdisr = 0;

	for (d = cd - 1; d >= 0; d--) {
	  predict = preds[d] + currchng * sin((double) (loc + d - cd) / piper);
	  if (predfail(predict, data[d])) /* Failed prediction */
	    currdisr += prederr(predict);
	}

	if (data[CACHE - 1])
	  for (d = CACHE - 1; d > cd; d--) {
	    predict = preds[d]
	      + currchng * sin((double) (loc - cd - (CACHE - d)) / piper);
	    if (predfail(predict, data[d])) /* Failed prediction */
	      currdisr += prederr(predict);
	  }

	if (currdisr < disrupts ||
	    (currdisr == disrupts && fabs(currchng) < fabs(minchnge))) {
	    disrupts = currdisr;
	    minchnge = currchng;
	    bestpiper = piper;
	    besttype = 1;
	    bestcoef = &(curr->csin);
	  }
      }
    }

    piper *= 2.0;
    dloc /= 2.0;
  } while (curr = curr->next);

  *bestcoef += minchnge;

  /* Update predictions for each datum in CACHE */
  for (d = cd - 1; d >= 0; d--)
    if (besttype == 0)
      preds[d] += minchnge;
    else if (besttype == 1)
      preds[d] += minchnge * sin((double) (loc + d - cd) / bestpiper);
    else if (besttype == 2)
      preds[d] += minchnge * cos((double) (loc + d - cd) / bestpiper);
  for (d = CACHE - 1; d > cd; d--)
    if (besttype == 0)
      preds[d] += minchnge;
    else if (besttype == 1)
      preds[d] += minchnge * sin((double) (loc - cd - (CACHE-d)) / bestpiper);
    else if (besttype == 2)
      preds[d] += minchnge * cos((double) (loc - cd - (CACHE-d)) / bestpiper);
  preds[cd] = goal;

  return disrupts;
}

void PrintCoeffs(Coeff *root) {
  do
    printf(" %f %f", root->ccos, root->csin);
  while (root = root->next);
}

int main() {
  Coeff *root = Initialize(), **last = &(root->next);
  char data[CACHE];
  int d, curr;
  int fc;
  long cnum = 0, dnum = 0;
  long tonew = 1, tocnt = 1;
  float predict;

  int getbit;
  char c;

  char tryc, ic;

  long success = 0;

  FILE *input = fopen("input.txt", "rb");

  for (d = 0; d < CACHE; d++) {
    data[d] = 0;
    preds[d] = 0.0;
  }
  curr = 0;

  root->csin = .5;

  d = 0;
  while ((fc = fgetc(input)) != EOF) {
    printf("%c", fc);
    fflush(NULL);

    for (getbit = 1; getbit < 256; getbit <<= 1) {
      c = (fc & getbit) != 0;
      /*printf("%d", c);*/
      fflush(NULL);

      data[curr] = c; /* Take new data */
      preds[curr] = FourierAt(root, dnum);

      /* Try to predict c */
      predict = preds[curr];
      if (predfail(predict, c)) /* Failed prediction */
	FixCoeffs(root, data, curr, predict, dnum);
	/*while (FixCoeffs(root, data, curr, predict, dnum) != 0)
	  predict = FourierAt(root, dnum);*/

      if ((predict > .5) == c)
	success++;

      /*printf("[%ld, %d] ", dnum, curr);
	if (predfail(predict, c))
	printf("Fix: ");
	printf("Input: %d; Predict %f; New Predict: %f\n", c, predict, FourierAt(root, dnum));*/

      /* Add coeffs if needed */
      if (!(--tonew)) {
	tocnt *= 2;
	tonew = tocnt;

	*last = Initialize();
	last = &((*last)->next);
      }

      dnum++;
      curr++;
      if (curr == CACHE)
	curr = 0;
    }

    if (d == 79) {
      printf("\nSuccess: %f; Next Guesses: ", (double) success / (double) dnum);
      ic = 0;
      while (ic < 40) {
	for (getbit = 1, tryc = 0; getbit < 256; getbit <<= 1)
	  tryc |= getbit * (FourierAt(root, dnum + ic++) > .5);
	printf("%c", tryc);
      }
      printf("\n");
      d = 0;
    } else
      d++;
  }

  Deinitialize(root);
}