Detailed mathematical approach

Problem Summary

The mirror is the ellipse \(4x^2+y^2=100\), except for a very small opening at the top where \(|x|\le 0.01\). The beam starts at \((0,10.1)\), enters through that opening, and its first actual impact on the mirror is \((1.4,-9.6)\). The task is to count how many reflections occur before the beam reaches the opening again and escapes.

This is a deterministic billiard problem inside an ellipse. Once two consecutive points on the path are known, the next segment is forced by the law of specular reflection, so the mathematics is about deriving a stable update rule for one bounce.

Mathematical Approach

Let \(F(x,y)=4x^2+y^2-100\). Every reflection point lies on the curve \(F(x,y)=0\). The key is to express one bounce entirely in terms of the previous point and the current point.

The Right State Variables

A single point on the ellipse is not enough, because the next bounce depends on the incoming direction. If the last two points are \(P_{k-1}\) and \(P_k\), then the incoming direction at \(P_k\) is

$v_{\mathrm{in}}=P_k-P_{k-1}.$

So the true state of the system is the ordered pair \((P_{k-1},P_k)\). The implementation stores exactly that pair and updates it after every reflection.

The Normal Vector and the Reflection Law

For an implicit curve \(F(x,y)=0\), the gradient is normal to the curve. Here

$\nabla F(x,y)=(8x,2y).$

Therefore the normal at \(P_k=(x_k,y_k)\) is \(n=(8x_k,2y_k)\). If \(v_{\mathrm{in}}\) is the incoming direction, the reflected direction is

$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$

Equivalently, one may normalize \(n\) first and write the usual unit-normal formula. Both forms describe the same line. Geometrically, the tangential component is preserved and the normal component is reversed, which is exactly the law of reflection.

The Next Intersection Without a Full Quadratic Solve

Starting from the current impact point \(P_k=(x_k,y_k)\), the outgoing ray is

$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$

Substituting this into the ellipse equation gives

$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$

Because \(P_k\) already lies on the ellipse, the constant term vanishes, so the quadratic factorizes as

$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$

The root \(t=0\) is the current point. The other root is the next impact point:

$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$

This simplification is the reason the implementations do not need a general quadratic formula. They only compute the nonzero root and step directly to the next reflection.

Worked Example: The First Reflected Segment

The beam arrives from \(P_{-1}=(0,10.1)\) to \(P_0=(1.4,-9.6)\), so

$v_{\mathrm{in}}=(1.4,-19.7).$

At \(P_0\), the normal is

$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$

Applying the reflection formula gives the outgoing direction

$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$

Then

$t\approx 0.3275153751,$

and the next point is

$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$

This concrete first step is a useful checkpoint because all three implementations reproduce it.

Detecting the Exit

The mirror is missing a tiny arc near the top. On the ellipse, any point with \(|x|\le 0.01\) and \(y>0\) lies on that upper opening rather than on reflective material. So the simulation stops as soon as the next would-be impact satisfies

$|x|\le 0.01,\qquad y>0.$

The last counted reflection is the bounce that sends the beam toward that gap. For the given initial ray, the total number of reflections is \(354\).

How the Code Works

Initialization

The C++, Python, and Java implementations store the previous point \((0,10.1)\), the current point \((1.4,-9.6)\), and a counter initialized to zero. That setup means the first loop iteration computes the reflection at the first interior impact point.

One Bounce Per Loop Iteration

Each iteration performs the same four geometric steps: build the incoming vector from the two stored points, compute the normal at the current impact point, reflect the direction, and use the nonzero root above to jump to the next point on the ellipse. After that, the state is shifted forward by replacing the previous point with the current one and the current point with the newly found point.

The C++ implementation uses the unnormalized form \(v-2(v\cdot n)n/(n\cdot n)\), while the Python and Java implementations normalize the normal first. These are algebraically equivalent. After each update the counter is incremented, and the new point is tested against the opening condition. When the test succeeds, the loop stops and prints \(354\).

Complexity Analysis

If the beam reflects \(B\) times before leaving, the running time is \(O(B)\), because every iteration uses only a fixed number of arithmetic operations. Memory usage is \(O(1)\): the algorithm keeps only a few floating-point coordinates, one direction vector, and the reflection counter.

For this specific problem \(B=354\), so the computation is tiny. The important point is not asymptotic difficulty but deriving a numerically stable geometric update that follows the exact reflection law.

Footnotes and References

1. Problem page: Project Euler 144
2. Ellipse: Wikipedia - Ellipse
3. Gradient and implicit curves: Wikipedia - Gradient
4. Specular reflection: Wikipedia - Specular reflection
5. Analytic geometry: Wikipedia - Analytic geometry