Kolakoski sequence: Difference between revisions
Content added Content deleted
(Added Sidef) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
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|C}}== |
=={{header|C}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
Line 161: | Line 162: | ||
</pre> |
</pre> |
||
=={{header|C |
=={{header|C sharp|C#}}== |
||
<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; |
|||
}</lang> |
|||
{{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|C#|C sharp}}== |
|||
{{trans|Java}} |
{{trans|Java}} |
||
<lang csharp>using System; |
<lang csharp>using System; |
||
Line 341: | Line 270: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|C++}}== |
|||
<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; |
|||
}</lang> |
|||
{{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}}== |
=={{header|D}}== |
||
Line 992: | Line 993: | ||
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 |
||
Looks like a Kolakoski sequence?: False</pre> |
Looks like a Kolakoski sequence?: False</pre> |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2018.04.01}} |
|||
<lang perl6>sub kolakoski (*@seed) { |
|||
my $k = @seed[0] == 1 ?? 1 !! 0; |
|||
my @k = flat @seed[0] == 1 ?? (1, @seed[1] xx @seed[1]) !! @seed[0] xx @seed[0], |
|||
{ $k++; @seed[$k % @seed] xx @k[$k] } … * |
|||
} |
|||
sub rle (*@series) { @series.join.subst(/((.)$0*)/, -> { $0.chars }, :g).comb».Int } |
|||
# Testing |
|||
for [1, 2], 20, |
|||
[2, 1], 20, |
|||
[1, 3, 1, 2], 30, |
|||
[1, 3, 2, 1], 30 |
|||
-> @seed, $terms { |
|||
say "\n## $terms members of the series generated from { @seed.perl } is:\n ", |
|||
my @kolakoski = kolakoski(@seed)[^$terms]; |
|||
my @rle = rle @kolakoski; |
|||
say " Looks like a Kolakoski sequence?: ", @rle[*] eqv @kolakoski[^@rle]; |
|||
}</lang> |
|||
{{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|Phix}}== |
=={{header|Phix}}== |
||
Line 1,149: | Line 1,111: | ||
[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}} |
|||
<lang perl6>sub kolakoski (*@seed) { |
|||
my $k = @seed[0] == 1 ?? 1 !! 0; |
|||
my @k = flat @seed[0] == 1 ?? (1, @seed[1] xx @seed[1]) !! @seed[0] xx @seed[0], |
|||
{ $k++; @seed[$k % @seed] xx @k[$k] } … * |
|||
} |
|||
sub rle (*@series) { @series.join.subst(/((.)$0*)/, -> { $0.chars }, :g).comb».Int } |
|||
# Testing |
|||
for [1, 2], 20, |
|||
[2, 1], 20, |
|||
[1, 3, 1, 2], 30, |
|||
[1, 3, 2, 1], 30 |
|||
-> @seed, $terms { |
|||
say "\n## $terms members of the series generated from { @seed.perl } is:\n ", |
|||
my @kolakoski = kolakoski(@seed)[^$terms]; |
|||
my @rle = rle @kolakoski; |
|||
say " Looks like a Kolakoski sequence?: ", @rle[*] eqv @kolakoski[^@rle]; |
|||
}</lang> |
|||
{{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}}== |
=={{header|Ruby}}== |