Kolakoski sequence: Difference between revisions
m (sp.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(41 intermediate revisions by 20 users not shown) | |||
Line 36: | Line 36: | ||
... |
... |
||
'''Note''' that the RLE of <code>1, 2, 2, 1, 1, ...</code> begins <code>1, 2, 2</code> |
'''Note''' that the RLE of <code>1, 2, 2, 1, 1, ...</code> begins <code>1, 2, 2</code> which is the beginning of the original sequence. The generation algorithm ensures that this will always be the case. |
||
;Task: |
;Task: |
||
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|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}}== |
=={{header|C}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 140: | Line 265: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 159: | Line 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] |
[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 |
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> |
</pre> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// Version 1.2.41 |
||
fun IntArray.nextInCycle(index: Int) = this[index % this.size] |
fun IntArray.nextInCycle(index: Int) = this[index % this.size] |
||
Line 219: | Line 1,046: | ||
println("Possible Kolakoski sequence? ${if (p) "Yes" else "No"}\n") |
println("Possible Kolakoski sequence? ${if (p) "Yes" else "No"}\n") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 241: | Line 1,068: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Lua}}== |
||
{{trans|C}} |
|||
{{works with|Rakudo|2018.04.01}} |
|||
<syntaxhighlight lang="lua">function next_in_cycle(c,length,index) |
|||
local pos = index % length |
|||
return c[pos] |
|||
end |
|||
function kolakoski(c,s,clen,slen) |
|||
local i = 0 |
|||
local k = 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] } … * |
|||
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 { |
|||
sub rle (*@series) { @series.join.subst(/((.)$0*)/, -> { $0.chars }, :g).comb».Int } |
|||
(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]) { |
|||
# Testing |
|||
$terms = shift @$_; |
|||
for [1, 2], 20, |
|||
print "\n$terms members of the series generated from [@$_] is:\n"; |
|||
[2, 1], 20, |
|||
print join(' ', @kolakoski = kolakoski($terms, @$_)) . "\n"; |
|||
[1, 3, 1, 2], 30, |
|||
$status = join('', @rle = rle(@kolakoski)) eq join('', @kolakoski[0..$#rle]) ? 'True' : 'False'; |
|||
[1, 3, 2, 1], 30 |
|||
print "Looks like a Kolakoski sequence?: $status\n"; |
|||
-> @seed, $terms { |
|||
}</syntaxhighlight> |
|||
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> |
|||
{{out}} |
{{out}} |
||
<pre> |
<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|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}}== |
=={{header|Python}}== |
||
Python 3.6+ |
Python 3.6+ |
||
< |
<syntaxhighlight lang="python">import itertools |
||
def cycler(start_items): |
def cycler(start_items): |
||
Line 308: | Line 1,449: | ||
def is_series_eq_its_rle(series): |
def is_series_eq_its_rle(series): |
||
rle = _run_len_encoding(series) |
rle = _run_len_encoding(series) |
||
return series[:len(rle)] == rle |
return (series[:len(rle)] == rle) if rle else not series |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
Line 317: | Line 1,458: | ||
print(f' {s}') |
print(f' {s}') |
||
ans = 'YES' if is_series_eq_its_rle(s) else 'NO' |
ans = 'YES' if is_series_eq_its_rle(s) else 'NO' |
||
print(f' Does it look like a Kolakoski sequence: {ans}')</ |
print(f' Does it look like a Kolakoski sequence: {ans}')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 336: | Line 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] |
[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> |
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}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl">fcn kolakoski(start_items=List(1,2), length=20){ //-->List |
||
Walker.tweak(fcn(s,rk,cw){ // infinite iterator |
Walker.tweak(fcn(s,rk,cw){ // infinite iterator |
||
s.append( c_next:=cw() ); |
s.append( c_next:=cw() ); |
||
Line 347: | Line 2,013: | ||
}.fp(List(), Ref(0), Walker.cycle(start_items).next) ) |
}.fp(List(), Ref(0), Walker.cycle(start_items).next) ) |
||
.walk(length); // iterate length times, return list |
.walk(length); // iterate length times, return list |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">fcn _run_len_encoding(truncated_series){ //List-->List |
||
truncated_series.reduce(fcn(a,b,rm,s){ # if trailing singleton, it is ignored |
truncated_series.reduce(fcn(a,b,rm,s){ # if trailing singleton, it is ignored |
||
if(a==b){ rm.inc(); return(b); } |
if(a==b){ rm.inc(); return(b); } |
||
Line 360: | Line 2,026: | ||
rle:=_run_len_encoding(series); |
rle:=_run_len_encoding(series); |
||
series[0,rle.len()]==rle |
series[0,rle.len()]==rle |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight 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) )){ |
L( L(1,3,1,2), 30), L( L(1,3,2,1), 30) )){ |
||
start_items, length := sl; |
start_items, length := sl; |
||
Line 368: | Line 2,034: | ||
println(" (%s)".fmt(( s:=kolakoski(start_items, length) ).concat(",") )); |
println(" (%s)".fmt(( s:=kolakoski(start_items, length) ).concat(",") )); |
||
println(" Does it look like a Kolakoski sequence: ",is_series_eq_its_rle(s) ) |
println(" Does it look like a Kolakoski sequence: ",is_series_eq_its_rle(s) ) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 11:56, 12 December 2023
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
2
ones, followed by3
twos, then1
ones,2
twos,1
one, ...
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
s
with the first item from the cyclec
:
1
- An index,
k
, into the, (expanding), sequence will step, or index through each item of the sequences
from the first, at its own rate.
We will arrange that the k
'th item of s
states how many times the last item of s
should 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
k
Get the next item from
c
and append it to the end of sequences
.s
will then become:
1, 2
k
was 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,2
Increment
k
Append the next item from the cycle to the list:
1, 2,2, 1
k
is 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,1
increment k
...
Note that the RLE of 1, 2, 2, 1, 1, ...
begins 1, 2, 2
which 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)
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))
- Output:
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
Arturo
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 ""
]
- 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
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;
}
- 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
C#
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();
}
}
}
}
C++
#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;
}
- Output:
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
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;
}
}
- 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
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")
}
}
- 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
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 ""
- 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
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&(~:/\)))
test cuts the data at a vector of frets where successive pairs are unequal. The groups are tallied, giving run length.
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│ └───────┴─┴─────────────────────────────────────────────────────────────┘
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));
}
}
}
- 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
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:
def cycle:
def c: .[], c;
c;
# 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] ;
Testing
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 )", ""
- Output:
Invocation: jq -nr -f kolakoski.jq
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: ✓
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
- Output:
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
Kotlin
// 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")
}
}
- 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
Lua
function next_in_cycle(c,length,index)
local pos = index % length
return c[pos]
end
function kolakoski(c,s,clen,slen)
local i = 0
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
- 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
Mathematica/Wolfram Language
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]]
- Output:
{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
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'
- 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
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";
}
- 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
Phix
with javascript_semantics function kolakoski(sequence cycle, integer n) sequence s = {} integer k = 1 while length(s)<n do integer c = cycle[mod(k-1,length(cycle))+1] s &= repeat(c,iff(k>length(s)?c:s[k])) k += 1 end while s = s[1..n] return s end function function possible_kolakoski(sequence s) integer count = 1 sequence rle = {} for i=2 to length(s) do if s[i]==s[i-1] then count += 1 else rle &= count count = 1 end if end for -- (final count probably incomplete, so ignore it) return rle = s[1..length(rle)] end function constant cycles = {{1,2},20, {2,1},20, {1,3,1,2},30, {1,3,2,1},30} for i=1 to length(cycles) by 2 do {sequence c, integer n} = cycles[i..i+1] sequence s = kolakoski(c,n) printf(1,"First %d members of the sequence generated by %s\n", {n,sprint(c)}) ?s bool p = possible_kolakoski(s) printf(1,"Possible Kolakoski sequence? %s\n\n", {iff(p ? "Yes" : "No")}) end for
- 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
Python
Python 3.6+
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}')
- 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
Raku
(formerly Perl 6)
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];
}
- 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
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
- Output:
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
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));
}
}
- Output:
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
Sidef
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}"
}
- Output:
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
Visual Basic .NET
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
- Output:
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
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")
}
}
- 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
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
}
- 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
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
}
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
}
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) )
}
- 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