Project Euler Problem #102

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 = U₀V₀ + U₁V₁

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

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

So this gives: cos θ = ( U₀V₀ + U₁V₁ ) / ( |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.

new File("euler_P102_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.

Project Euler Problem #62

Read the details of the problem here

Summary

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution

It’s a brute force approach with a guessed maxima but the coded solution is a fairly trivial one-liner (but I’ve split it for legibility).

def answer =
        (1..10000).collect { it ** 3 }
                  .groupBy { it.toString().toList().sort().join("") }
                  .findAll { it.value.size() == 5 }
                  .collect { it.value }
                  .flatten()
                  .min()

It runs in 1.14 seconds.

Conclusion

You’ve got to love the Groovy listops for problems like this. The code wasn’t the fastest to run but easily fell within my 15 second cut-off. It was very quick to put together and the code intent is clear to read. The only slight snag I found was there are actually two solutions that have five cube permutations but this was resolved easily to get the minimum value of the two solutions.

Project Euler Problem #99

Read the details of the problem here

Summary

Which base/exponent pair in the file has the greatest numerical value?

Solution

I took the straightforward approach to this one. As the resulting numbers would be huge it was just a matter of using log10(base) * exp and comparing those values. The coded solution is trivial.

def ( i, answer, max ) = [ 1, -1, 0.0 ]

new File("base_exp.txt").eachLine {
    def ( base, exp ) = it.split(",")*.toDouble()
    def log = Math.log10(base) * exp
    if (log > max) ( answer, max ) = [ i, log ]
    i++
}

It ran in 46 ms and took a very short time to write!

Conclusion

Groovy was a very nice language to use for this. It was very easy to read the file and process the contents. See how the spread-dot operator is used on the list resulting from the split to convert both operands in to Doubles ready for the next step. The only slightly irritating part was that I had to maintain my own record count as there is no eachWithIndex() method available on a File object. I could have treated this differently by reading into a list first but this seemed quicker!

As there was no heavy maths processing performance was fine, it was quick to write and the code intent is clear.

Project Euler Problem #5

Read the details of the problem here

Summary

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Solution

I didn’t need to write a program for this question. I vaguely remembered from school that the LCM of a series of numbers is just the product of the maximum powers of its prime factors, or something like that terminology.

It goes something like this. 2^4 = 16, which is less than 20, so that’s included but 2^5 isn’t as 32 is greater than 20. Similarly 3^2 = 9, is in, but 3^3 = 27 is out. Intermediate numbers will always be able to be factored into products of lesser powers of the primes and can therefore be ignored.

So this gives the list: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

So it wasn’t really much of a program to be written though groovysh did the calculation admirably. Performance wasn’t an issue!

Conclusion

Just goes to show it’s sometimes worth engaging brain before hitting the keyboard.

Reading ahead in the Project Euler questions it looks like factorization of large numbers is an ongoing theme so I’ll probably end up writing something that does this but I’ll do that when I need it.

Project Euler Problem #59

Read the details of the problem here

Summary

Using a brute force attack, can you decrypt the cipher using XOR encryption?

Solution

I actually got lucky with this one. The clue was that it contained English text, so the most common character was likely to be SPACE (ASCII 32). I tried for a simple frequency analysis first on that basis to find candidate key characters and it gave the right answer. It ran in 0.62 seconds.

If this approach hadn’t worked my next approach would have been to restrict the key characters as per the question and compare each decoded sequence against a valid character set e..g a-z, A-Z, comma, parentheses, full-stops, etc. looking for least exceptions and rating the key against that.

For something like this, where the plaintext type and key length was known it didn’t really warrant coding up a sliding XOR attack.

def seqs = [ [], [], [] ]

new File("euler_p59_cipher1.txt").text.split(",")
        .eachWithIndex { val, idx –>
            seqs[idx % seqs.size()] << val.toInteger()
        }

def answer = 0
def ASCII_SPACE = 32

seqs.each { vals ->

    def freqs = new int[256]
    vals.each { freqs[it]++ }

    def ( pkey, max ) = [ 0, 0 ]
    freqs.eachWithIndex { freq, chr ->
        if (freq > max) ( pkey, max ) = [ chr ^ ASCII_SPACE, freq ]
    }

    answer += vals.sum { it ^ pkey }
}

I went on to decode the passage and the result was truly Biblical. Not sure that I would have used that particular text in such a website but, as this solution proves, you don’t actually need to read it to get the answer. As to the key itself, well, I’d have stayed clear of that too. It’s one of those passwords you just NEVER use!

Conclusion

Groovy was a very nice language to use for this. It made it very easy to read the file and split it into sequences for each character in the keyword. In fact, that could have been a one-liner. The construction of the frequency table and the extraction of a potential key character was also very straightforward.

As there was no heavy maths processing performance was fine, it was quick to write and the code intent is clear.

It also helped that I’ve had an interest in cryptography since young. I thoroughly recommend Simon Singh’s Code Book as a gentle introduction into the topic.

Project Euler Problem #4

Read the details of the problem here

Summary

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

An obvious brute force solution completes in 1.14 seconds. The only simple optimizations I made were to count down rather than up for the two numbers and to put a guard condition on the expensive functions.

String.metaClass.isPalindrome = { ->
    delegate == delegate.reverse()
}

def answer = 0

for (i in 999..100) {
    for (j in 999..100) {
       def p = i * j
       if ((p > answer)  && (p.toString().isPalindrome())) answer = p
    }
}

As they say, “‘Nuff Said!”

Conclusion

The ability to extend to the String metaclass with an “isPalindrome()” method leads to quite a nice syntax but isn’t much different to just defining a support method. (I could also have put the function into the Integer class directly and hidden the String conversion in that.)

The solution ran well within my 15 second limit but still felt slow for what it was doing. An equivalent Java version runs in 137 ms. That’s around 8x faster.

Project Euler Problem #3

Read the details of the problem here

Summary

What is the largest prime factor of the number 600851475143?

Solution

Pretty straightforward question with a straightforward brute force answer.

The code simply uses a naïve Sieve of Eratosthenes to generate primes up to the  square root of the target number “n” and then factorises from that sieve.

long n = 600851475143L
def isPrime = new boolean[Math.sqrt(n)+1]
Arrays.fill(isPrime, true);
isPrime[1] = false

for (int i in 2..Math.sqrt(isPrime.size())) {
    if (isPrime[i]) {
        for (j = i + i; j < isPrime.size(); j += i) isPrime[j] = false
    }
}

def (answer, i) = [ 0, 2 ]
while (n > 1) {
    if ((isPrime[i]) && (n % i == 0)) {
        ( n, answer ) = [ n / i, i ]
    }
    i++
}

It’s all very quick to write but look at the explicit typing in the declaration of “n”. Without this the “n / i” calculation in the factorisation loop will assign a BigDecimal to n which will then fail on the next mod operation. It is also possible to work around this feature by casting the result but the typing approach is probably the lesser of two evils.

The script completes in 3.44 seconds, the sieve creation itself taking 3.36 seconds. This seems extremely slow. Porting this over into classic Java it returns in 32 ms with the sieve creation taking 31 ms. That’s 100 times faster.

A simpler solution, without the sieve and relying on the BigInteger#isProbablePrime method returns in 1.21 secs, whereas the Java version of this takes 0.87 secs.

Conclusion

Groovy didn’t actually add much to this solution apart from removing the boilerplate class code that Java required (and that IDEs generate automatically so it’s not much of a saving). The multiple assignment syntax was nice but nothing that I couldn’t have done without.

The fact that doing calculations like this means that the developer has to be aware of the types of the variables isn’t really a big deal but does suddenly make you aware that you’re not running in a real typeless environment like Ruby or Python. The runtime error message I received, “Cannot use mod() on this number type: BigDecimal” was a bit of a surprise and emphasises how much testing is necessary with dynamically typed languages where the number types can differ in the operations they support.

It appears from this that Groovy is imposing quite a severe overhead, adding some two orders of magnitude to numerical processing. If I need to do any real number crunching it’ll be best to create a proper Java helper class and use it from the Groovy script.

For the BigInteger#isProbablePrime solution (shown below), Groovy does provide for a much cleaner syntax than the Java version in which it’s obvious that the BigInteger class has been grafted on and, without operator overloading being available, is a bit of a stranger in a strange land.

long n = 600851475143G
def (answer, i) = [ 0, 2G ]
while (n > 1) {
    if (i.isProbablePrime(100) && (n % i == 0)) {
        ( n, answer ) = [ n / i, i ]
    }
    i++
}

See how easy it is to make “i” a BigInteger simply by appending a “G” to the value assignment. So it’s still necessary to be aware of the type, but this makes it easier than having to explicitly “new” a BigInteger.

The timings for this non-sieve solution show that, for large numbers of primes to be checked it’s almost always preferable to use a sieve in Java, whereas in Groovy there’s a higher tolerance given the overhead of building that sieve.

Project Euler Problem #2

Read the details of the problem here

Summary

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution

Remember that the Fibonacci sequence, whereby the next number in the sequence is the sum of the previous two elements, gives this series:

x, y, x + y, x + 2y, 2x + 3y, 3x + 5y, …

I need to capture the even-valued elements, i.e. every third element, where the summed multipliers of x & y is even…or I can just add the two previous elements and skip every third element. In the sequence above the “x+y” element would get missed out.

def (x, y, answer) = [ 1, 1, 0 ]

while (y < 4000000) {
  answer += (x + y)
  (x, y) = [ x + 2*y, 2*x + 3*y ]
}

This runs in 0.33 seconds. Again really not as fast as I might expect, in fact, pretty slow. So I tried it out in straight Java…a similar solution coded in Java (and using a temporary variable rather than the multiple assignment syntax available in Groovy) runs in 0.0000006 seconds (0.6 microseconds). Interesting.

I could have just generated Fibonacci sequence normally and used "element & 1” or “element % 2” to see if it was even. A solution like that is fractionally quicker at 0.30 secs in Groovy as there’s less math going on.

Conclusion

Groovy didn’t actually add much to this solution apart from removing the boilerplate class code that Java required (and that IDEs generate automatically so it’s not much of a saving). The multiple assignment syntax was nice but nothing that I couldn’t have done without.

It appears from this that Groovy is imposing quite a severe overhead around numerical processing. If I need to do any real number crunching it’ll be best to create a proper Java helper class and use it from the Groovy script.

Project Euler Problem #1

Read the details of the problem here.

Summary

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution

I guess I could have used summing of arithmetic progressions to work this out even by hand but would it have been as quick as writing this brute-force one-liner in Groovy?

def answer =
    (1..<1000).findAll { (it % 3 == 0) || (it % 5 == 0) }.sum()

This runs in around 0.44 secs which seems a bit slow given it’s not doing any heavy lifting but it’s well within the 15-20s that I’m allowing myself for these Project Euler jobs.

Conclusion

In this case, Groovy’s ranges, list selector and list aggregate functions make this a snap to write and to understand. I must admit to preferring the a..<b syntax for an exclusive range expression to Ruby’s open range a...b syntax where it’s too easy to miss the extra full-stop on reading.

Project Euler – A Groovy Approach

I recently came across Project Euler which is a site that hosts a “series of challenging mathematical/computer programming problems” in order to “provide a platform for the inquiring mind to…learn new concepts in a fun and recreational context.”

Having some time on my hands recently I decided that I’d like to have a go at some of the problems and thought that I’d take the opportunity to use Groovy, which I’m learning, to do any necessary programming in.

I’m going to write up my solutions here, in brief, to the problems I tackle and comment on how Groovy was, or wasn’t, of help in the development. I’ll just be using the Java 6 Runtime & Groovy 1.6 SDK without adding on 3rd party libraries that might take some of the headache away. I am trying to pick things up from first principles as much as possible.

I don’t think I’ll be giving anything away – Project Euler has been around for quite a while, since October 2001, and the answers to the older, easier questions are already available on the Internet. I expect it’ll take me quite a while to get to the point where a solution isn’t published somewhere.

The Project Euler website recommends that programmatic solutions should run in under 60 seconds. Since that was around written around 8 years ago and given the increase in computer power over that time, I’ll be aiming for my solutions to run in under 15 seconds (even if I need to slip into proper compiled Java code from time-to-time).

I’m developing on an Acer Aspire 8930G w/ 2.53 GHz Core 2 Duo CPU and 4GB RAM running Windows Vista Ultimate SP2 32-bit. It gets 5.4 and 5.9 Windows Performance Ratings for the Processor and Memory respectively.

Note: Some of the programming I’ll be doing might be a bit slip-shod and not up to "enterprise” standards – this is a hobby project after all! I’ll make appropriate notes on such as I progress.