Wednesday, December 26, 2007

The tendency to complicate things

If you're from Hong Kong, most likely you've played some kind of "Black Magic" games before. In case you don't know what I'm talking about, let me explain a bit.

The original "Black Magic" game involves a guesser, a hinter and a group of people. In the beginning of the game, the guesser is told to leave the room so that s/he cannot see what is going to happen. Then, the hinter will ask the group of people to pick an object in the room. After an object is picked, the guesser will be asked to come back and the hinter will point to a series of objects and ask the guesser whether the objects are the one the group chose. The guesser will keep saying no until the hinter points to the object the group chose, at which time the guesser will say yes and the crowd will wonder how the guesser knows that.

There are many variants of "Black Magic" games like this one and yesterday I tried another one. Instead of picking an object in the room, the group will pick one card out of nine (any card such as poker card is fine). The nine cards are arranged in a 3 x 3 fashion so that its layout resembles a rectangle. Like the original "Black Magic" game, the hinter points at a number of cards and asks the guesser whether the one being pointed at is the one the group chose. And, of course, the guesser will say yes when the hinter points at the right one.

The key to all these "Black Magic" games is to look for that subtle yet simple hint the hinter is giving the guesser. Because I played the original "Black Magic" game before, I knew that the hint must be something very simple. Yet, I was the last one who found out what the trick was.

Man, why did I suck so much? I should have some kind of advantage as I played similar games before, right?

When I thought about that on my way home, I figured out a pretty good reason why I'm not good with this sort of games. Most of the engineers, like me, are very accustomed to abstract and complicated thinkings. Because of the nasty technical problems we have so troubleshoot everyday, we have a natural tendency to think that all problems are complicated and we've to squeeze out every bit of our smarts to find out what the solution is.

If you know that we've taken classes like Algorithms and Complexity in college, you may show more mercy on our sin to complicate things. For example, there's a simple and slow way to sort an array of integers named Bubble Sort. Even if you're not a computer science major, it's easy to understand how it works. Say you have an array like

5 1 3 4 2

The concept of Bubble Sort is just to compare each pair of integers and swap them if the one on the right is less than the one on the left. So, after comparing 5 and 1, the array becomes

1 5 3 4 2

And then we compare 5 and 3 and so on. After one round of comparisons, the array becomes

1 3 4 2 5

We will repeat the process again by comparing 1 and 3 first and keep on doing the comparisons until the array is finally in its sorted form 1 2 3 4 5.

The concept is simple right? Yeah it is, but the algorithm is inefficient; its worst case complexity is O(n2), which is pretty damn slow if you're talking about n = 1,000,000,000.

So, what did the computer scientists do to speed things up? They tried to look for patterns and invent algorithms like Merge Sort that based on paradigms such as Divide and conquer. If you take a look at the implementation of Merge Sort, you will notice that it's not as simple like Bubble Sort anymore. In spite of that, it's much faster on average.

That's one reason engineers tend to think "Hmm, the solution can't be that simple." And, yet, the solution DOES happen to be that simple sometimes.

Come on fellow engineers, if you're playing another "Black Magic" game with your friends next time, don't look for patterns anymore (Okay, I know you love patterns). The patterns are noises; look for that single hint. After all, that guy is called a hinter, not a patterner :P