If you’ve lived in New York City, you have probably thought about the most optimal way to get from one place to another on a grid. But it’s so much more subtle and complicated…

Imagine that you are on one corner of a 10×10 street grid and trying to get to the other corner. The streets are of equal size and the lights turn from red to green every 1 minute. Each light is random, so you don’t know what it will be until you hit it. BUT, when you hit the intersection you know how many seconds until the light turns.

Experienced New Yorkers know that the most efficient way to move on a grid is not to wait for lights – walk on the x axis until you hit a light, then walk on the y axis, and keep repeating. If you think about it, that means that in our 10×10 grid example, you can avoid hitting lights until you hit the side of the grid. Once you have gone as far as you can in the y direction, you have to travel completely in the x direction and are forced to wait for any lights you encounter.

So considering the above, you are least likely to hit the edge of the grid if you travel in as close to a diagonal as possible. A diagonal keeps you as far away from the edges as can be.

So, there are some moments when simply following the lights is not optimal and it’s worth it to wait a few seconds to keep your path close to the diagonal.

The challenge: present a formula that answers the decision of whether to wait or continue, based on location in the grid and seconds left in your current light cycle.

Remember: calculating the expected wait time for a single light is easy, but for multiple lights it is difficult because you will be using your strategy. So it’s recursive, and it probably has some game theory in it.

Any ideas?