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

#define TRUE 1
#define FALSE 0

typedef int bool;

int next_in_cycle(int *c, int len, int index) {
    return c[index % len];
}

void kolakoski(int *c, int *s, int clen, int slen) {
    int i = 0, j, k = 0;
    while (TRUE) {
        s[i] = next_in_cycle(c, clen, k);
        if (s[k] > 1) {
            for (j = 1; j < s[k]; ++j) {
                if (++i == slen) return;
                s[i] = s[i - 1];
            }
        }
        if (++i == slen) return;
        k++;
    }
}

bool possible_kolakoski(int *s, int len) {
    int i, j = 0, prev = s[0], count = 1;
    int *rle = calloc(len, sizeof(int));
    bool result = TRUE;
    for (i = 1; i < len; ++i) {
        if (s[i] == prev) {
            count++;
        }
        else {
            rle[j++] = count;
            count = 1;
            prev = s[i];
        }
    }
    /* no point adding final 'count' to rle as we're not going to compare it anyway */
    for (i = 0; i < j; i++) {
        if (rle[i] != s[i]) {
           result = FALSE;
           break;
        }
    }
    free(rle);
    return result;
}

void print_array(int *a, int len) {
    int i;
    printf("[");
    for (i = 0; i < len; ++i) {
       printf("%d", a[i]);
       if (i < len - 1) printf(", ");
    }
    printf("]");
}

int main() {
    int i, clen, slen, *s;
    int c0[2] = {1, 2};
    int c1[2] = {2, 1};
    int c2[4] = {1, 3, 1, 2};
    int c3[4] = {1, 3, 2, 1};
    int *cs[4] = {c0, c1, c2, c3};
    bool p;
    int clens[4] = {2, 2, 4, 4};
    int slens[4] = {20, 20, 30, 30};
    for (i = 0; i < 4; ++i) {
        clen = clens[i];
        slen = slens[i];
        s = calloc(slen, sizeof(int));
        kolakoski(cs[i], s, clen, slen);
        printf("First %d members of the sequence generated by ", slen);
        print_array(cs[i], clen);
        printf(":\n");
        print_array(s, slen);
        printf("\n");
        p = possible_kolakoski(s, slen);
        printf("Possible Kolakoski sequence? %s\n\n", p ? "True" : "False");
        free(s);
    }
    return 0;
}