BrainFuck part 5 - Math sequences

Pascal's triangle

Pascal's triangle is a triangular array of binomial coefficients: cell k of row n indicates how many combinations exist of n things taken k at a time. It looks like this

• 1
• 1 1
• 1 2 1
• 1 3 3 1
• 1 4 6 4 1
• ...

One can prove that a given cell is the sum of 2 cells from previous row: the one just above and the one on top left.

Given that, let's see how we can generate the Nth row of Pascal's triangle

Let's start

• Memory: empty
• Cursor: first cell
• Input: a decimal number N (greater than 0)

Process

• Read a decimal number
• Init line 0 : just 1
• While counter is not null
  • Decrease counter
  • Generate next line
    • Go to row last cell (e.g. mem : A B C D 0 0 0
    • Move it to the next 2 cells (e.g. mem : A B C 0 D D)
    • Go to previous cell and loop
      • mem : A B 0 C C+D D
      • then A 0 B B+C C+D D
      • and finally 0 A A+B B+C C+D D
    • Move all values back on the left
• Print last line, comma separated. Line is symetric : can be print from right to left as well
• Print '1' and ignore first value (it's always 1)
• While there is an item
  • Print comma
  • Move / Print item
  • Go left
• Loop

Code

>,[>++++++[-<-------->]>+++++++++[-    read an integer 
<<<[->+>+<<]>>[-<<+>>]>]<<[-<+>],]      ** part 2 **
>+                                     Initialize first row
<<[                                    while counter is not null
  -                                    decrease counter
  >>[>]<                               go to last cell
  [[->+>+<<]<]                         while there is a cell: move to the next 2 ones on the left and repeat
  >>[[-<+>]>]                          Move whole array to the left
  <<[<]<                               back to counter
]                                      loop
>+++++++[-<+++++++>]<.-----            print 49 (='1') and change into comma (44)
>>[>]<-<                               go to last cell (1) then reset; then go to previous cell
[                                      for each cell in the row
  [<]<.>>[>]<                          print comma (first memory cell) then go back to the current cell
  [->+<]>                              move to the right (at least one 0 needed to print a decimal value)
  [>>>>++++++++++<<<<[->+>>+>-[<-]<[-  Print decimal value
  >>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-   ** part 2 **
  ]>[-<<<<+>>>>]<<<<]<[>++++++[<+++++   ** part 3 **
  +++>-]<-.[-]<]                        ** part 4 **
<]

Minified version

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

Final state

• Memory: 44, 0, 0, 0
• Cursor: on second cell
• Input: read (empty)
• Output: Nth row from Pascal's triangle (modulo 256)

Note: because of the nature of the algorithm, if a cell equals 0 on a row it will break the loop. And modulo 256, a cell can actually be null.

However, the first cell that will be a multiple of 256 in standard Pascal's triangle appears on row 256, and the counter itself, from user input, cannot be more than 255.

In other words: this algorithm is valid as long as we rely on a counter. Having an infinite loop to generate more than 255 rows will fail. We can of course introduce 2-cell-long arrays but it's not really important here.