Towers of Hanoi in Brainf*ck

 

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.

[Hanoi screenshot]

 

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.