Monday, September 2, 2019

6-Year-Old Rule?

The story begins recently I am indulging in the quantum computing programming whose foundation involves a lot of linear algebra. The direct consequence is I want to solve almost all problems using the complex number, vector, and matrix. The Mars Rover problem got my attention.

The rover on the Mars surface only takes L, R, and M instruction. L means turn left. R means turn right. M means move 1 step forward. If the initial position is (0, 0) and facing North, what will be the location and facing direction after receiving couples of instructions? 

This is a perfect opportunity to practice my math, I thought. The direction and location are all complex numbers. I can manipulate numbers to make the code concise! I convert the L, R, and M instruction to complex number op:


  • turn left L is complex (0, 1) where the real part is 0 and the imaginary part is 1
  • turn right R is complex (0, -1)
  • move forward M is complex number (1, 0)
The new location and direction can be computed like the following:

  • new location += op.Real * Direction  //L and R's real part is 0, so it does not move location
  • new direction *= op  //M is 1, so it has no effect on the direction
It looks cool and code is concise. I avoided those unpleasant switch statements. 

Everything looks satisfying until I realize those expensive multiply operations might be a performance problem. I wrote a simple solution using those switch statements. The simple solution doubled the code. However, the performance is 30+% faster than my "elegant" one! 

I told my wife what was going on when I encountered her in the kitchen, with a little bit of frustration. She smiled and pointed my 6-year-old son. "If the solution can be understand by him, it must be faster." she said, "It requires a smaller brain so it runs faster."

Well, both algorithms are O(n). Maybe next time, I should think on the big O level. 

No comments: