Following on from the previous post… I am going to play with some general sorting algorithms, and hope that these might give me some inspiration for a more imaginative answer to our question. The first algorithm I will play with is selection sort. Here it is:
This doesn’t answer the question, which doesn’t call for a full sort. But it is starting to get the brain firing. I chose selection sort because it most closely resembles the implementation I posted previously. It’s not bad, I like recursion. But splicing lists is quite expensive in python, so it isn’t ideal. Plus, it runs in O(n^2) time, which is not ideal.
On the downside, it is very similar to my original answer. It is just an extended version of it. So this isn’t the way I want to head. I will play around with some other ideas and see if i can’t find something interesting over the next few days.
(refactored version of selection sort here – much nicer, the return x + y, is a trick I picked up from Haskell 🙂