Sort: Counting sort

Context

Counting sort is a sort algorithm dedicated to lists having values in a small set. Then, one can create an array of same size and store values (or count) while reading.
Using BrainFuck, all our values are stored between 0 and 255. Therefore, it might be an interesting sort algorithm. Let's implement it.
Initial state

• Memory: 0 0 [array] 0 0 0 0 0 ... where array is a 2 cells block array of nullable integers
• Pointer: just after array
• Input: any

Process

• Generate counter array
• That's a 2 cells block array of nullable integers, of size 256
• Generate the first cell
• Then have 255 in a counter and generate all cells after
• For each integer N from the list
• Access item N in array and increment counter
• Optionally, we can rebuild back the array when sort is completed
• Define current value (initially: 0)
• For each counter C in counter array
• Add current value C times
• Increment current value

Code - try it

generate counter array: 2 cells array with 256 items
->>>>>+<<<<<[->>>>>[>>]+[<<]<<<]

read integers one by one and store into array
go to first integer and loop
<<[<<]>>
[
  remove cell indicator
  -
  move value to end
  >[->[>>]>+<<<[<<]>]
  go to value and move backward
  >[>>]>[-<+>]
  access array cell given by index
  <[->>>[>>]+>>->[-<<+>>]<<<[<<]<]
  increment count for given value
  >>>[>>]>>>+
  move array back to position
  <<<<<[[->>+<<]>[->>+<<]<<<]
  go to next integer
  <<<[<<]>>
]

rebuild array of values
>>>>>
[
  move cell
  -<<+>>>[-<<+>>]<<
  add value N that many times
  [
    -
    go to current value
    <[<<]<
    copy / move to end of array
    [->+>+<<]>[-<<<[<<]>+>[>>]>]
    set cell flag
    <<<[<<]+[>>]
    restore current value copy
    >>[-<<+>>]
    go back to value counter
    >[>>]<
  ]
  increment current value
  <[<<]<+
  >>>[>>]>>
  go to next cell and loop
]

clear counter array
<<<<[->[-]<<<]

Final state

• Memory: 0 0 [sorted array] 0 0 0...
• Cursor: 2 cells after array
• Input: unchanged
• Output: unchanged

Notes

1. Due to our array rebuild, the sort is descending, but this can be easily changed to ascending sort
2. Despite a shorter algorithm, execution is really longer than Quicksort

Sort: Bubble sort

Context

There are multiple ways to sort an array in computer theory. One of them is called Bubble sort.
This algorithm is clearly not the best one, though it's quite easy to implement:

• Consider 2 adjacent cells
• Compare values
• If second is smaller, then swap the 2 values
• Move to next pair of 2 cells (the one that includes the second element of my current pair)
• When reaching end of array, redo the whole loop as long as at least one swap has been made (sort is not over)

The name comes from the behaviour of biggest / smaller elements (according to the sort direction) : they are pushed to the top of the list like bubbles in liquids.

Let's write our own bubble sort implementation

Initial state

• Memory: 0 0 [array] 0 0 0 0 0 0 ... where array is an array of nullable integers (2 cells per item, one set to 1 and second set to the value)
• Cursor: just after array
• Input: any

Process

• Set a loop indicator to 1 and start a loop
• Reset loop indicator
• Go to last two cells
• Move and copy the second cell to the right (leave enough space for comparison)
• Copy first cell value
• Compare first and second value copies
• If second is smaller than first
• Swap the 2 values
• RESET the loop indicator and set to 1. Reset is mandatory, otherwise (simply adding 1) will fail if there are 256 changes (loop indicator will then be 0). Here, instead, let's just have the indicator reset and set to 1
• Move to the next pair if any
• Move array back to its original location
• Go back to loop indicator and loop if needed

Code - try it

set loop indicator and loop
>>>>>>>+[
  reset indicator and go to last 2 cells
  -<<<<<<<<<<<
  while there are 2 cells to compare
  [
    copy / move second cell
    >>->[->+>>>>>+<<<<<<]>>>>>+<<<<[-<+>]
    copy first cell
    <<<[->+>>+<<<]>[-<+>]
    compare 2 values
    >>>+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<<
    [-
      second is smaller : swap
      temporarily move first cell
      <<[->+<]
      move first cell
      >>>>>>>>[-<<<<<<<<+>>>>>>>>]
      reset and set loop indicator
      >[>>]>[-]+<<<[<<]<<<<
      move second value
      [->>>>>>>+<<<<<<<]
      go back to position before if
      >
    ]
    move to last 2 cells and loop
    <<<<<
  ]
  move array back to initial location
  >>>>>>>>>>[[-<<<<<<+>>>>>>]>[-<<<<<<+>>>>>>]>]
  go to loop indicator and loop
  >
]

Final state

• Memory: 0 0 [array] 0 0 0 0 0 0
• Cursor: 6 cells after the array
• Input: unchanged
• Output: unchanged

Display all prime numbers

Context

A prime number is a number that allows only 2 distinct divisors: 1 and itself.
First prime numbers are 2, 3, 5, 7, 11 ...
Computing all prime numbers up to a limit can be implemented using a sieve, that works like this

• Generate an array of all integers from 2 up to the limit
• Go to the first non-null item in the array
• This number N is prime
• Then, reset array items every N cells starting from this one

Example: 2 is prime, and all multiple of 2 are removed, then 3 is a prime and all multiples of 3 are removed, including 6 that will be reset twice (once for 2, and once for 3), then 4 is null (reset by 2), so move to 5, ...

Initial state

• Memory: empty
• Cursor: first cell
• Input: any

Process

• First, define a 'comma' on first cell (code: 44), because we'll display comma-separated numbers, so it avoids building the comma everytime.
• Note: this is equivalent to a constant value in other programming languages...
• Then, generate all numbers from limit to 2, in decreasing order, in a 2-cells array, but this time it'll be [{value, 1}]  instead of [{1, value}] (code is a bit shorter)
• Generate the limit (using '-', we'll have 255, the biggest possible value)
• Set next cell to 1
• While current value is not null
• Copy 2 cells ahead
• Set next cell to 1
• Decrease copied value by 1, and stay on this value
• Result will be an array from 255 to 0, let's just remove the extra cells at the end.
• Finally, go to the first cell
• If value is not null
• Print the number
• Print comma
• Copy / move it twice: one for backup, one for counter
• Iterate on all array cells
• Move 2-cells block to the right
• Decrease counter. If null
• Reset copied cell
• Reset counter to initial value (copy from backup)
• Move whole array at its original position
• Go to next cell

Code - try it

generate comma
>++++[-<+++++++++++>]
generate all numbers from max to 2
>-[[->+>+<<]>[-<+>]+>-]<-<-<

[
  go to current number
  -<
  [
    number is not null: prime
    copy twice and print
    [->>+>>+<<<<]
    >>>>[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]
    print comma
    <<<<[<<]<.>>>[>>]
    copy counter
    >[->+>>+<<<]>[-<+>]<

    for each cell
    <<<[
      move
      -<[->>+<<]>>>+
      go to counter and decrease then check if null
      [>>]+<-[>-]>[-
        reset last copied cell
        <<[<<]>[-]>[>>]
        reset counter
        >>[-<+<<+>>>]<[->+<]
      ]
      process next cell
      <<<[<<]<<
    ]
    move back all cells
    >>>>[<[-<<+>>]<+>>->>]
    clear counters
    <[-]>>>[-]<<<<<
  ]
  process next number
  <
]

Final state

• Memory: 44 0 0 0 (44 is code for comma)
• Cursor: second cell
• Input: unchanged
• Output: all primes below 255, comma separated, with extra comma - note that extra comma can be removed by adding a Backspace character (code = 10). Simply add ++++++++++. at the end of the code.

Null values in arrays

Context

As mentioned in this previous post, array implementation induces a limitation: elements cannot be null. Let's now see how to deal with zeros.
To access an element in an array, we need to go through all elements, so use a loop. And loops stop when value reached is null. Therefore, our current array structure doesn't fit.

However, it's still possible to have arrays with 2 memory cells per element: first that contains a non-zero value (any value, but let's say 1), and second that contains the actual element value.
Then, to access elements in the array, we need to iterate on blocks of 2 cells.

Code sample

>>+ first separator

>>, read char

[

  >++++[-<----------->]+< comma check

  [---- convert to digit value

    >++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>] multiply current by ten and add new digit

  ]>[ comma case

    <+>->> add cell with 1 and start next number

  ]<,]

<<[<<]>> go back to array last element (first cell) then back to the array beginning

This block of code read comma-separated decimal numbers, including 0, and store them in memory cells separated by cells containing 1.

The last line shows how to move back to the array first element.

Access array item by index

Context

Generally speaking, in computer theory, one of the key points when working with arrays is that you can randomly access any element given its index with a constant time operation - noted O(1). Conversely, chained lists force you to iterate from first element to next ones until you reach the end.
Using BrainFuck, the operation to randomly access an element in an array given its index is actually more close to the list mechanism. Here is the global idea:

• Use our target index as a counter
• Move first element out of the array and decrease counter
• When counter is null, pick first element of the array
• Move everything back at the right place
• Move the current reverted stack to the left, to use constant memory
• Loop until all items are moved

We'll consider a zero-based index array in this example.

Initial state

• Memory: 0, 0, array, 0, index
• Cursor: on index
• Input: any

Process

• While index is not null
• Decrease index
• Go to array's first element
• Move it to the left
• Go back to index
• Loop invariant: (considering the array as the part delimited by 2 zeros) the value with position index in the array - as index is decreased as well as array size, from beginning
• When index equals 0, then array starts with our target element
• When index is null
• Move to array's first item
• Copy outside array
• Move to left first
• Then move outside array and twice
• Move one of the copies at the beginning of the array (actually, one cell left the beginning of the array)
• Move all array items back to their original position

Code 

[
  while index is not null

  -
  decrease index

  <<[<]>[-<+>]
  move last element outside array

  >[>]>
  go back to index
]
<<[<]>
go the array's first element

[-<+>]
move to the left

<[->>[>]>+>+<<<[<]<]
copy outside array twice

>>[>]>>
go to second copy

[-<<<[<]<+>>[>]>>]
move second copy back to where it comes

<<<[<]<[[->+<]<]>>[>]>
move all items back to their original position

Code (minified)

[-<<[<]>[-<+>]>[>]>]<<[<]>[-<+>]<[->>[>]>+>+<<<[<]<]>>[>]>>[-<<<[<]<+>>[>]>>]<<<[<]<[[->+<]<]>>[>]>

Final state

• Memory: 0,array, 0, array[index]
• Cursor: on result (array[index])
• Input: unchanged
• Output: unchanged

Example

Live 'Letter-by-index' example, that generates an alphabet array (from A to Z), reads a number N (should be between 1 and 26) in the input, pick the corresponding array item, and print the Nth letter of the alphabet.
Obviously, it would have been faster to simply read the number and add 64 to it, but pointless for this example :)

Revert array, in place

Context

Given an array, with our standard formalism, let's see how we can reverse it, i.e [A,B,C] to become [C,B,A]. But to make it more complex, let's do it in place, without needing extra data storage.
Well, more exactly, with a constant amount of data storage, meaning that we won't need more space for bigger arrays

• Start at the end of the array (let's say it's a stack)
• Copy last array item at the end of the reverted stack
• Move the current reverted stack to the left, to use constant memory
• Loop until all items are moved

Initial state

• Memory: 0, A, B, C, D, ..., 0...
• Cursor: last array item
• Input: any

Process

• Start on stack's last element
• While there is at least one element
• While element is not null
• Decrease it by 1
• Move right twice (reverted stack's start point)
• Move right until cell is empty (first free position)
• Here is the trick: we should not add the new item right here! (otherwise we won't be able to identify the end of the array)
• Instead, move right once again, and increase cell by 1.
• Move left twice, then move left until cell is empty, and finally move left once.
• Back to item we want to move
• Loop invariant: sum of first stack's last element and cell just after second stack
• When first stack's last element is finally null, cell just after second stack contains moved last element from first stack
• Go to second stack's end
• Move newly added item to the left (append at the end of the array)
• Go back to second array's first element
• We now have 2 zeros between our 2 stacks: first's final delimiter, and one empty cell (generated by the move of last element) : we need to move the whole second stack one cell to the left to stay in-place.
• While second array's end is not reached
• Move current element to the left
• Move cursor to right
• Go back to first stack's last element
• Loop invariant: memory contains 0, then some items from original stack, then zero and finally all items missing from original stack in reversed order
• When first stack is empty: 2 zeros then all stack in reversed order
• Finally, move the whole reverted stack to the left once, to avoid the extra 0 

Code 

[
  consider last integer
  [
    while it is not null
    -
    move 1 from this number 
    >>[>]>+
    to the end of the reverted stack
    <<[<]<
    and go back to the moved value
  ]
  >>[>]>
  go to the new item; not exactly at the end but one cell after
  it wouldn't have been possible to reach the end of array otherwise
  [-<+>]
  move this value to the end of the array
  <[<]>
  go back to the reverted stack's first element
  [[-<+>]>]
  move each element to the left to have in place algorithm
  <<[<]<
  go to original stack's last element
]
revert completed
>>[[-<+>]>]<<
move all items to the left because both original and reverted 0 array delimiters are here

Code (minified)

[[->>[>]>+<<[<]<]>>[>]>[-<+>]<[<]>[[-<+>]>]<<[<]<]>>[[-<+>]>]<<

Final state

• Memory: 0,..., D, C, B, A, 0
• Cursor: on final item (A)
• Input: unchanged
• Output: unchanged

Example

Live 'Stack-revert' example, that reads input, place all chars in an array, revert the array, then print the reverted stack (e.g. input abcdefgh prints hgfedcba)

Read comma-separated numbers

Context

Let's have an input like '12,34,56,78,9,100'. The goal is to have an array of numbers [12], [34], ... in memory, reading comma-separated decimal numbers. To achieve it, we'll have to

• Read a char
• If it's a comma (ASCII code 44), then start a new number
• Otherwise it's a digit, add it to ten times the current number

Note: this post is strongly related to array definition and read decimal number ones

Initial state

• Memory: 0, 0, 0, 0...
• Cursor: first cell
• Input: comma-separated decimal numbers (A,B,C,...)

Process

• Leave one cell to delimit array, plus one cell for current first integer read
• While a character is read
• Remove 44 (',' ASCII code)
• Set else bit
• If result is not null
• It's a digit. Remove 4 to get the decimal digit value
• Update current integer
• Otherwise
• Start a new integer 

Code 

>>
array delimiter and first integer (currently 0)
,[
  >++++[-<----------->]+<
  remove 44 (comma ASCII code) and set bit else
  [>-<
    if read value is not 44 => it is a digit
    ----
    remove 4 again (to remove 48 which is 0's ASCII code)
    >+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]
    multiply current integer by ten and add new digit
  ]
  >[-
    else
    >
    move to next integer
  ]<
,]

Code (minified)

>>,[>++++[-<----------->]+<[>-<---->+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]]>[->]<,]

Final state

• Memory: 0,A,B,C,...,0
• Cursor: on final 0 (end of array)
• Input: empty
• Output: unchanged

Example

Live 'Comma-separated decimal to ASCII' converter: type comma-separated ASCII code to display the corresponding string (e.g. input 50,48,49,55 produces 2017)

Array length

Context

Note: in this post, arrays will be implemented according to our previous definition.
Array length can be computed by counting its number of elements. To do so, we need to split the array between counted elements and not counted ones. And counting an element means move it from one array to another.
To have clean code, we can additionally move back all our elements at the initial position.

Initial state

• Memory: 0, Array, 0, 0, 0
• Cursor: first cell
• Input: any

Process

• Move to last item (can be done by >[>]<, move to first item on second cell, move to next until it's null, move back to last non-null cell)
• While last item is not null
• Move last item to next cell
• Increment count (2 cells after the end of array)
• Go back to last item of first array
• Optional : move all array items back to their original position and same for result

Code 

>[>]< go to last item

[ 

  [->+<] move to right 

  >[>]>+ go to counter and increment 

  <<[<]< go to new last item

] 

>>[[-<+>]>] move back all items 

>[-<+>]< move result back

Code (minified)

>[>]<[[->+<]>[>]>+<<[<]<]>>[[-<+>]>]>[-<+>]

Final state

• Memory: 0, Array, 0, Array length
• Cursor: on array length
• Input: any
• Output: unchanged

Introduction to arrays

Context

No code in this post. The goal is only to define how we can implement arrays.
In order to ease array manipulations, it's recommended to define some hypothesis.

• An array contains values
• It is delimited by zero values at the beginning and at the end
• Therefore, an array cannot contain '0' value.
• But an array can be empty

• Memory: 0, Array, 0

Then, all codes manipulating arrays in the coming posts will use this data structure, until a future one where a more complex structure will also allows null values.