Kolakoski sequence: Difference between revisions

Content added Content deleted

Inline

@@ Line 162: / Line 162: @@
 =={{header|C++}}==
-{{trans|D}}
 <lang cpp>#include <iostream>
-#include <ostream>
 #include <vector>
+using Sequence = std::vector<int>;
-template <typename F>
-void repeat(size_t count, F action) {
-    for (size_t i = 0; i < count; ++i) {
-        action(i);
-    }
-}
+std::ostream& operator<<(std::ostream& os, const Sequence& v) {
-template<typename T>
+  os << "[ ";
-std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
-    auto it = v.cbegin();
+  for (const auto& e : v) {
-    auto end = v.cend();
+    std::cout << e << ", ";
+  }
-    os << "[";
+  os << "]";
+  return os;
-    if (it != end) {
-        os << *it;
-        it = std::next(it);
-    }
-    for (; it != end; it = std::next(it)) {
-        os << ", " << *it;
-    }
-    return os << "]";
 }
+int next_in_cycle(const Sequence& s, size_t i) {
-template<typename T>
+  return s[i % s.size()];
-auto nextInCycle(const T& c, size_t index) {
-    return c[index % c.size()];
 }
+Sequence gen_kolakoski(const Sequence& s, int n) {
-template<typename T>
+  Sequence seq;
-std::vector<T> kolakoski(const std::vector<T>& c, size_t len) {
+  for (size_t i = 0; seq.size() < n; ++i) {
-    std::vector<T> s(len);
-    size_t i = 0;
+    const int next = next_in_cycle(s, i);
+    std::vector<int> nv(i >= seq.size() ? next : seq[i], next);
-    size_t k = 0;
+    seq.insert(std::end(seq), std::begin(nv), std::end(nv));
-    while (i < len) {
+  }
-        s[i] = nextInCycle(c, k);
+  return { std::begin(seq), std::begin(seq) + n };
-        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;
 }
+bool is_possible_kolakoski(const Sequence& s) {
-template<typename T>
+  Sequence r;
-bool possibleKolakoski(const std::vector<T>& c) {
-    auto len = c.size();
+  for (size_t i = 0; i < s.size();) {
-    std::vector<T> rle;
+    int count = 1;
+    for (size_t j = i + 1; j < s.size(); ++j) {
-    auto prev = c[0];
-    size_t count = 1;
+      if (s[j] != s[i]) break;
+      ++count;
-    for (size_t i = 1; i < len; ++i) {
-        if (c[i] == prev) {
-            count++;
-        } else {
-            rle.push_back(count);
-            count = 1;
-            prev = c[i];
-        }
     }
+    r.push_back(count);
-    // no point adding final 'count' to rle as we're not going to compare it anyway
+    i += count;
-    for (size_t i = 0; i < rle.size(); i++) {
+  }
-        if (rle[i] != c[i]) {
-            return false;
+  for (size_t i = 0; i < r.size(); ++i) if (r[i] != s[i]) return false;
+  return true;
-        }
-    }
-    return true;
 }
 int main() {
+  std::vector<Sequence> seqs = {
-    using namespace std;
+    { 1, 2 },
+    { 2, 1 },
-    vector<vector<int>> ias = { {1, 2}, {2, 1}, {1, 3, 1, 2}, {1, 3, 2, 1} };
-    vector<int> lens = { 20,20,30,30 };
+    { 1, 3, 1, 2 },
+    { 1, 3, 2, 1 }
+  };
-    for (size_t i = 0; i < ias.size(); i++) {
+  for (const auto& s : seqs) {
-        auto len = lens[i];
-        auto ia = ias[i];
+    auto kol = gen_kolakoski(s, 20);
+    std::cout << "Starting with: " << s << ": " << std::endl << "Kolakoski sequence: "
-        auto kol = kolakoski(ia, len);
-        cout << "First " << len << " members of the sequence generated by " << ia << ":" << endl;
+      << kol << std::endl << "Possibly kolakoski? " << is_possible_kolakoski(kol) << std::endl;
+  }
-        cout << kol << endl;
+  return 0;
-        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]:
+<pre>Starting with: [ 1, 2, ]:
-[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
+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
-Possible Kolakoski sequence? Yes
+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, ]
-First 20 members of the sequence generated by [2, 1]:
+Possibly kolakoski? 1
-[2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2]
+Starting with: [ 1, 3, 1, 2, ]:
-Possible Kolakoski sequence? Yes
+Kolakoski sequence: [ 1, 3, 3, 3, 1, 1, 1, 2, 2, 2, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, ]
+Possibly kolakoski? 1
-First 30 members of the sequence generated by [1, 3, 1, 2]:
+Starting with: [ 1, 3, 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]
-Possible Kolakoski sequence? Yes
+Kolakoski sequence: [ 1, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1, 3, 2, ]
+Possibly kolakoski? 0</pre>
-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}}==