70 lines
1.5 KiB
JavaScript
70 lines
1.5 KiB
JavaScript
|
class Crutch {
|
||
|
|
constructor(len) {
|
||
|
|
this.len = len;
|
||
|
|
this.s = new Array(len);
|
||
|
|
this.i = 0;
|
||
|
|
}
|
||
|
|
repeat(count) {
|
||
|
|
for (let j = 0; j < count; j++) {
|
||
|
|
if (++this.i === this.len) return;
|
||
|
|
this.s[this.i] = this.s[this.i - 1];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
function nextInCycle(self, index) {
|
||
|
|
return self[index % self.length];
|
||
|
|
}
|
||
|
|
|
||
|
|
function kolakoski(self, len) {
|
||
|
|
const c = new Crutch(len);
|
||
|
|
let k = 0;
|
||
|
|
while (c.i < len) {
|
||
|
|
c.s[c.i] = nextInCycle(self, k);
|
||
|
|
if (self[k] > 1) {
|
||
|
|
c.repeat(self[k] - 1);
|
||
|
|
}
|
||
|
|
if (++c.i === len) return c.s;
|
||
|
|
k++;
|
||
|
|
}
|
||
|
|
return c.s;
|
||
|
|
}
|
||
|
|
|
||
|
|
function possibleKolakoski(self) {
|
||
|
|
const rle = [];
|
||
|
|
let prev = self[0];
|
||
|
|
let count = 1;
|
||
|
|
let pos = 0;
|
||
|
|
for (let i = 1; i < self.length; i++) {
|
||
|
|
if (self[i] === prev) {
|
||
|
|
count++;
|
||
|
|
} else {
|
||
|
|
rle[pos++] = count;
|
||
|
|
count = 1;
|
||
|
|
prev = self[i];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for (let i = 0; i < pos; i++) {
|
||
|
|
if (rle[i] !== self[i]) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
const ias = [
|
||
|
|
[1, 2],
|
||
|
|
[2, 1],
|
||
|
|
[1, 3, 1, 2],
|
||
|
|
[1, 3, 2, 1]
|
||
|
|
];
|
||
|
|
const lens = [20, 20, 30, 30];
|
||
|
|
|
||
|
|
for (let i = 0; i < ias.length; i++) {
|
||
|
|
const len = lens[i];
|
||
|
|
const kol = kolakoski(ias[i], len);
|
||
|
|
console.log(`First ${len} members of the sequence generated by [${ias[i]}]:`);
|
||
|
|
console.log(`[${kol}]`);
|
||
|
|
console.log(`Possible Kolakoski sequence? ${possibleKolakoski(kol)}\n`);
|
||
|
|
}
|