Kolakoski sequence

editable example

Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.

ghul

use IO.Std.write_line

use Collections.LIST

use Collections.List

use Ghul.Pipes

cycler(values: int[]) -> () -> int is

let at mut = 0

return () => (

let value = values[at]

at = (at + 1) % values.count

value

)

si

kolakoski(values: int[], length: int) -> List[int] is

let next = cycler(values)

let sequence = LIST[int]()

let at_run mut = 0

while sequence.count < length do

let value = next()

sequence.add(value)

for _ in 1..sequence[at_run] do

sequence.add(value)

od

at_run = at_run + 1

od

return sequence[0..length]

si

run_lengths(sequence: List[int]) -> List[int] is

let runs = LIST[int]()

let run mut = 0

for i in 0..sequence.count do

run = run + 1

let last = i + 1 == sequence.count

if last \/ sequence[i + 1] != sequence[i] then

runs.add(run)

run = 0

fi

od

return runs

si

self_describing(sequence: List[int]) -> bool => (

let runs = run_lengths(sequence)

(0..runs.count - 1) |> all(i => runs[i] == sequence[i])

)

report(values: int[], length: int) is

let sequence = kolakoski(values, length)

write_line("from ({values |> join(", ")}), first {length}:")

write_line(" {sequence |> join(", ")}")

write_line(" self-describing: {self_describing(sequence)}")

si

report([1, 2], 20)

report([2, 1], 20)

report([1, 3, 1, 2], 30)

report([1, 3, 2, 1], 30)

from (1, 2), first 20:
  1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1
  self-describing: True
from (2, 1), first 20:
  2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2
  self-describing: True
from (1, 3, 1, 2), first 30:
  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
  self-describing: True
from (1, 3, 2, 1), first 30:
  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
  self-describing: False