Create a BijectiveBrain

Question

Create a bijective function between the syntactically valid BF programs and the natural numbers

This means that you will assign each BF program a nonnegative integer (0,1,2,...) in such a way that each number gets a BF program without syntax errors (and without whitespace or comments).

Note that something like Binaryf***, for two reasons. Both +> and > map to 2, and no valid program maps to 6 (since [ is not a valid BF program).

You may either create two programs, one to map BF programs to numbers, one to map numbers to valid BF programs (which will be inverses) (in which case your score is the sum of their lengths), or you can create one program which does both tasks (in which case your score is just length of that one program).

Note: The program(s) must run in polynomial time (in terms of the length of the input). (This rule is to prevent boring brute force approaches.)

This is code-golf, so the shortest program(s) wins!

Answer 1

Haskell, 215+242=457

I haven't significantly golfed this. Its more of a example.

From BF to number

c '>'=1
c '<'=2
c '+'=3
c '-'=4
c '.'=5
c ','=6

i 0 ""=0
i 0 ('[':t)=7+7*(i 1 t)
i 0 (h:t)=(c h)+7*(i 0 t)

i b (']':t)=0+8*(i (b-1) t)
i b ('[':t)=7+8*(i (b+1) t)
i b (h:t)=(c h)+8*(i b t)

main=interact(show.i 0)

From number to BF

c 1='>'
c 2='<'
c 3='+'
c 4='-'
c 5='.'
c 6=','

i 0 0=""
i 0 n = case divMod n 7 of
    (m,0)->'[':i 1 (m-1)
    (m,x)->(c x):i 0 m
i b n = case divMod n 8 of
    (m,0)->']':i (b-1) m
    (m,7)->'[':i (b+1) m
    (m,x)->(c x):i b m

main=interact(i 0.read)

It works through a combination of Bijective numeration and Mixed radix.

The encoder has two modes: no unmatched brackets mode and unmatched brackets mode.

If there are no unmatched brackets, 0 maps to the empty program, and each of the characters ><+-.,[ is mapped to a number from 1 to 7. ] is not included since a BF program can not have ] until it an unmatched bracket. This digit becomes the least significant digit, and is in base 7.

Once there are unmatched brackets, the digits are in base 8, with ] assigned to 0. In particular, there is no number assigned to the ending the program (since you can not end the program while there are unmatched brackets). Once all brackets are matched, it returns to no unmatched brackets mode. To output 0 exactly while in this mode, you must match all brackets, and then end.

Example: .-,.><++.,[>] -> 4228460766 -> .-,.><++.,[>]