Published 2011-12-14 @ 16:08
I was working on Project Euler problem #15 a few weeks back. It’s based on traveling routes from one corner of a grid to the opposite corner. The fact that it is on a fixed grid means that it is related to the Manhattan distance. Originally, I kept thinking about this problem the way it was stated, going from point A to B and was terribly stuck. There are ways to brute force it, but they’re not practical at all. Eventually, I decided to stop thinking about it in terms of Manhattan streets. I flipped the diagram 45° and started thinking about it from the bottom/destination up and how many paths there were up to the source:
Almost immediately the problem solved itself with a constant-time solution.
Sometimes it is simply a matter of changing your perspective on a problem to make the solution obvious.