Kolakoski sequence: Difference between revisions
Content deleted Content added
Added Kotlin |
Added C |
||
Line 51: | Line 51: | ||
# Check the sequence againt its RLE. |
# Check the sequence againt its RLE. |
||
(There are [[wp:Kolakoski_sequence#From_finite_integer_sets|rules]] on generating Kolakoski sequences from this method that are broken by the last example) |
(There are [[wp:Kolakoski_sequence#From_finite_integer_sets|rules]] on generating Kolakoski sequences from this method that are broken by the last example) |
||
=={{header|C}}== |
|||
{{trans|Kotlin}} |
|||
<lang 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; |
|||
}</lang> |
|||
{{output}} |
|||
<pre> |
|||
First 20 members of the sequence generated by [1, 2]: |
|||
[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1] |
|||
Possible Kolakoski sequence? True |
|||
First 20 members of the sequence generated by [2, 1]: |
|||
[2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2] |
|||
Possible Kolakoski sequence? True |
|||
First 30 members of the sequence generated by [1, 3, 1, 2]: |
|||
[1, 3, 3, 3, 1, 1, 1, 2, 2, 2, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1] |
|||
Possible Kolakoski sequence? True |
|||
First 30 members of the sequence generated by [1, 3, 2, 1]: |
|||
[1, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1, 3, 2, 1, 1, 1, 1, 3, 3, 3, 2, 2, 1] |
|||
Possible Kolakoski sequence? False |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
<lang scala>// Version 1.2.41 |
<lang scala>// Version 1.2.41 |