User:Blashyrkh/A+B-brainfuck
Jump to navigation
Jump to search
My implementation of A+B Problem in Brainfuck. Stripped version is 316 bytes long. It uses decimal representation for calculations. Here's the full version with explanation (probably TOO verbose):
; Blashyrkh's elementary school of brainfuck programming
; Take your seats kids
; Let's solve more general problem: A plus B plus C plus etc until EOF
; A plus B would work as a special case
; Each input number (maybe except the last one) should be followed by LF
; Being good boys and girls we will accept both 'minus one' and 'no change' styles of EOF
; Any character other than digit or LF (ascii 10) would ruin everything
; Beware brainfuck interpreters that DO NOT replace CRLF with LF on Windows!
; == Memory layout ==
; |EOF| 0 | 0 | x | | x | | x | Input buffer
; | | | | | a | | a | | Accumulator
;
; == Work cycle ==
; read addendum to input buffer and reverse it in process
; if read ends with EOF then special flag is set which is analyzed after summation
; input of current addendum ends with LF or EOF
; EOF flag breaks the main loop
; add the addendum to the accumulator
; normalize accumulator digits (propagate carry bit)
; repeat
; handle special cases (leading zeroes and zero result)
; print result
; Main loop always starts at cell zero where EOF flag resides
; The flag is zero normally (and initially) and set to one if EOF is encountered during the input loop
-[
; Reset EOF flag back to its original value (zero)
+
; Set position to cell number 3
; That's where the first read symbol will be stored
>>>
; Remember that we promised to be good boys and girls (ok I did not you)
; We shall accept both 'minus one' and 'no change' EOF
; It means that we have to set a cell to minus one before performing input into it
-[
; Input!
,+
; Current input cell (let's name it 'x' for now) is:
; 0 in case of EOF
; 11 in case of LF
; 49~58 in case of digit
; Let's look at the diagram:
; | 0 | 0 | 0 | x | a | ? | (case A)
; ^
; | 0 | 0 | 0 | 0 | a | ? | (case B)
; ^
; Case A: subtract 11 from x
; Case B: set EOF flag and leave x=0
[-----------<<->]<+[<]>
; | 0 | 0 | 0 | x | a | ? | x=38~47 or 0
; ^
; | 0 | 0 | 1 | 0 | a | ? |
; ^
[-<<+>>]>
; | 0 | 0 | 0 | x | a | ? | x=38~47
; ^
; |EOF| 0 | 0 | 0 | a | ? | EOF or LF
; ^
; if a digit was entered then we need to shift the whole input two cells
; rightwards to prepare place for the next input digit
; otherwise change nothing
[
; | 0 | 0 | 0 | x | a | x | a | x | x=38~47
; ^
<++++++[->------<]>-
; | 0 | 0 | 0 | x | a | x | a | x | x=1~10
; ^
[>>]<<
; | 0 | 0 | 0 | x | a | x | a | x | a | 0 |
; ^
[[->>+<<]<<]
; | 0 | 0 | 0 | 0 | a | x | a | x | a | x |
; ^
>+>
; | 0 | 0 | 1 | 0 | a | x | a | x | a | x |
; ^
]
; | 0 | 0 | 1 | 0 | a | x | a | x | a | x | when we wait for next digit of current number
; ^
; |EOF| 0 | 0 | 0 | a | x | a | x | a | x | when EOF or LF was entered
; ^
<[->-<]>
; | 0 | 0 | 0 | _1| a | x | a | x | a | x |
; ^
; |EOF| 0 | 0 | 0 | a | x | a | x | a | x |
; ^
; If EOF or LF was entered then we break the loop
; Otherwise we put 'minus one' input the cell and repeat input
]
; |EOF| 0 | 0 | 0 | a | x | a | x | ?
; ^
; Addendum is stored to 'x' cells where x=1~10
; Accumulator is in 'a' cells where a=1~10
; But length of accumulator and of the last addendum may be different
; Let's add new addendum to accumulator and clear (reset to zero) all x cells
; Iterate over 'x' cells
>>[
; Point to corresponding 'a' cell
<
; | ? | 0 | a | x |
; ^
; | ? | 0 | 0 | x |
; ^
; Zero 'a' cell means that this accumulator cell was not initialized yet (implicit zero)
; If 'a' is zero than we can move 'x' there
; Otherwise we add 'x' and subtract 1 since 'x' are also 1~10
[>-[-<+>]]
; | ? | 0 | a'| 0 |
; ^
; | ? | 0 | 0 | x |
; ^
<[<]>>
; | ? | 0 | a'| 0 |
; ^
; | ? | 0 | 0 | x |
; ^
[-<+>]
; | ? | 0 | a'| 0 |
; ^
; | ? | 0 | x | 0 |
; ^
; Bingo!
; Move to next 'x' cell
>>
]
; Move to last guaranteed nonzero accumulator cell
<<<
; Rewind
[<<]>>
; Addendum is added to accumulator but its digits are not normalized
; They are 1~19 instead of 1~10
; We need to normalize them and propagate carry bit
; |EOF| 0 | 0 | 0 | a | 0 | a | 0 | a |
; ^
[
>++++++++++
; |EOF| 0 | 0 | 0 | a | 10| a | 0 | a |
; ^
[
<-<+>[<-]<
; |EOF| 0 | 0 | 0 | a'| ? | a | 0 | a |
; ^
; |EOF| 0 | 0 | 1 | 0 | ? | a | 0 | a |
; ^
[->++++++++++>>>-<<<<<]
; |EOF| 0 | 0 | 0 | a'| ? | a | 0 | a |
; ^
; |EOF| 0 | 0 | 0 | 10| ? | a | _1| a |
; ^
>>>-
]
; It worked ok for the first digit
; But we need to process the rest of accumulator
; We need space for it
; Each digit needs two zeroes to the left of it
; So we have to move already processed digits one cell left
; |EOF| 0 | 0 | 0 | a | 0 | a | c'| a |
; ^
<[-<+>]>>>+
; |EOF| 0 | 0 | a | 0 | 0 | a | c | a |
; ^
; Next thing to do: what is 'c'? It's carry flag which should be added to the next 'a'
; Why didn't we add it already? Because a=0 along with c=1 has special meaning: 'a' must be set to 2!
; It's because a=0 means "not yet initialized accumulator cell" and we have to perform this
; initialization (:=1) before adding carry bit
[
; |EOF| 0 | 0 | a | 0 | 0 | a | 1 | a | '*' should be incremented
; * ^
; |EOF| 0 | 0 | a | 0 | 0 | 0 | 1 | a | '*' should be set to 2
; * ^
-<[>]++
; |EOF| 0 | 0 | a | 0 | 0 | a | 2 | a |
; ^
; |EOF| 0 | 0 | a | 0 | 0 | 2 | 0 | a |
; ^
<[+>--<<]>>
; |EOF| 0 | 0 | a | 0 | 0 | a'| 0 | a |
; ^
; |EOF| 0 | 0 | a | 0 | 0 | 2 | 0 | a |
; ^
]
; Point to next accumulator cell and repeat the loop
<
]
; Now accumulator is OK but it's shifted one cell left
; |EOF| 0 | 0 | a | 0 | a | 0 | 0 | 0 |
; ^
<<<[[->+<]<<]
; |EOF| 0 | 0 | 0 | a | 0 | a | 0 | 0 |
; ^
; Continue if not EOF
<-
]
; Now we're almost ready to print our result
; Two special cases must be handled though
; (1) leading zeroes
; (2) no digits at all
>+>>>[>>]<<
[
; | 0 | 1 | 0 | 0 | a | 0 | a | 0 | 1 | leading zero looks like this
; ^
; | 0 | 1 | 0 | 0 | a | 0 | a | 0 | a |
; ^
-[+[<<]]
; | 0 | 1 | 0 | 0 | a | 0 | a | 0 | 0 |
; ^
; | 0 | 1 | 0 | 0 | a | 0 | a | 0 | a |
; ^
<[->>]<
; | 0 | 1 | 0 | 0 | a | 0 | a | 0 | 0 |
; ^
; | 0 | 0 | 0 | 0 | a | 0 | a | 0 | a |
; ^
]
; Probably no digits left at all (result was zero but all zeroes were removed)
; | 0 | 1 | 0 | 0 | 0 |
; ^
; | 0 | 0 | 0 | 0 | a |
; ^
<[->>>+<<<]
; Now print digits from right to left
; First let's rewind and add 47 to each digit (thus convert to ascii range)
>>>[->++++++[-<++++++++>]>]<<
; And print them all backwards
[.<<]
; print LF
++++++++++.
; That's all folks!