Shoot the Car

Problem: There is a infinite road. At t0, a car is at coordinate a. It will move towards either left or right (you don't know) at a constant speed b. You don't know the value of a and b. You just know they are integers. You have a gun and at t1, t2, ... tn, ..., you can shoot at any coordinate on the road. Can you find a way to finally shoot the car within finite time?

Solution: Since a and b will be finite, so the search space is finite. Naively, you can try to traverse a matrix M*N. At each tick, you try to shoot at M[i] + t*N[j]. If you fail to shoot the car after traversal, expand the matrix and traverse the part you haven't visited.

While more elegant way is try to order the states you want to search. We can start from (0,0), then (1,0) -> (1,1) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (-1, -1) -> (0, -1) -> (1, -1) -> (2, 0) -> .... Just start from the center and swirl!