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 a 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 of 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.
Over the past couple of years I keep on coming back to Project Euler, it’s nice when you just want a quick challenge, or to try your maths skills. It’s highlighted how rusty some of my concepts were, and I’ve learnt a whole load of new ones along the way. I really like the way that the example problem given is quite quick to determine using brute force, but the desired answer always needs a . . .
The challenge set by problem 18 was By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 + 9 = 23. A 15-row triangle was then supplied for which the program must determine the corresponding maximum value taking a similar path . . .