74 lines
1.6 KiB
D
74 lines
1.6 KiB
D
import std.stdio;
|
|
|
|
void repeat(int count, void delegate(int) action) {
|
|
for (int i=0; i<count; i++) {
|
|
action(i);
|
|
}
|
|
}
|
|
|
|
T nextInCycle(T)(T[] self, int index) {
|
|
return self[index % self.length];
|
|
}
|
|
|
|
T[] kolakoski(T)(T[] self, int len) {
|
|
T[] s;
|
|
s.length = len;
|
|
int i;
|
|
int k;
|
|
while (i<len) {
|
|
s[i] = self.nextInCycle(k);
|
|
if (s[k] > 1) {
|
|
repeat(s[k] - 1,
|
|
(int j) {
|
|
if (++i == len) return;
|
|
s[i] = s[i-1];
|
|
}
|
|
);
|
|
}
|
|
if (++i == len) return s;
|
|
k++;
|
|
}
|
|
return s;
|
|
}
|
|
|
|
bool possibleKolakoski(T)(T[] self) {
|
|
auto len = self.length;
|
|
T[] rle;
|
|
auto prev = self[0];
|
|
int count = 1;
|
|
foreach (i; 1..len) {
|
|
if (self[i] == prev) {
|
|
count++;
|
|
} else {
|
|
rle ~= count;
|
|
count = 1;
|
|
prev = self[i];
|
|
}
|
|
}
|
|
// no point adding final 'count' to rle as we're not going to compare it anyway
|
|
foreach (i; 0..rle.length) {
|
|
if (rle[i] != self[i]) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void main() {
|
|
auto ias = [[1,2],[2,1],[1,3,1,2],[1,3,2,1]];
|
|
auto lens = [20,20,30,30];
|
|
|
|
foreach (i,ia; ias) {
|
|
auto len = lens[i];
|
|
auto kol = ia.kolakoski(len);
|
|
writeln("First ", len, " members of the sequence generated by ", ia, ":");
|
|
writeln(kol);
|
|
write("Possible Kolakoski sequence? ");
|
|
if (kol.possibleKolakoski) {
|
|
writeln("Yes");
|
|
} else {
|
|
writeln("no");
|
|
}
|
|
writeln;
|
|
}
|
|
}
|