60 lines
1.7 KiB
Nim
60 lines
1.7 KiB
Nim
template nextInCycle(a: openArray[int]; index: Natural): int =
|
|
a[index mod a.len]
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
func kolakoski(a: openArray[int]; length: Positive): seq[int] =
|
|
|
|
result.setLen(length)
|
|
var i, k = 0
|
|
|
|
while true:
|
|
result[i] = a.nextInCycle(k)
|
|
if result[k] > 1:
|
|
for j in 1..<result[k]:
|
|
inc i
|
|
if i == length: return
|
|
result[i] = result[i - 1]
|
|
inc i
|
|
if i == length: return
|
|
inc k
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
func possibleKolakoski(a: openArray[int]): bool =
|
|
|
|
var
|
|
rle: seq[int]
|
|
prev = a[0]
|
|
count = 1
|
|
|
|
for i in 1..a.high:
|
|
if a[i] == prev:
|
|
inc count
|
|
else:
|
|
rle.add count
|
|
count = 1
|
|
prev = a[i]
|
|
|
|
# No point adding final 'count' to rle as we're not going to compare it anyway.
|
|
for i, val in rle:
|
|
if val != a[i]: return false
|
|
|
|
result = true
|
|
|
|
#———————————————————————————————————————————————————————————————————————————————————————————————————
|
|
|
|
when isMainModule:
|
|
|
|
import sequtils, strformat
|
|
|
|
const
|
|
Ias = [@[1, 2], @[2, 1], @[1, 3, 1, 2], @[1, 3, 2, 1]]
|
|
Lengths = [20, 20, 30, 30]
|
|
|
|
for (length, ia) in zip(Lengths, Ias):
|
|
let kol = ia.kolakoski(length)
|
|
echo &"First {length} members of the sequence generated by {($ia)[1..^1]}:"
|
|
echo ($kol)[1..^1]
|
|
let s = if kol.possibleKolakoski(): "Yes" else: "No"
|
|
echo "Possible Kolakoski sequence? " & s & '\n'
|