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).

Looks like it's o(n). Average length of decrement series seems to be constant (though I don't have the exact theoretical value, it should be close to 6 or to 8.24). Long simulations show that average number of brainfuck instructions per one printed character is 226 (with all optimizations turned off).

; == 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
  <[->->+<<]

  ; we point to the second zero cell (cell number 1)

  ; 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
    <<<
  ]

  ; reached cell number zero (the leftmost zero)
  ; move position back to 48 to ensure that the outer loop loops forever
  >>
]