At last, here's the solution to the 9 digit problem of Encse in Brainfuck.

The raw program

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

Easy, huh?

Brainfuck Workbench

I don't think I could have implemented all this without developing a liltle IDE for Brainfuck called Brainfuck Workbench (BfWB) using Intentional's glorious Domain Workbench.

To make it more manageable, I added a few features to the core Bf language:

• Blocks, which can group statements and can be repeated.
• Blocks as well as primitive statements can be repeated for a given number.
• Macros can be defined which are then expanded at compile time by the generator. Macros can have named parameters which can be passed further to other macros or used as a repeat clause in the body of the macro.
• Symbol (aka named constants) can be defined and then used as repeat clauses and macro parameters throughout the whole program.
• You can also add comments and regions at most of the places in the code.

Just to get a feel for it, here's the main program as defined in the workbench:

The two main bit here are the macro extend and fDiv. Extend generates the next number in the recursion and puts it onto a stack-like structure. fDiv checks if the current number is divisible by the current level number. If the divisibility is satisfied and we are not at the last level, it extends further. Otherwise if we are at the last level then we print the number and backtrack. If the number is not divisible or even extend was not successful (because we have run out of free candidate digits) then we backtrack.

Division is tricky as you have probably guessed, but I'll reveal no clues here... It's definitely NOT using unary arithmetics. :P The whole thing finishes in 2 seconds in Brainfuck Developer.

Alternatively you can use any of the many online Brainfuck interpreters. I tried the one at ircbot.hu.

So what is it good for?

Absolutely nothing. :) Brainfuck is a toy language and as such it has no direct real world value. 

However, I have found that writing a Brainfuck program invoked my very hardcore programmer skills and have put them at great stress. When you write a Brainfuck program you have to know exactly all the invariants, preconditions and postconditions at every single statement. Sloppy coding is just not acceptable with Brainfuck. The moment you lose even one bit of your loop invariant and then bang!, your program just does not work and you are up to a half hour debugging session until you find out what happened.

Also as far as BfWB is concerned, I was using it to test a few ideas to improve IDW. So that time is not lost either (at least not all of it :) ).

Credits

Thanks to Encsé for the great exercise.

Thanks to Tim Rohlfs for Brainfuck Developer a Brainfuck IDE that has a really nice debugger and without which I would have been lost.

Thanks to Urban Müller for inventing Brainfuck in the first place.