Kolakoski sequence: Difference between revisions
→{{header|C#|C sharp}}
SqrtNegInf (talk | contribs) (Added Perl example) |
|||
Line 160:
Possible Kolakoski sequence? False
</pre>
=={{header|C++}}==
{{trans|D}}
<lang cpp>#include <iostream>
#include <ostream>
#include <vector>
template <typename F>
void repeat(size_t count, F action) {
for (size_t i = 0; i < count; ++i) {
action(i);
}
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
auto it = v.cbegin();
auto end = v.cend();
os << "[";
if (it != end) {
os << *it;
it = std::next(it);
}
for (; it != end; it = std::next(it)) {
os << ", " << *it;
}
return os << "]";
}
template<typename T>
auto nextInCycle(const T& c, size_t index) {
return c[index % c.size()];
}
template<typename T>
std::vector<T> kolakoski(const std::vector<T>& c, size_t len) {
std::vector<T> s(len);
size_t i = 0;
size_t k = 0;
while (i < len) {
s[i] = nextInCycle(c, k);
if (s[k] > 1) {
repeat(s[k] - 1, [&s, &i, len](size_t j) {
if (++i == len) return;
s[i] = s[i - 1];
});
}
if (++i == len) return s;
k++;
}
return s;
}
template<typename T>
bool possibleKolakoski(const std::vector<T>& c) {
auto len = c.size();
std::vector<T> rle;
auto prev = c[0];
size_t count = 1;
for (size_t i = 1; i < len; ++i) {
if (c[i] == prev) {
count++;
} else {
rle.push_back(count);
count = 1;
prev = c[i];
}
}
// no point adding final 'count' to rle as we're not going to compare it anyway
for (size_t i = 0; i < rle.size(); i++) {
if (rle[i] != c[i]) {
return false;
}
}
return true;
}
int main() {
using namespace std;
vector<vector<int>> ias = { {1, 2}, {2, 1}, {1, 3, 1, 2}, {1, 3, 2, 1} };
vector<int> lens = { 20,20,30,30 };
for (size_t i = 0; i < ias.size(); i++) {
auto len = lens[i];
auto ia = ias[i];
auto kol = kolakoski(ia, len);
cout << "First " << len << " members of the sequence generated by " << ia << ":" << endl;
cout << kol << endl;
cout << "Possible Kolakoski sequence? ";
if (possibleKolakoski(kol)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
cout << endl;
}
return 0;
}</lang>
{{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|C#|C sharp}}==
| |||