Kolakoski sequence
You are encouraged to solve this task according to the task description, using any language you may know.
The Kolakoski sequence is an infinite sequence of natural numbers, (excluding zero); with the property that:
- if you form a new sequence from the counts of runs of the same number in the first sequence, this new sequence is the same as the first sequence.
- Example
This is not a Kolakoski sequence:
1,1,2,2,2,1,2,2,1,2,...
Its sequence of run counts, (sometimes called a run length encoding, (RLE); but a true RLE also gives the character that each run encodes), is calculated like this:
- Starting from the leftmost number of the sequence we have
2ones, followed by3twos, then1ones,2twos,1one, ...
The above gives the RLE of:
2, 3, 1, 2, 1, ...
The original sequence is different from its RLE in this case. It would be the same for a true Kolakoski sequence.
- Creating a Kolakoski sequence
Lets start with the two numbers (1, 2) that we will cycle through; i.e. they will be used in this order:
1,2,1,2,1,2,....
- We start the sequence
swith the first item from the cyclec:
1 - An index,
k, into the, (expanding), sequence will step, or index through each item of the sequencesfrom the first, at its own rate.
We will arrange that the k'th item of s states how many times the last item of sshould appear at the end of s.
We started s with 1 and therefore s[k] states that it should appear only the 1 time.
Increment
kGet the next item from
cand append it to the end of sequences.swill then become:
1, 2kwas moved to the second item in the list ands[k]states that it should appear two times, so append another of the last item to the sequences:
1, 2,2Increment
kAppend the next item from the cycle to the list:
1, 2,2, 1kis now at the third item in the list that states that the last item should appear twice so add another copy of the last item to the sequences:
1, 2,2, 1,1increment k
...
Note that the RLE of 1, 2, 2, 1, 1, ... begins 1, 2, 2 whiuch is the beginning of the original sequence. The generation algorithm ensures that this will always be the case.
- Task
- Create a routine/proceedure/function/... that given an initial ordered list/array/tuple etc of the natural numbers
(1, 2), returns the next number from the list when accessed in a cycle. - Create another routine that when given the initial ordered list
(1, 2)and the minimum length of the sequence to generate; uses the first routine and the algorithm above, to generate at least the requested first members of the kolakoski sequence. - Create a routine that when given a sequence, creates the run length encoding of that sequence (as defined above) and returns the result of checking if sequence starts with the exact members of its RLE. (But note, due to sampling, do not compare the last member of the RLE).
- Show, on this page, (compactly), the first 20 members of the sequence generated from
(1, 2) - Check the sequence againt its RLE.
- Show, on this page, the first 20 members of the sequence generated from
(2, 1) - Check the sequence againt its RLE.
- Show, on this page, the first 30 members of the Kolakoski sequence generated from
(1, 3, 1, 2) - Check the sequence againt its RLE.
- Show, on this page, the first 30 members of the Kolakoski sequence generated from
(1, 3, 2, 1) - Check the sequence againt its RLE.
(There are rules on generating Kolakoski sequences from this method that are broken by the last example)
C
<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:
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
Go
<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")
}
}</lang>
- Output:
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
Haskell
<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 ""</lang>
- Output:
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
Kotlin
<lang scala>// Version 1.2.41
fun IntArray.nextInCycle(index: Int) = this[index % this.size]
fun IntArray.kolakoski(len: Int): IntArray {
val s = IntArray(len)
var i = 0
var k = 0
while (true) {
s[i] = this.nextInCycle(k)
if (s[k] > 1) {
repeat(s[k] - 1) {
if (++i == len) return s
s[i] = s[i - 1]
}
}
if (++i == len) return s
k++
}
}
fun IntArray.possibleKolakoski(): Boolean {
val len = this.size
val rle = mutableListOf<Int>()
var prev = this[0]
var count = 1
for (i in 1 until len) {
if (this[i] == prev) {
count++
}
else {
rle.add(count)
count = 1
prev = this[i]
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for (i in 0 until rle.size) {
if (rle[i] != this[i]) return false
}
return true
}
fun main(args: Array<String>) {
val ias = listOf(
intArrayOf(1, 2), intArrayOf(2, 1),
intArrayOf(1, 3, 1, 2), intArrayOf(1, 3, 2, 1)
)
val lens = intArrayOf(20, 20, 30, 30)
for ((i, ia) in ias.withIndex()) {
val len = lens[i]
val kol = ia.kolakoski(len)
println("First $len members of the sequence generated by ${ia.asList()}:")
println(kol.asList())
val p = kol.possibleKolakoski()
println("Possible Kolakoski sequence? ${if (p) "Yes" else "No"}\n")
}
}</lang>
- Output:
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
Perl 6
<lang perl6>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];
}</lang>
- Output:
## 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
Python
Python 3.6+
<lang python>import itertools
def cycler(start_items): return itertools.cycle(start_items).__next__
def _kolakoski_gen(start_items):
s, k = [], 0
c = cycler(start_items)
while True:
c_next = c()
s.append(c_next)
sk = s[k]
yield sk
if sk > 1:
s += [c_next] * (sk - 1)
k += 1
def kolakoski(start_items=(1, 2), length=20):
return list(itertools.islice(_kolakoski_gen(start_items), length))
def _run_len_encoding(truncated_series):
return [len(list(group)) for grouper, group in itertools.groupby(truncated_series)][:-1]
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__':
for start_items, length in [((1, 2), 20), ((2, 1), 20),
((1, 3, 1, 2), 30), ((1, 3, 2, 1), 30)]:
print(f'\n## {length} members of the series generated from {start_items} is:')
s = kolakoski(start_items, length)
print(f' {s}')
ans = 'YES' if is_series_eq_its_rle(s) else 'NO'
print(f' Does it look like a Kolakoski sequence: {ans}')</lang>
- Output:
## 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] Does it look like a Kolakoski sequence: YES ## 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] Does it look like a Kolakoski sequence: YES ## 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] Does it look like a Kolakoski sequence: YES ## 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] Does it look like a Kolakoski sequence: NO
zkl
<lang zkl>fcn kolakoski(start_items=List(1,2), length=20){ //-->List
Walker.tweak(fcn(s,rk,cw){ // infinite iterator
s.append( c_next:=cw() );
sk:=s[rk.inc()]; // inc returns previous value, ie k++
if(sk>1) s.extend((List.createLong(sk - 1,c_next))); // list of sk cn's
sk // where we are in s, not end of s
}.fp(List(), Ref(0), Walker.cycle(start_items).next) )
.walk(length); // iterate length times, return list
}</lang> <lang zkl>fcn _run_len_encoding(truncated_series){ //List-->List
truncated_series.reduce(fcn(a,b,rm,s){ # if trailing singleton, it is ignored
if(a==b){ rm.inc(); return(b); }
s.append(rm.value);
rm.set(1);
b
}.fp2(Ref(1),s:=List()) );
s
} fcn is_series_eq_its_rle(series){ //-->Bool
rle:=_run_len_encoding(series); series[0,rle.len()]==rle
}</lang> <lang zkl>foreach sl in (List( L( L(1,2), 20), L( L(2, 1), 20),
L( L(1,3,1,2), 30), L( L(1,3,2,1), 30) )){
start_items, length := sl;
println("First %d members of the series generated from (%s) are:"
.fmt(length,start_items.concat(",")));
println(" (%s)".fmt(( s:=kolakoski(start_items, length) ).concat(",") ));
println(" Does it look like a Kolakoski sequence: ",is_series_eq_its_rle(s) )
}</lang>
- Output:
First 20 members of the series generated from (1,2) are: (1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1) Does it look like a Kolakoski sequence: True First 20 members of the series generated from (2,1) are: (2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2) Does it look like a Kolakoski sequence: True First 30 members of the series generated from (1,3,1,2) 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 it look like a Kolakoski sequence: True First 30 members of the series generated from (1,3,2,1) 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 it look like a Kolakoski sequence: False