I've done an implementation of the well-known "Towers of Hanoi" problem in Brainf*ck. The program features semi-graphical terminal output (see screenshot) and does solve the problem by itself (i.e. it doesn't simply output an hardcoded solution).

The program has been written using my Brainf*ck Compiler Suite. The bfc source can be found here and the compiled Brainf*ck program here.

Brainf*ck doesn't have real function calls and so it also does not allow recursion. But "Towers of Hanoi" is a recursive problem, so I needed to implement the algorithm with explicit stack/context management:

macro hanoi(from, other, to, num) { var state, depth, tmp; state, depth = 1; while (depth) { while _neq(state, 4) { if (num) { var ctx_do_push = 0; var state1, state3 = 0; if _eq(state, 1) { ctx_do_push = 1; state1 = 1; } if _eq(state, 3) { ctx_do_push = 1; state3 = 1; } if (ctx_do_push) ctx_push(from, other, to, num, state); if (state1) { tmp = other; other = to; to = tmp; num -= 1; state = 0; depth += 1; } if (state3) { tmp = other; other = from; from = tmp; num -= 1; state = 0; depth += 1; } } if _eq(state, 2) move_slice(from, to); state += 1; } depth -= 1; if (depth) { ctx_pop(from, other, to, num, state); state += 1; } } } |

The macros `ctx_push()` and `ctx_pop()` push or pop their
arguments on a stack. So this does in fact the same thing as a recursive
function would do with it's local variables on the stack frame. The macro
`move_slice()` moves a slice from the `from` tower to the
`to` tower. Note that the expensive macros `ctx_push()`,
`ctx_pop()` and `move_slice()` are only inlined once each.

The same algorithm implemented recursively in perl reduces to:

sub hanoi($$$$) { my ($from, $other, $to, $num) = @_; hanoi($from, $to, $other, $num-1) if $num; move_slice($from, $to); hanoi($other, $from, $to, $num-1) if $num; } |

The compiled Brainf*ck program is about 64kB big and should run on a wide range of brainf*ck runtimes. The terminal must be able to understand vt100 escape codes and the output must be eighter unbuffered or auto-flushed at newline characters.