User:Blashyrkh/Kolakoski-brainfuck

Kolakoski sequence generation implemented in Brainfuck with logarithmic memory consumption

Can't prove (yet) but it seems to me that time complexity of this solution is somewhere between o(n) and o(n log n). Probably, it's o(n log log n).

; == memory layout ==
; | 0 | 0 | 48 | s | c | 0 | s | c | 0 | etc
; s (symbols) are always 1 or 2 and therefore can be used as nonzero anchors
; c (counters) are nonzero normally but can be decremented to zero
; delimiting zeroes can be used as a temporary store

; initialize first three cells (0 0 and 48) and print first '1'
>+++++++[->+++++++<]>.-

; initialize two pairs of c and s
>++>++>>++>++[<<<]>

; now we point to 48
; let's start infinite cycle
[
  ; print current symbol (destructive for first two cells and first s)
  >[-<+<+>>]<.

  ; and restore everything back
  <[->->+<<]

  ; now we point at the lefmost cell which contains zero again

  ; now it is time to decrement counter(s)
  ; if some counter is decremented to zero then corresponding symbol should be inverted
  ; and next counter decremented and so on
  ; if some counter is decremented but still nonzero then we stop decrementing

  >>>-[>]
  ; if the counter is decremented to zero then we point at it
  ;                                  otherwise we point at the next delimiter
  +>>>[
    <<+++<-

    ; we are here only if the counter is decremented to zero
    ; we point to our counter which is zero now
    ; we already changed our delimiter (the one immediately after the counter) from zero to three
    ; it is done to invert the current symbol
    <[->>-<<]>>[-<<+>>]

    ; now we are at the next delimiter and the symbol is inverted
    ; repeat the loop with the next pair
    >>-[>]+>>>
  ]

  ; now we point to some delimiter
  ; and we know that previous delimiter is corrupted
  ; also we know how far decrementing reaches nowadays and probably it is time to expand our stack

  ; | c | 0 | s | c | 0
  ;       ^
  ; | c | 0 | 0 | 0 | 0
  ;       ^
  ; in the second case we have to expand the stack with two twos

  >++>[<--<]
  ; | c | 0 | s | c | 0 |
  ;       ^
  ; | c | 0 | 2 | 0 | 0 |
  ;               ^
  ++>[<-->>>]
  ; | c | 0 | s | c | 0 |
  ;                   ^
  ; | c | 0 | 2 | 2 | 0 |
  ;                   ^

  ; the magic is over
  ; two things left to do
  ; fix prevprev delimiter
  ; and replace each zero counter with the value of the following symbol
  <<<<<<-<<<<<
  [
    ; destructive copy value of next symbol to counter and to delimiter
    >>>[-<+<+>>]
    ; now restore both symbol and delimiter
    <[->+<]
    ; back to symbol
    <<

    ; go to previous symbol
    <<<
  ]

  >>
]

And it's still can be shortened a little bit (7 bytes actually): there's no need to initialize 2 pairs at the beginning, one pair should be enough. The stack would be expanded on the first pass anyway.