By | 2007-11-03

KISS : Keep It Simple and Stupid

Sometimes I forget this principle. The other day was one of such days. I was trying to solve a problem at TopCoder (a website that runs computer programming contests)…

The statement was something like “given n males and m females, sit them down in a circular table, in a way that if you start removing every K persons, after m steps there will be only males”. It looks like a trivial problem (and it is), but the difficulties arrive when you consider a big K, starting to do loops with a different number of people each time.

I started using a lot of modulus operations and trying to get an elegant solution as well. But the modulus is quite expensive (in computational terms), and the code was getting confused (and of course it was really difficult to trace). I made a lot of examples with pen and paper, trying to abstract something useful. Suddenly I realized: why don’t I program just what I am doing with pen and paper? Just letting the computer iterates every step, counting and setting females at the K step. I programmed it, and later I verified (peeking other’s code) that it was the correct solution: simple, stupid, but effective. [Well, actually the complexity in this way is O(m*K), and using only modulus is O(m), but in a short domain (as they said, K<=1000) the first solution is faster.] This reminds me a classical quote:

“Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?” – Brian Kernighan