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

Published on 12 May 2024 09:40 PM
#Lua

How to resolve the algorithm Kolakoski sequence step by step in the Lua 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 Lua programming language

Source code in the lua programming language

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

You may also check:How to resolve the algorithm Quine step by step in the Applesoft BASIC programming language
You may also check:How to resolve the algorithm Textonyms step by step in the Haskell programming language
You may also check:How to resolve the algorithm Stack traces step by step in the Scala programming language
You may also check:How to resolve the algorithm Knight's tour step by step in the BASIC programming language
You may also check:How to resolve the algorithm Determine if two triangles overlap step by step in the ooRexx programming language