105 lines
2.1 KiB
Lua
105 lines
2.1 KiB
Lua
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
|