Project Euler Problem #102

November 20, 2009

Read the details of the problem here

Summary

For how many triangles in the text file does the interior contain the origin?

Solution

This question had me wondering for a while as to what the best approach to take might be. In the end I went for a simple approach that just relied on the fact that the interior angles from any point within a triangle to the vertexes would add up to 360° or 2 * Pi radians. To calculate the angles at the origin I relied on some things I’d learned when I used to write computer games as a hobby.

The dot product of two 2D vectors, U and V, is equivalent to the following two formulae:

U•V = U0V0 + U1V1

U•V = |U| * |V| * cos θ

Where |U| is the magnitude of the vector U, i.e. sqrt( U0² + U1² )

So this gives: cos θ = ( U0V0 + U1V1 ) / ( |U| * |V| )

The coded solution is then quite trivial and just calculates the angle at the origin subtended by vectors out to the pairs of vertices for each line segment.

def answer = 0

new File("triangles.txt").eachLine {
    def (x0, y0, x1, y1, x2, y2) = it.split(",")*.toInteger()
    def ( a, b, c ) = [ [ x0, y0 ], [ x1, y1 ], [ x2, y2 ] ]
    def theta = 0.0

    [ [ a, b ], [ a, c ], [ b, c ] ].each {
        def ( u, v ) = it
        def dot = u[0] * v[0] + u[1] * v[1]
        def ul =  Math.sqrt(u[0] * u[0] + u[1] * u[1])
        def vl =  Math.sqrt(v[0] * v[0] + v[1] * v[1])
        theta += Math.acos(dot / (ul * vl))
    }
    
    if (Math.abs(theta - 2 * Math.PI) < 1E-7) answer++
}

It ran in 0.96 seconds and wasn’t difficult to write once I’d decided what approach to take! Note the importance of using an epsilon value (1E-7) when comparing floating-point numbers as you can’t rely on an exact equality.

There are probably quicker ways to do this (in fact, I know there are) but this approach was nice & straightforward to code off the top of my head and ran in an acceptable time.

Conclusion

Groovy makes reading a text file and parsing it into appropriate data structures quite simple. It didn’t really make any difference to the rest of the solution apart from perhaps the nice syntax on the <list of sides>.each{} loop as it was mostly just straightforward maths.

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: