Project Euler Problem #144

April 1, 2013

Read the details of the problem here

Summary

Investigating multiple reflections of a laser beam.

Solution

A nice little problem and really helped by Euler providing the slope tangent for points on the ellipse. It’s a matter of finding the intersection point between the vector denoting the beam’s path and the ellipse equation and then reflecting it around the normal (at right angles to the tangent) of the mirror’s slope at that point (using the dot and cross products). This just repeated until the beam intersection is within a suitable tolerance of the entry/exit gap at the top.

def ( answer, epsilon ) = [ 0, 0.01d ]

def p0 = [ x:0.0d, y:10.1d ]
def p1 = [ x:1.4d, y:-9.6d ]

while ((answer < 1) ||
       !((Math.abs(p1.x) <= epsilon && (p1.y > 0.0)))) {

  answer++

  def a = [ x:p0.x - p1.x, y:p0.y - p1.y ]
  def b = [ x:-4.0 * p1.x, y:-p1.y]

  def ( dotp, crossp ) = [  a.x * b.x + a.y * b.y,
                            a.x * b.y - b.x * a.y ]

  def c = [ x: dotp * b.x - crossp * b.y,
            y: crossp * b.x + dotp * b.y ]
  def s = (-2.0 * (4.0 * c.x * p1.x + c.y * p1.y)) /
          (4.0 * (c.x * c.x) + (c.y * c.y))
  def p2 = [ x:s * c.x + p1.x, y:s * c.y + p1.y ]

  ( p0, p1 ) = [ p1, p2 ]
}



This executes in Groovy 1.8.8 under Java 7u17 in around 0.12 seconds, so well within my 5 second cut-off.

Conclusion

Groovy made for quite a terse solution to this problem. The ability to use tuples with named members as lightweight point and vector classes was quite convenient and made for more readable code. The multiple assignment capability kept the LoC count down too. It’s important to include the ’d’ type signifiers on the starting values to force the use of doubles throughout the calculations. This is one of those Gr-r-r-oovy annoyances that I’d prefer not having to worry about though.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: