Project Euler Problem #24

February 9, 2010

Read the details of the problem here

Summary

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solution

A quick look on Wikipedia found the information about lexicographic order permutation. It was then just a case of coding that up in Groovy and remembering that the millionth permutation is actually permutation 999999.

def (s, perm) = [ "0123456789", 1000000-1 ]
def (elems, len) = [ s.toList(), s.size() ]

def fact = (2..<len).inject(1) { p, v -> p * v }

for (i in 0..<len-1) {
    def p = perm.intdiv(fact) % (len-i)
    def temp = elems[i+p];
    (i+p).downto(i+1) { elems[it] = elems[it-1] }
    elems[i] = temp;
    fact = fact.intdiv(len-(i+1))
}

def answer = elems.join("")

This runs in 0.45 seconds. A Java version, that uses char[] rather than an ArrayList runs in under 0.05 ms (or thereabouts – nanoTime() is precise but not that accurate under Windows Vista). I make that about 9000x times faster which is just ridiculous!

Conclusion

Groovy did the job OK for this solution. Kept the coding noise level to a minimum and avoided some boilerplate but nothing that can’t easily be done in Java.

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: