The Mirrors and Light Problem

THE PROBLEM

Imagine a rectangle with mirrors on the boundaries. The problem is, if a ray of light enters from bottom left corner of the rectangle at an angle to 45° to both sides, and once it reaches the boundary, it gets reflected as it strikes the mirror. Now the question is, at which corner this light will finally reach such that after any further reflection, it will retrace its path?

For example, in the below image, a ray of light enters at (0,0) point and finally reaches (3, 5) point.

BRUTE FORCE SOLUTION

A brute force solution would be traversing step by step till you reach another corner.

The solution talks about xDirection, yDirection which will tell you the direction where light is going.

+1 means the next coordinate would increase the value and -1 will decrease the next coordinate value. For example, moving from left bottom to top right, direction would be (1, 1) and after first reflection with x=3, it will become (-1, 1).

Next optimization we can do is that we do not need to traverse through all points just to reach the next edge ( or Boundary ). We can calculate which is the nearest to the current starting point, by calculating the distance from the edges coming in current direction.

OPTIMIZED SOLUTION

In this solution, we will try to find if there is a way to find number of steps required to reach the desired corner.

For example, in our 3x5 problem. Lets consider 1 step as distance between (0, 0) to (1, 1). Then it will take a total of 15 steps to reach (3, 5) from (0, 0). Lets try to calculate this value.

Considering ray(1) starting from (0, 0) will take 3 steps to reach the other boundary of the rectangle(x=3), and after reflection it will take another 3 steps to reach the opposite boundary(x=0).

So, in conclusion, After taking

3, 6, 9, 12, ...                                            - (I) 

steps I will be at either at x=0 or x=3, and after taking

5, 10, 15, 18, ...                                          - (II)

steps I will be at either y=0 or y=5. You will reach the desired corner, when the condition

(x=0 or x=3) and (y=0 and y=5)                              - (III)

matched. So you will need common values from series (I) and (II), which are

15, 30, 45, 60, ...

We would need only the first element, as after that light will retrace its path back. This number is also the LCM(3, 5).

For a xLength X yLength problem, it would take LCM(xLength, yLength) steps to reach the other corner and LCM(xLength, yLength) / xLength gives us nth number in the x coordinate series.

We also saw that nth number in the series tells us which boundary we ends up. For example, in series (I) for n=1 light reaches boundary x=3 and for n=2 light reaches boundary x=0.

So if n is odd, its the boundary opposite to the one we started, else it is same one.

Hence in 3x5 problem, 15/3 = 5 (odd) tells us that corner will be at x=3 boundary and 15/5=3 (odd) tells us that corner will be at y=5 boundary. Intersection of which is (3, 5) corner.

Below is the implementation of above solution

So we saw how a small and easy looking problem can also test your mathematical skills.

Note: To further add complexity to the problem, we can also take input as the angle the light is entering instead of 45° or light is not starting from (0, 0).

Happy Solving :)