Monday, March 9, 2009

ProjectEuler problem 144

Project Euler is a website offering math challenges solvable by programming - usually few tens lines of code are enough. Last friday, after more than a year of Euler abstinence, I decided to have a look at it again, and ran across this cool problem (#144, check it out here).

So the goal is to find the number of times the laser beam will hit the ellipse-shaped cell before exiting through the input cavity.
First, let's formulate the problem with simple trigonometry. Have a look at the schema below:

The laser beam comes from A and hits the ellipse at point 0. We can calculate the slope m0: (yO-yA)/(xO-xA); we can also calculate the slope m1: -4*x/y. We need to calculate slope m2 and deduce B in order to iterate this process (find the next point of impact).

It appears clear that:
a = a0-a1
a = a1+PI-a2

tan(a) = tan(a0-a1)
= (tan(a0)-tan(a1))/(1+tan(a0)*tan(a1))
= (m0-m1)/(1+m0*m1)

tan(a) = tan(a1+PI-a2)
= tan(a1-a2)
= (tan(a1)-tan(a2))/(1+tan(a1)*tan(a2))
= (m1-m2)/(1+m1*m2)

Let's set X = (m0-m1)/(1+m0*m1)
X = (m1-m2)/(1+m1*m2)
-> m2 = (m1-X)/(1+X*m1)

We have the slope m2 of the reflected beam (OB). With the coordinates of O (x0,y0), we have the equation of the line:
y = a*x+b, with a=m2 and b=y0-m2*x0

The last step is calculate the coordinates of B. We have:
- the equation of the ellipse: 4*x^2+y^2 = 100
- the equation of (0B): y = m2*x+b

It boils down to solving the quadratic:
x^2*(4+a^2) + x*(2*a*b) + (b^2-100) = 0

And then we yield the coordinates of B. After a few 300-and-something iterations (nah I wouldn't spoil your Euler fun) you'll find out the reflected point falls onto the exit hole. Problem solved!

Wednesday, March 4, 2009

Sudoku solver

Nothing new or original here.
This Sudoku solver just aims to show how compact Python code can be...
The core of this piece of code is less than 40 lines of code. And we could do much better than that.