How to resolve the algorithm Kolakoski sequence step by step in the D programming language

Published on 12 May 2024 09:40 PM
#D

How to resolve the algorithm Kolakoski sequence step by step in the D programming language

Table of Contents

Problem Statement

The Kolakoski sequence is an infinite sequence of natural numbers, (excluding zero); with the property that: This is not a Kolakoski sequence: 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: The above gives the RLE of: The original sequence is different from its RLE in this case. It would be the same for a true 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 will arrange that the k'th item of s states how many times the last item of sshould appear at the end of s. We started s with 1 and therefore s[k] states that it should appear only the 1 time. ... 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. (There are rules on generating Kolakoski sequences from this method that are broken by the last example)

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Kolakoski sequence step by step in the D programming language

Source code in the d programming language

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;
    }
}

You may also check:How to resolve the algorithm Execute Computer/Zero step by step in the XPL0 programming language
You may also check:How to resolve the algorithm N'th step by step in the TypeScript programming language
You may also check:How to resolve the algorithm Matrix transposition step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Long year step by step in the Go programming language
You may also check:How to resolve the algorithm Higher-order functions step by step in the TI-89 BASIC programming language