Skip to main content

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.

Comments

Popular posts from this blog

Why do my Android Notification only appear in the status bar?

I'm definitely getting back into Android development, I'm remembering that feeling of 'Surely this should be easier than this!'. All I wanted to do was to schedule a local notification which behaved similar to a push notification pop-up. That is, as well as showing the small icon in the status bar I wanted it to pop up on screen to notify the end user. All seems fairly easily, I found this code for how to schedule a notification. That all worked perfectly, apart from the notification would only appear in the status bar. Searching around I found loads of different answers / solutions, mostly all saying the same thing:It only worked if you used 'NotificationCompat.Builder' in place of 'Notification.Builder', orYou had to set the priority to 'NotificationCompat.PRIORITY_HIGH'As usually happens, none of these solutions worked for me until I added in the missing piece of the jigsaw:- '.setDefaults(Notification.DEFAULT_ALL)'. For me this…

IPhone hangs when running from XCode

I've had this happen a couple of times now and the first time was a little worrying that I'd bricked my iPhone. Basically I was running an application on my phone via XCode and when rebuilding an updated version it failed with a "busy" error message. Stopping XCode and unconnecting my phone had no effect, the phone was stuck displaying the loading screen of the application and wouldn't respond to any key commands. To fix you have to hard reboot, holding the power and home button until the phone reboots - doesn't lose any of the data you have on your phone (a concern the first time I did it).

Do "Task Hours" add anything in Scrum (Agile)?

What do task hours add to the overall process in scrum?This was a question that has arisen from all team members in both instances that I've helped teams switch over to scrum. The benefits of artifacts like the comparative story point estimation, the 2 week sprints, stand-ups and the end of sprint demo have been self evident to the team, but as one I think every team member has expressed dismay when it comes to task planning and estimating each task in hours. Left unchecked there is a natural tendency for people to actually begin to dread the start of each sprint purely due to the task planning session.In my current role we've been lucky to investigate this further as a team.The team sat down to discuss the problems it was experiencing with estimating tasks in hours and the following common themes appeared:It is hard: Maybe it shouldn't be, but time estimation is hard! Story points are comparative and abstracted making them easier to determine, but time estimate is gen…