Kolakoski sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|zkl}}: get rid of variables) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (42 intermediate revisions by 20 users not shown) | |||
Line 36:
...
'''Note''' that the RLE of <code>1, 2, 2, 1, 1, ...</code> begins <code>1, 2, 2</code>
;Task:
Line 46:
# Show, on this page, the first 20 members of the sequence generated from <code>(2, 1)</code>
# Check the sequence againt its RLE.
# Show, on this page, the first 30 members of the
# Check the sequence againt its RLE.
# Show, on this page, the first 30 members of the
# 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)
=={{header|11l}}==
{{trans|C++}}
<syntaxhighlight lang="11l">F gen_kolakoski(s, n)
[Int] seq
V i = 0
L seq.len < n
V next = s[i % s.len]
seq [+]= [next] * (I i >= seq.len {next} E seq[i])
i++
R seq[0 .< n]
F is_possible_kolakoski(s)
[Int] r
V i = 0
L i < s.len
V count = 1
L(j) i + 1 .< s.len
I s[j] != s[i]
L.break
count++
r.append(count)
i += count
L(i) 0 .< r.len
I r[i] != s[i]
R 0B
R 1B
L(s) [[1, 2],
[2, 1],
[1, 3, 1, 2],
[1, 3, 2, 1]]
V kol = gen_kolakoski(s, I s.len > 2 {30} E 20)
print(‘Starting with: ’s":\nKolakoski sequence: "kol"\nPossibly kolakoski? "is_possible_kolakoski(kol))</syntaxhighlight>
{{out}}
<pre>
Starting with: [1, 2]:
Kolakoski sequence: [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
Possibly kolakoski? 1B
Starting with: [2, 1]:
Kolakoski sequence: [2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2]
Possibly kolakoski? 1B
Starting with: [1, 3, 1, 2]:
Kolakoski sequence: [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]
Possibly kolakoski? 1B
Starting with: [1, 3, 2, 1]:
Kolakoski sequence: [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]
Possibly kolakoski? 0B
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">kolakoski: function [a, length][
result: array.of: length 0
i: new 0
k: new 0
loop.forever a 'x [
result\[i]: x
if result\[k] > 1 [
loop 1..dec result\[k] 'j [
inc 'i
if i = length -> return result
result\[i]: result\[i-1]
]
]
inc 'i
if i = length -> return result
inc 'k
]
return result
]
possibleKolakoski?: function [seq][
prev: seq\0
count: new 1
rle: new []
loop 1..dec size seq 'i [
if? seq\[i] = prev -> inc 'count
else [
'rle ++ count
count: new 1
prev: seq\[i]
]
]
loop.with:'i rle 'val [
if val <> seq\[i] -> return false
]
return true
]
Seqs: [[1 2] [2 1] [1 3 1 2] [1 3 2 1]]
Lens: [20 20 30 30]
loop couple Seqs Lens 'c [
generated: kolakoski c\0 c\1
print ["First" c\1 "members of the sequence generated by" c\0 ":"]
print generated
print ["Possible Kolakoski sequence?" possibleKolakoski? generated]
print ""
]</syntaxhighlight>
{{out}}
<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|C}}==
{{trans|Kotlin}}
<
#include <stdlib.h>
Line 140 ⟶ 265:
}
return 0;
}</
{{output}}
Line 159 ⟶ 284:
[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|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace KolakoskiSequence {
class Crutch {
public readonly int len;
public int[] s;
public int i;
public Crutch(int len) {
this.len = len;
s = new int[len];
i = 0;
}
public void Repeat(int count) {
for (int j = 0; j < count; j++) {
if (++i == len) return;
s[i] = s[i - 1];
}
}
}
static class Extension {
public static int NextInCycle(this int[] self, int index) {
return self[index % self.Length];
}
public static int[] Kolakoski(this int[] self, int len) {
Crutch c = new Crutch(len);
int k = 0;
while (c.i < len) {
c.s[c.i] = self.NextInCycle(k);
if (c.s[k] > 1) {
c.Repeat(c.s[k] - 1);
}
if (++c.i == len) return c.s;
k++;
}
return c.s;
}
public static bool PossibleKolakoski(this int[] self) {
int[] rle = new int[self.Length];
int prev = self[0];
int count = 1;
int pos = 0;
for (int i = 1; i < self.Length; i++) {
if (self[i] == prev) {
count++;
}
else {
rle[pos++] = count;
count = 1;
prev = self[i];
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for (int i = 0; i < pos; i++) {
if (rle[i] != self[i]) {
return false;
}
}
return true;
}
public static string AsString(this int[] self) {
StringBuilder sb = new StringBuilder("[");
int count = 0;
foreach (var item in self) {
if (count > 0) {
sb.Append(", ");
}
sb.Append(item);
count++;
}
return sb.Append("]").ToString();
}
}
class Program {
static void Main(string[] args) {
int[][] ias = {
new int[]{1, 2},
new int[]{2, 1},
new int[]{1, 3, 1, 2},
new int[]{1, 3, 2, 1}
};
int[] lens = { 20, 20, 30, 30 };
for (int i = 0; i < ias.Length; i++) {
int len = lens[i];
int[] kol = ias[i].Kolakoski(len);
Console.WriteLine("First {0} members of the sequence by {1}: ", len, ias[i].AsString());
Console.WriteLine(kol.AsString());
Console.WriteLine("Possible Kolakoski sequence? {0}", kol.PossibleKolakoski());
Console.WriteLine();
}
}
}
}</syntaxhighlight>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include <vector>
using Sequence = std::vector<int>;
std::ostream& operator<<(std::ostream& os, const Sequence& v) {
os << "[ ";
for (const auto& e : v) {
std::cout << e << ", ";
}
os << "]";
return os;
}
int next_in_cycle(const Sequence& s, size_t i) {
return s[i % s.size()];
}
Sequence gen_kolakoski(const Sequence& s, int n) {
Sequence seq;
for (size_t i = 0; seq.size() < n; ++i) {
const int next = next_in_cycle(s, i);
Sequence nv(i >= seq.size() ? next : seq[i], next);
seq.insert(std::end(seq), std::begin(nv), std::end(nv));
}
return { std::begin(seq), std::begin(seq) + n };
}
bool is_possible_kolakoski(const Sequence& s) {
Sequence r;
for (size_t i = 0; i < s.size();) {
int count = 1;
for (size_t j = i + 1; j < s.size(); ++j) {
if (s[j] != s[i]) break;
++count;
}
r.push_back(count);
i += count;
}
for (size_t i = 0; i < r.size(); ++i) if (r[i] != s[i]) return false;
return true;
}
int main() {
std::vector<Sequence> seqs = {
{ 1, 2 },
{ 2, 1 },
{ 1, 3, 1, 2 },
{ 1, 3, 2, 1 }
};
for (const auto& s : seqs) {
auto kol = gen_kolakoski(s, s.size() > 2 ? 30 : 20);
std::cout << "Starting with: " << s << ": " << std::endl << "Kolakoski sequence: "
<< kol << std::endl << "Possibly kolakoski? " << is_possible_kolakoski(kol) << std::endl;
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>Starting with: [ 1, 2, ]:
Kolakoski sequence: [ 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, ]
Possibly kolakoski? 1
Starting with: [ 2, 1, ]:
Kolakoski sequence: [ 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, ]
Possibly kolakoski? 1
Starting with: [ 1, 3, 1, 2, ]:
Kolakoski sequence: [ 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, ]
Possibly kolakoski? 1
Starting with: [ 1, 3, 2, 1, ]:
Kolakoski sequence: [ 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, ]
Possibly kolakoski? 0</pre>
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="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;
}
}</syntaxhighlight>
{{out}}
<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? Yes
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? Yes
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? Yes
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? no</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
import "fmt"
func nextInCycle(c []int, index int) int {
return c[index % len(c)]
}
func kolakoski(c []int, slen int) []int {
s := make([]int, slen)
i, k := 0, 0
for {
s[i] = nextInCycle(c, k)
if s[k] > 1 {
for j := 1; j < s[k]; j++ {
i++
if i == slen {
return s
}
s[i] = s[i - 1]
}
}
i++
if i == slen {
return s
}
k++
}
}
func possibleKolakoski(s []int) bool {
slen := len(s)
rle := make([]int, 0, slen)
prev := s[0]
count := 1
for i := 1; i < slen; i++ {
if s[i] == prev {
count++
} else {
rle = append(rle, 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 < len(rle); i++ {
if rle[i] != s[i] {
return false
}
}
return true
}
func printInts(ia []int, suffix string) {
fmt.Print("[")
alen := len(ia)
for i := 0; i < alen; i++ {
fmt.Print(ia[i])
if i < alen - 1 {
fmt.Print(", ")
}
}
fmt.Printf("]%s\n", suffix)
}
func main() {
ias := make([][]int, 4)
ias[0] = []int{1, 2}
ias[1] = []int{2, 1}
ias[2] = []int{1, 3, 1, 2}
ias[3] = []int{1, 3, 2, 1}
slens := []int{20, 20, 30, 30}
for i, ia := range ias {
slen := slens[i]
kol := kolakoski(ia, slen)
fmt.Printf("First %d members of the sequence generated by ", slen)
printInts(ia, ":")
printInts(kol, "")
p := possibleKolakoski(kol)
poss := "Yes"
if !p {
poss = "No"
}
fmt.Println("Possible Kolakoski sequence?", poss, "\n")
}
}</syntaxhighlight>
{{out}}
<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? Yes
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? Yes
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? Yes
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? No
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.List (group)
import Control.Monad (forM_)
replicateAtLeastOne :: Int -> a -> [a]
replicateAtLeastOne n x = x : replicate (n-1) x
zipWithLazy :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLazy f ~(x:xs) ~(y:ys) = f x y : zipWithLazy f xs ys
kolakoski :: [Int] -> [Int]
kolakoski items = s
where s = concat $ zipWithLazy replicateAtLeastOne s $ cycle items
rle :: Eq a => [a] -> [Int]
rle = map length . group
sameAsRleUpTo :: Int -> [Int] -> Bool
sameAsRleUpTo n s = r == take (length r) prefix
where prefix = take n s
r = init $ rle prefix
main :: IO ()
main = forM_ [([1, 2], 20),
([2, 1], 20),
([1, 3, 1, 2], 30),
([1, 3, 2, 1], 30)]
$ \(items, n) -> do
putStrLn $ "First " ++ show n ++ " members of the sequence generated by " ++ show items ++ ":"
let s = kolakoski items
print $ take n s
putStrLn $ "Possible Kolakoski sequence? " ++ show (sameAsRleUpTo n s)
putStrLn ""</syntaxhighlight>
{{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|J}}==
<syntaxhighlight lang="j">
NB. cyclic
create_cycle_=: 3 :0
I=: 0
A=: y
N=: # A
)
next_cycle_=: 3 :0
r=. A {~ N | I
I=: >: I
r
)
NB. kolakoski
kolakoski =: 30&$: :(dyad define) NB. TERMS kolakoski ALPHABET
c=. y conew'cycle'
s=. i. 0
term=. 0
while. x > # s do.
s=. (, ([: #~ next__c)`(term&{ # next__c)@.(term < #)) s
term=. >: term
end.
s
)
test=: (({.~ #) -: ]) }:@:(#;.1~ (1 , 2&(~:/\)))
</syntaxhighlight>
test cuts the data at a vector of frets where successive pairs are unequal. The groups are tallied, giving run length.
<pre>
f=: (;~ test)@:kolakoski
(; f)&> 1 2 ; 2 1 ; 1 3 1 2 ; 1 3 2 1
┌───────┬─┬─────────────────────────────────────────────────────────────┐
│1 2 │1│1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 │
├───────┼─┼─────────────────────────────────────────────────────────────┤
│2 1 │1│2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 1│
├───────┼─┼─────────────────────────────────────────────────────────────┤
│1 3 1 2│1│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 │
├───────┼─┼─────────────────────────────────────────────────────────────┤
│1 3 2 1│0│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 1│
└───────┴─┴─────────────────────────────────────────────────────────────┘
</pre>
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.util.Arrays;
public class Kolakoski {
private static class Crutch {
final int len;
int[] s;
int i;
Crutch(int len) {
this.len = len;
s = new int[len];
i = 0;
}
void repeat(int count) {
for (int j = 0; j < count; j++) {
if (++i == len) return;
s[i] = s[i - 1];
}
}
}
private static int nextInCycle(final int[] self, int index) {
return self[index % self.length];
}
private static int[] kolakoski(final int[] self, int len) {
Crutch c = new Crutch(len);
int k = 0;
while (c.i < len) {
c.s[c.i] = nextInCycle(self, k);
if (c.s[k] > 1) {
c.repeat(c.s[k] - 1);
}
if (++c.i == len) return c.s;
k++;
}
return c.s;
}
private static boolean possibleKolakoski(final int[] self) {
int[] rle = new int[self.length];
int prev = self[0];
int count = 1;
int pos = 0;
for (int i = 1; i < self.length; i++) {
if (self[i] == prev) {
count++;
} else {
rle[pos++] = count;
count = 1;
prev = self[i];
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for (int i = 0; i < pos; i++) {
if (rle[i] != self[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] ias = new int[][]{
new int[]{1, 2},
new int[]{2, 1},
new int[]{1, 3, 1, 2},
new int[]{1, 3, 2, 1}
};
int[] lens = new int[]{20, 20, 30, 30};
for (int i=0; i<ias.length; i++) {
int len = lens[i];
int[] kol = kolakoski(ias[i], len);
System.out.printf("First %d members of the sequence generated by %s: \n", len, Arrays.toString(ias[i]));
System.out.printf("%s\n", Arrays.toString(kol));
System.out.printf("Possible Kolakoski sequence? %s\n\n", possibleKolakoski(kol));
}
}
}</syntaxhighlight>
{{out}}
<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|jq}}==
This section is based on a kolakoski generator that continues
indefinitely.
Thanks to jq's backtracking semantics,
we only need a "cycle" generator
that cycles indefinitely often:
<syntaxhighlight lang="jq">def cycle:
def c: .[], c;
c;</syntaxhighlight>
<syntaxhighlight lang="jq">
# Input: an array
# Output: the corresponding kolakoski sequence.
# This version of the kolakoski generator is optimized to the extent
# that it avoids storing the full sequence by removing the first item
# in the .s array at each iteration.
def kolakoski:
foreach cycle as $next ( {s: []};
# ensure the next element occurs .s[0] times
.s += [$next]
| .extra = [range(0; .s[0]-1) as $i | $next]
| .s = .s[1:] + .extra
;
$next, .extra[] ) ;
def kolakoski($len): limit($len; kolakoski);
def iskolakoski:
def rle:
. as $seq
| reduce range(1;length) as $i ({rle:[], count:1};
if $seq[$i] == $seq[$i - 1]
then .count += 1
else .rle = .rle + [.count]
| .count = 1
end)
| .rle;
rle | . == .[0 : length] ;
</syntaxhighlight>
Testing
<syntaxhighlight lang="jq">
def tests: [[[1, 2], 20], [[2, 1] ,20], [[1, 3, 1, 2], 30], [[1, 3, 2, 1], 30]];
tests[] as [$a, $n]
| $a
| [kolakoski($n)] as $k
| "First \($n) of kolakoski sequence for \($a):", $k, "check: \($k | if iskolakoski then "✓" else "❌" end )", ""
</syntaxhighlight>
{{out}}
Invocation: jq -nr -f kolakoski.jq
<pre>
First 20 of kolakoski sequence for [1,2]:
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
check: ✓
First 20 of kolakoski sequence for [2,1]:
[2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2]
check: ✓
First 30 of kolakoski sequence for [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]
check: ✓
First 30 of kolakoski sequence for [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]
check: ✓
</pre>
=={{header|Julia}}==
{{trans|C}}
<syntaxhighlight lang="julia">function kolakoski(vec, len)
seq = Vector{Int}()
k = 0
denom = length(vec)
while length(seq) < len
n = vec[k % denom + 1]
k += 1
seq = vcat(seq, repeat([n], k > length(seq) ? n : seq[k]))
end
seq[1:len]
end
function iskolakoski(seq)
count = 1
rle = Vector{Int}()
for i in 2:length(seq)
if seq[i] == seq[i - 1]
count += 1
else
push!(rle, count)
count = 1
end
end
rle == seq[1:length(rle)]
end
const tests = [[[1, 2], 20],[[2, 1] ,20], [[1, 3, 1, 2], 30], [[1, 3, 2, 1], 30]]
for t in tests
vec, n = t[1], t[2]
seq = kolakoski(vec, n)
println("Kolakoski from $(vec): first $n numbers are $seq.")
println("\t\tDoes this look like a Kolakoski sequence? ", iskolakoski(seq) ? "Yes" : "No")
end
</syntaxhighlight> {{output}} <pre>
Kolakoski from [1, 2]: first 20 numbers are [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1].
Does this look like a Kolakoski sequence? Yes
Kolakoski from [2, 1]: first 20 numbers are [2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2].
Does this look like a Kolakoski sequence? Yes
Kolakoski from [1, 3, 1, 2]: first 30 numbers are [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].
Does this look like a Kolakoski sequence? Yes
Kolakoski from [1, 3, 2, 1]: first 30 numbers are [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].
Does this look like a Kolakoski sequence? No
</pre>
=={{header|Kotlin}}==
<
fun IntArray.nextInCycle(index: Int) = this[index % this.size]
Line 219 ⟶ 1,046:
println("Possible Kolakoski sequence? ${if (p) "Yes" else "No"}\n")
}
}</
{{output}}
Line 241 ⟶ 1,068:
</pre>
=={{header|
{{trans|C}}
<syntaxhighlight lang="lua">function next_in_cycle(c,length,index)
local pos = index % length
return c[pos]
end
local k = 0
while true do
s[i] = next_in_cycle(c,clen,k)
if s[k] > 1 then
for j=1,s[k]-1 do
i = i + 1
if i == slen then
return nil
end
s[i] = s[i - 1]
end
end
i = i + 1
if i == slen then
return nil
end
k = k + 1
end
return nil
end
function possible_kolakoski(s,length)
local j = 0
local prev = s[0]
local count = 1
local rle = {}
local result = "True"
for i=0,length do
rle[i] = 0
end
for i=1,length-1 do
if s[i] == prev then
count = count + 1
else
rle[j] = count
j = j + 1
count = 1
prev = s[i]
end
end
-- no point adding the final 'count' to rle as we're not going to compare it anyway
for i=0,j-1 do
if rle[i] ~= s[i] then
result = "False"
break
end
end
return result
end
function print_array(a)
io.write("[")
for i=0,#a do
if i>0 then
io.write(", ")
end
io.write(a[i])
end
io.write("]")
end
-- main
local c0 = {[0]=1, [1]=2}
local c1 = {[0]=2, [1]=1}
local c2 = {[0]=1, [1]=3, [2]=1, [3]=2}
local c3 = {[0]=1, [1]=3, [2]=2, [3]=1}
local cs = {[0]=c0, [1]=c1, [2]=c2, [3]=c3}
local clens = {[0]=2, [1]=2, [2]=4, [3]=4}
local slens = {[0]=20, [1]=20, [2]=30, [3]=30}
for i=0,3 do
local clen = clens[i]
local slen = slens[i]
local s = {}
for j=0,slen-1 do
s[j] = 0
end
kolakoski(cs[i],s,clen,slen)
io.write(string.format("First %d members of the sequence generated by ", slen))
print_array(cs[i])
print(":")
print_array(s)
print()
local p = possible_kolakoski(s,slen)
print(string.format("Possible Kolakoski sequence? %s", p))
print()
end</syntaxhighlight>
{{out}}
<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|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[KolakoskiGen]
KolakoskiGen[start_List, its_Integer] := Module[{c, s, k, cnext, sk},
s = {};
k = 1;
c = start;
Do[
cnext = First[c];
c = RotateLeft[c];
AppendTo[s, cnext];
sk = s[[k]];
If[sk > 1,
s = Join[s, ConstantArray[cnext, sk - 1]]
];
k += 1;
,
{its}
];
s
]
run = Take[KolakoskiGen[{1, 2}, 20], 20]
check = Length /@ Split[%];
check === Take[run, Length[check]]
run = Take[KolakoskiGen[{2, 1}, 20], 20]
check = Length /@ Split[%];
check === Take[run, Length[check]]
run = Take[KolakoskiGen[{1, 3, 1, 2}, 30], 30]
check = Length /@ Split[%];
check === Take[run, Length[check]]</syntaxhighlight>
{{out}}
<pre>{1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1}
True
{2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2}
True
{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}
True
{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}
False</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">template nextInCycle(a: openArray[int]; index: Natural): int =
a[index mod a.len]
#---------------------------------------------------------------------------------------------------
func kolakoski(a: openArray[int]; length: Positive): seq[int] =
result.setLen(length)
var i, k = 0
while true:
result[i] = a.nextInCycle(k)
if result[k] > 1:
for j in 1..<result[k]:
inc i
if i == length: return
result[i] = result[i - 1]
inc i
if i == length: return
inc k
#---------------------------------------------------------------------------------------------------
func possibleKolakoski(a: openArray[int]): bool =
var
rle: seq[int]
prev = a[0]
count = 1
for i in 1..a.high:
if a[i] == prev:
inc count
else:
rle.add count
count = 1
prev = a[i]
# No point adding final 'count' to rle as we're not going to compare it anyway.
for i, val in rle:
if val != a[i]: return false
result = true
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
import sequtils, strformat
const
Ias = [@[1, 2], @[2, 1], @[1, 3, 1, 2], @[1, 3, 2, 1]]
Lengths = [20, 20, 30, 30]
for (length, ia) in zip(Lengths, Ias):
let kol = ia.kolakoski(length)
echo &"First {length} members of the sequence generated by {($ia)[1..^1]}:"
echo ($kol)[1..^1]
let s = if kol.possibleKolakoski(): "Yes" else: "No"
echo "Possible Kolakoski sequence? " & s & '\n'</syntaxhighlight>
{{out}}
<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? Yes
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? Yes
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? Yes
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? No</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">sub kolakoski {
my($terms,@seed) = @_;
my @k;
my $k = $seed[0] == 1 ? 1 : 0;
if ($k == 1) { @k = (1, split //, (($seed[1]) x $seed[1])) }
else { @k = ($seed[0]) x $seed[0] }
do {
$k++;
push @k, ($seed[$k % @seed]) x $k[$k];
} until $terms <= @k;
@k[0..$terms-1]
}
sub rle {
(my $string = join '', @_) =~ s/((.)\2*)/length $1/eg;
split '', $string
}
for ([20,1,2], [20,2,1], [30,1,3,1,2], [30,1,3,2,1]) {
$terms = shift @$_;
print "\n$terms members of the series generated from [@$_] is:\n";
print join(' ', @kolakoski = kolakoski($terms, @$_)) . "\n";
$status = join('', @rle = rle(@kolakoski)) eq join('', @kolakoski[0..$#rle]) ? 'True' : 'False';
print "Looks like a Kolakoski sequence?: $status\n";
}</syntaxhighlight>
{{out}}
<pre>
=={{header|Phix}}==
{{trans|C}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">kolakoski</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">))+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">c</span><span style="color: #0000FF;">:</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">possible_kolakoski</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rle</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">rle</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">count</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- (final count probably incomplete, so ignore it)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">rle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rle</span><span style="color: #0000FF;">)]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">cycles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">30</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kolakoski</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First %d members of the sequence generated by %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">s</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">possible_kolakoski</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Possible Kolakoski sequence? %s\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">?</span> <span style="color: #008000;">"Yes"</span> <span style="color: #0000FF;">:</span> <span style="color: #008000;">"No"</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<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? Yes
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? Yes
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? Yes
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? No
</pre>
=={{header|Python}}==
Python 3.6+
<
def cycler(start_items):
Line 308 ⟶ 1,449:
def is_series_eq_its_rle(series):
rle = _run_len_encoding(series)
return (series[:len(rle)] == rle) if rle else not series
if __name__ == '__main__':
Line 317 ⟶ 1,458:
print(f' {s}')
ans = 'YES' if is_series_eq_its_rle(s) else 'NO'
print(f' Does it look like a Kolakoski sequence: {ans}')</
{{out}}
Line 336 ⟶ 1,477:
[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]
Does it look like a Kolakoski sequence: NO</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.04.01}}
<syntaxhighlight lang="raku" line>sub kolakoski (*@seed) {
my $k = @seed[0] == 1 ?? 1 !! 0;
my @k = flat @seed[0] == 1 ?? (1, @seed[1] xx @seed[1]) !! @seed[0] xx @seed[0],
{ $k++; @seed[$k % @seed] xx @k[$k] } … *
}
sub rle (*@series) { @series.join.subst(/((.)$0*)/, -> { $0.chars }, :g).comb».Int }
# Testing
for [1, 2], 20,
[2, 1], 20,
[1, 3, 1, 2], 30,
[1, 3, 2, 1], 30
-> @seed, $terms {
say "\n## $terms members of the series generated from { @seed.perl } is:\n ",
my @kolakoski = kolakoski(@seed)[^$terms];
my @rle = rle @kolakoski;
say " Looks like a Kolakoski sequence?: ", @rle[*] eqv @kolakoski[^@rle];
}</syntaxhighlight>
{{out}}
<pre>## 20 members of the series generated from [1, 2] is:
[1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1]
Looks like a Kolakoski sequence?: True
## 20 members of the series generated from [2, 1] is:
[2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2]
Looks like a Kolakoski sequence?: True
## 30 members of the series generated from [1, 3, 1, 2] is:
[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]
Looks like a Kolakoski sequence?: True
## 30 members of the series generated from [1, 3, 2, 1] is:
[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]
Looks like a Kolakoski sequence?: False</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def create_generator(ar)
Enumerator.new do |y|
cycle = ar.cycle
s = []
loop do
t = cycle.next
s.push(t)
v = s.shift
y << v
(v-1).times{s.push(t)}
end
end
end
def rle(ar)
ar.slice_when{|a,b| a != b}.map(&:size)
end
[[20, [1,2]],
[20, [2,1]],
[30, [1,3,1,2]],
[30, [1,3,2,1]]].each do |num,ar|
puts "\nFirst #{num} of the sequence generated by #{ar.inspect}:"
p res = create_generator(ar).take(num)
puts "Possible Kolakoski sequence? #{res.join.start_with?(rle(res).join)}"
end</syntaxhighlight>
{{out}}
<pre>
First 20 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 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 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 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|Rust}}==
<syntaxhighlight lang="rust">
use itertools::Itertools;
fn get_kolakoski_sequence(iseq: &[usize], size: &usize) -> Vec<usize> {
assert!(*size > 0);
assert!(!iseq.is_empty());
let mut kseq: Vec<usize> = Vec::default();
// create an itertor which keeps repeating the initial sequence infinitely
let repeater = iseq.iter().cloned().cycle();
// push the very first element, repeated as many times as the number
kseq.extend_from_slice(&vec![*iseq.get(0).unwrap()].repeat(*iseq.get(0).unwrap()));
//start cycling throught the initial sequence, but skip the very first one
for (k_counter, elem) in repeater.enumerate().skip(1) {
// push the given element
kseq.push(elem);
// and repeat the current element as many times
// as it's needed based on the previous elements
kseq.extend_from_slice(&vec![elem].repeat(*kseq.get(k_counter).unwrap() - 1));
// finish generation when the Kolakoski sequence has reached the given length
if kseq.len() >= *size {
break;
}
}
// truncate it as it might have more elements than needed
kseq[0..*size].to_vec()
}
fn is_kolakoski(kseq: &[usize]) -> bool {
assert!(!kseq.is_empty());
// calculate the RLE
let rle: Vec<usize> = kseq
.iter()
.batching(|it| {
it.next()
.map(|v| it.take_while_ref(|&v2| v2 == v).count() + 1)
})
.collect();
rle.iter().zip(kseq).filter(|&(a, b)| a == b).count() == rle.len()
}
fn main() {
let lengths = vec![20, 20, 30, 30];
let seqs = vec![vec![1, 2], vec![2, 1], vec![1, 3, 1, 2], vec![1, 3, 2, 1]];
for (seq, length) in seqs.iter().zip(&lengths) {
let kseq = get_kolakoski_sequence(&seq, length);
println!("Starting sequence: {:?}", seq);
println!("Kolakoski sequence: {:?}", kseq);
println!("Possible Kolakoski sequence? {:?}", is_kolakoski(&kseq));
}
}
</syntaxhighlight>
{{out}}
<pre>
Starting sequence: [1, 2]
Kolakoski sequence: [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
Possible Kolakoski sequence? true
Starting sequence: [2, 1]
Kolakoski sequence: [2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2]
Possible Kolakoski sequence? true
Starting sequence: [1, 3, 1, 2]
Kolakoski sequence: [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
Starting sequence: [1, 3, 2, 1]
Kolakoski sequence: [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|Sidef}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">func create_generator(arr) {
Enumerator({|f|
var s = []
var i = 0
loop {
var t = arr[i++ % arr.len]
s << t
f(var v = s.shift)
s << (v-1).of(t)...
}
})
}
var tests = [
[20, [1,2]],
[20, [2,1]],
[30, [1,3,1,2]],
[30, [1,3,2,1]]
]
for num,arr in (tests) {
say "\nFirst #{num} of the sequence generated by #{arr}:"
var res = create_generator(arr).first(num)
var rle = res.run_length.map{.tail}
say "#{res}\nPossible Kolakoski sequence? #{res.first(rle.len) == rle}"
}</syntaxhighlight>
{{out}}
<pre>
First 20 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 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 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 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|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Imports System.Runtime.CompilerServices
Imports System.Text
Module Module1
Class Crutch
Public ReadOnly len As Integer
Public s() As Integer
Public i As Integer
Public Sub New(len As Integer)
Me.len = len
s = New Integer(len - 1) {}
i = 0
End Sub
Public Sub Repeat(count As Integer)
For j = 1 To count
i += 1
If i = len Then
Return
End If
s(i) = s(i - 1)
Next
End Sub
End Class
<Extension()>
Public Function NextInCycle(self As Integer(), index As Integer) As Integer
Return self(index Mod self.Length)
End Function
<Extension()>
Public Function Kolakoski(self As Integer(), len As Integer) As Integer()
Dim c As New Crutch(len)
Dim k = 0
While c.i < len
c.s(c.i) = self.NextInCycle(k)
If c.s(k) > 1 Then
c.Repeat(c.s(k) - 1)
End If
c.i += 1
If c.i = len Then
Return c.s
End If
k += 1
End While
Return c.s
End Function
<Extension()>
Public Function PossibleKolakoski(self As Integer()) As Boolean
Dim rle(self.Length) As Integer
Dim prev = self(0)
Dim count = 1
Dim pos = 0
For i = 2 To self.Length
If self(i - 1) = prev Then
count += 1
Else
rle(pos) = count
pos += 1
count = 1
prev = self(i - 1)
End If
Next
REM no point adding final 'count' to rle as we're not going to compare it anyway
For i = 1 To pos
If rle(i - 1) <> self(i - 1) Then
Return False
End If
Next
Return True
End Function
<Extension()>
Public Function AsString(self As Integer()) As String
Dim sb As New StringBuilder("[")
Dim it = self.GetEnumerator()
If it.MoveNext Then
sb.Append(it.Current)
End If
While it.MoveNext
sb.Append(", ")
sb.Append(it.Current)
End While
Return sb.Append("]").ToString
End Function
Sub Main()
Dim ias()() As Integer = {New Integer() {1, 2}, New Integer() {2, 1}, New Integer() {1, 3, 1, 2}, New Integer() {1, 3, 2, 1}}
Dim lens() As Integer = {20, 20, 30, 30}
For i = 1 To ias.Length
Dim len = lens(i - 1)
Dim kol = ias(i - 1).Kolakoski(len)
Console.WriteLine("First {0} members of the sequence by {1}: ", len, ias(i - 1).AsString)
Console.WriteLine(kol.AsString)
Console.WriteLine("Possible Kolakoski sequence? {0}", kol.PossibleKolakoski)
Console.WriteLine()
Next
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>First 20 members of the sequence 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 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 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 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|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">fn next_in_cycle(c []int, index int) int {
return c[index % c.len]
}
fn kolakoski(c []int, slen int) []int {
mut s := []int{len: slen}
mut i, mut k := 0, 0
for {
s[i] = next_in_cycle(c, k)
if s[k] > 1 {
for j := 1; j < s[k]; j++ {
i++
if i == slen {
return s
}
s[i] = s[i - 1]
}
}
i++
if i == slen {
return s
}
k++
}
return s
}
fn possible_kolakoski(s []int) bool {
slen := s.len
mut rle := []int{len: 0, cap:slen}
mut prev := s[0]
mut count := 1
for i in 1..slen {
if s[i] == prev {
count++
} else {
rle << count
count = 1
prev = s[i]
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for i in 0..rle.len {
if rle[i] != s[i] {
return false
}
}
return true
}
fn print_ints(ia []int, suffix string) {
print("[")
alen := ia.len
for i in 0.. alen {
print(ia[i])
if i < alen - 1 {
print(", ")
}
}
println("]$suffix")
}
fn main() {
mut ias := [][]int{len: 4}
ias[0] = [1, 2]
ias[1] = [2, 1]
ias[2] = [1, 3, 1, 2]
ias[3] = [1, 3, 2, 1]
slens := [20, 20, 30, 30]
for i, ia in ias {
slen := slens[i]
kol := kolakoski(ia, slen)
print("First $slen members of the sequence generated by ")
print_ints(ia, ":")
print_ints(kol, "")
p := possible_kolakoski(kol)
mut poss := "Yes"
if !p {
poss = "No"
}
println("Possible Kolakoski sequence? $poss \n")
}
}
</syntaxhighlight>
{{out}}
<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? Yes
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? Yes
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? Yes
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? No
</pre>
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="wren">var kolakoski = Fn.new { |c, slen|
var s = List.filled(slen, 0)
var i = 0
var k = 0
while (true) {
s[i] = c[k % c.count]
if (s[k] > 1) {
for (j in 1...s[k]) {
i = i + 1
if (i == slen) return s
s[i] = s[i-1]
}
}
i = i + 1
if (i == slen) return s
k = k + 1
}
}
var possibleKolakoski = Fn.new { |s|
var slen = s.count
var rle = []
var prev = s[0]
var count = 1
for (i in 1...slen) {
if (s[i] == prev) {
count = count + 1
} else {
rle.add(count)
count = 1
prev = s[i]
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for (i in 0...rle.count) {
if (rle[i] != s[i]) return false
}
return true
}
var ias = [
[1, 2],
[2, 1],
[1, 3, 1, 2],
[1 ,3, 2, 1]
]
var slens = [20, 20, 30, 30]
var i = 0
for (ia in ias) {
var slen = slens[i]
var kol = kolakoski.call(ia, slen)
System.write("First %(slen) members of the sequence generated by ")
System.print("%(ia):")
System.print("%(kol)")
var p = possibleKolakoski.call(kol)
var poss = p ? "Yes" : "No"
System.print("Possible Kolakoski sequence? %(poss)\n")
i = i + 1
}</syntaxhighlight>
{{out}}
<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? Yes
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? Yes
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? Yes
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? No
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
Walker.tweak(fcn(s,rk,cw){ // infinite iterator
s.append( c_next:=cw() );
Line 347 ⟶ 2,013:
}.fp(List(), Ref(0), Walker.cycle(start_items).next) )
.walk(length); // iterate length times, return list
}</
<
truncated_series.reduce(fcn(a,b,rm,s){ # if trailing singleton, it is ignored
if(a==b){ rm.inc(); return(b); }
Line 360 ⟶ 2,026:
rle:=_run_len_encoding(series);
series[0,rle.len()]==rle
}</
<
L( L(1,3,1,2), 30), L( L(1,3,2,1), 30) )){
start_items, length := sl;
Line 368 ⟶ 2,034:
println(" (%s)".fmt(( s:=kolakoski(start_items, length) ).concat(",") ));
println(" Does it look like a Kolakoski sequence: ",is_series_eq_its_rle(s) )
}</
{{out}}
<pre>
| |||