7
$\begingroup$

You are given an m x n grid. A dimensionless ball is placed at the centre of one of the grid squares and starts moving in one of 4 directions: north-east, north-west, south-east, or south-west. The ball continues moving until it reaches the edge of the board at which point, it bounces back in accordance with the laws of Physics.

Example in which the ball does not reach all squares.

Given m, n, the initial position and direction (NE / NW / SE / SW) of the ball, is it possible to determine whether the ball will ever reach a specified target grid square (x0, y0)?

It is possible to answer the question by exhaustively tracing the movement of the ball, but is there any easier more efficient alternative? Any pointers to related literature would also be much appreciated.

$\endgroup$
1
  • 4
    $\begingroup$ The standard method of approaching these types of problem is to extend the grid infinitely. The ball bouncing off the walls is really the same as the ball continuing in a straight line into a mirrored version of the same grid. $\endgroup$ Commented Nov 4, 2015 at 10:31

1 Answer 1

6
$\begingroup$

Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds. You should keep a hash table of all states of the ball that have been seen before (where the state of a ball is the grid square it is in, and which direction it is heading); if you see it repeat a past state, then you know it will loop forever and you can stop tracing the movement any further. With this way, tracing the ball's movement will take at most $O(mn)$ time in the worst case.

This can be sped up by using a little bit of simple algebra to calculate "given the current state, what's the next wall the ball will hit?" in $O(1)$ time -- that will be faster, but not easier.


There is a more elegant and efficient solution, based upon number theory and on Tom Van der Zanden's technique of extending the grid infinitely.

Imagine a parallel universe where ball travels in a straight line in an infinite grid; as Tom says, bouncing off the walls in our universe is equivalent to continuing in a straight line in the parallel universe. This is the first insight we will use.

Let's work out the implications of this insight. In our universe the ball starts at some initial coordinate $(x_0,y_0)$, moving NE, and we want to know if will ever reach coordinate $(x',y')$. What does this mean in the infinite universe? Well, imagine placing mines at coordinates $(x',y')$, $(x',2n-y')$, $(x',y'+2n)$, $(x',4n-y')$, ..., $(2m-x',y')$, $(2m-x',2n-y')$, ... -- in particular, at coordinates $(2im \pm x',2jn \pm y')$ where $i,j$ range over all integers. Then I claim that the ball will eventually reach coordinate $(x',y')$ in our universe if and only if the ball will eventually hit a mine in the parallel universe. So our problem reduces to asking: in the parallel universe, will the ball ever hit a mine?

The second insight is that we can use number theory to answer that question. In particular, after $t$ units of time, the ball will be at position $(x_0+t,y_0+t)$ in the parallel universe. We want to know whether there exists any integers $t,i,j$ such that $x_0+t = 2im \pm x'$ and $y_0+t = 2jn \pm y'$. Re-arranging these equations and using the language of modular arithmetic, we are asking whether there exists an integer $t$ such that both of the following equations hold:

$$\begin{align*}t &\equiv \pm x' - x_0 \pmod{2m},\\ t &\equiv \pm y' - y_0 \pmod{2n}.\end{align*}$$

Now we're all set to apply number theory. In particular, this is set up perfectly to apply the Chinese remainder theorem. Define $g = 2 \gcd(m,n)$. Then the above system of equations has a solution in the integers if and only if

$$\pm x' - x_0 \equiv \pm y' - y_0 \pmod{g}.$$

In other words, we should check the following four conditions:

  • $x'-x_0 \equiv y' - y_0 \pmod{g}$
  • $-x'-x_0 \equiv y' - y_0 \pmod{g}$
  • $x'-x_0 \equiv -y' - y_0 \pmod{g}$
  • $-x'-x_0 \equiv -y' - y_0 \pmod{g}$

If any of those four conditions holds, then there is a solution to the above system of equations and thus in the parallel universe the ball will hit some mine; if none of those four conditions holds, then the ball will never hit any mine. (These 4 conditions are the relevant conditions if the ball is initially travelling NE. The other directions can be handled symmetrically with a similar set of 4 conditions.)

Rephrasing in terms of the original problem, we get a solution to the original problem that is easy to implement and runs in $O(1)$ time. We compute $g=2 \gcd(m,n)$ and check the four conditions in the bullet list above. If any of the four conditions holds, then the answer is yes: the ball will eventually reach the point $(x',y')$. If none of the four conditions holds, then the answer is no: the ball will never reach the point $(x',y')$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.