88 lines
2 KiB
C
88 lines
2 KiB
C
#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;
|
|
}
|