Project Euler Problem #33

June 16, 2010

Read the details of the problem here

Summary

Discover all the fractions with an unorthodox cancelling method.

Solution

Playing catch up writing this one up too. Just been reading this one back after six months or something…what dreadful code! I was trying for a Groovy solution and this is what I came up with. It just does an exhaustive search to find the four items and their product, and then uses a GCD routine to reduce it into it’s lowest term to extract the answer.

def ( np, dp ) = [ 1, 1 ]

(12..<99)
    .findAll { it % 10 != 0 }
    .each { n ->
        (n+1..99)
            .findAll { (it % 10 != 0) && (n % 10 == it.intdiv(10)) }
            .each { d ->
                def ( n1, d1 ) = [ n.intdiv(10), d % 10 ]
                if (n/d == n1/d1) ( np, dp ) = [ np * n1, dp * d1 ]
            }
    }

def ( gcd, n ) = [ np, dp ]

while (n != 0) {
  ( gcd, n ) = [ n, gcd % n ]
}

def answer = dp.intdiv(gcd)

This runs in 80 ms. Well within the 15 second deadline but the code does seem a bit convoluted in hindsight.

Conclusion

I did this with an over-use of Groovy features and, as such, it looks quite terrible. Performance was OK, but a less Groovy approach I put together after revisiting it ran in under 10 ms and, if anything, was even more terse.

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: