Project Euler Problem #73

April 9, 2010

Read the details of the problem here

Summary

How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Solution

This is really just a variant of Problem 71 that I solved using Farey Sequences. I found that I could use the same approach but the implementation proved trickier that I was hoping due to the magnitude of the problem.

I started by simply implementing a recursive version with a function that took the left-hand and right-hand denominators of a Farey pair, and calculated the mediant denominator. If it was within the specified limit it incremented the count and then called itself with the left-hand and mediant denominators, and then mediant and right-hand denominators. Very straightforward…but it blew the call stack.

I switched over to a manual heap-based stack, which is easy to do in Groovy, and used the same algorithm. The code for this is shown below and is very straightforward. However, this ran in 18.9 seconds so quite a way outside my 15 second limit. A port of this to Java ran in around 6 seconds, so I expect that most of the work was being done in the java.util.Vector (or Stack) code which, being synchronized, isn’t the fastest.

def stack = [ [3, 2] ]
def answer = 0

while (stack.size() > 0) {

    def (c, d) = stack.pop()    
    def m = c + d

    if (m <= 12000) {
        answer++
        stack.push( [c, m] )
        stack.push( [m, d] )
    }
}

Though this was sufficient to pass my time-limit criteria I felt that it would be possible to do this using a manually managed stack and avoiding tuples for the pairs. This meant that the code had to be changed somewhat and just preserved the right-hand denominator of the Farey pair. The code for this is shown below.

def ( stack, top ) = [ new int[12000], 0 ]
def ( c, d ) = [ 3, 2 ]
def answer = 0

while (true) {
    def m = c + d
    if (m <= 12000) {
        answer++
        stack[top++] = d
        d = m
    }
    else {
        if (top == 0) break
        c = d
        d = stack[--top]
    }
}

This runs in 6.0 seconds and so satisfies my success conditions! A Java version of this runs in 83.5 milliseconds (so around 70x faster – as I’ve come to expect from Groovy for computationally intensive programs).

Conclusion

The Groovy capability of using tuples and stacks meant that it was easy to create the initial heap-based stack solution albeit not particularly performant. The final solution didn’t really use any specific Groovy features.

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: