The Brainfuck Quest

One of my study resources for learning new languages is SPOJ. Actually, I’ve used it only to learn Ruby so far, but I’ll use it for any one to come (Python?, LISP?).

Although SPOJ international has a much bigger user base and challenge level, I’m giving more attention to SPOJ Brazil, and BRAIN, one of its problems, is giving me much more headache then it should do.

I decided to give it another try, but the code was big enough for me to try to fix it. But this time I will make it different by adding unit tests.

The old testing process

The testing process consisted of running the tests given in the problem site. But my code pass them and still fails in the tests given when the code is submitted.

The new testing process

I put some unit tests (thanks for embedding unit tests, Matz) to test individual commands of my interpreter, and I found the first problem with it. The # command was printing the first ten bytes of the input, instead of the first ten bytes of the vector. The tests given in the problem site didn’t cover this case.

Then I added tests for the four basic math operations. The divide test is quite good, since the loop nesting stack is something that goes seven levels up in the stack!

My code just blowed up when I tried to run it. After some search, I found nothing. After a lot of more searching, I found a little bug: When the interpreter read the ] command, it wasn’t appending the following code in the right order. The other tests didn’t find this error because the loops were quite simple, with just one nested loop.

Then again I tried to upload it, but it failed once more. Now, I let it there for a couple of days, and then, I found another problems with the whole nesting system. Now I have to say that what saved my life was a piece of paper and a pen. I drawn the whole nesting process, making arrows for variables names and arrays, and it all became clear to me. After a little brainstorming (and more drawing), I re-wrote it all and all my tests passed!

I was already screaming bad words when I realized it had to pass SPOJs tests too, and then it all came to ruins when I got a TLE in my face. The problem has a 1 second time limit. The problem became performance.

Profiling

I really, really thought about re-writing everything in C and upload it just to prove my algorithm works. I decided to give Ruby’s profiler a try, by running the code with the -r profile option.

The results

At the beginning I thought the Range#each method was the cause of my problems, but it isn’t because all relevant code runs inside one of them. I thought about whining about the language too, but for sure, the problem is with my algorithm.

Now I have a apparently functional brainfuck interpreter who does not run fast enough for SPOJs tests. The source is here. I don’t want to give up on it. My plans were to post it when it passes, but I just can’t see any solution in the near future, and I don’t want to abandon the blog either.

I’ll make more posts anytime this issue evolves. Or not.