Monday, 8 October 2012

Project Euler #24

I'm trying to start up on project Euler again, one thing I do like is that it highlights how poor some of my maths knowledge actually is. Neither school or college covered many of these algorithms; which is bit of a surprise given that I did a four year mechanical apprenticeship with applied mathematics.....still never too late to learn

So I (re)started on problem 24 which read:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

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

I usually start with a brute force attack on the problem, using TDD and the supplied example to verify the output. This worked nicely for the given example, but even on modern computing power I couldn't get it to finish in a reasonable time to determine the required answer - it was taking much too long!

Resorting to Google for "fast ways to calculate lexicographic permutations" I found a great solution and explanation on www.mathblog.dk. On previous problems I've tried to stay away from exact answers, instead I learnt about the sieve of eratosthenes when trying to find ways to determine the 'nth' prime number and then implementing it myself, but in this case I decided to take their answer and plug it into my code. Having used TDD the whole way through I quickly extracted an interface off my brute force attempt and created a new implementation with this code, dropping that into my unit tests proved it would work and provided the answer in under 3ms.

Now 27 problems "solved" and counting, hopefully I'll find a problem that will allow me to reuse the algorithm from this problem so I can learn bout it some more.

No comments:

Post a Comment