Posts Tagged ‘Programming’


I’ve been working lately on a problem known as “topswop”. “Solving” it is not the hard part, in fact it is ridiculously easy (4 lines in Erlang). The problem of it is to find a long sequence of numbers.

This is the problem:

Imagine you have a list of non ordered positive integers from 1 to n. All numbers are unique, no number occur in the list twice. E.g.
Now take the first number (in this case 3) and extract that many numbers from the head of the list (in this case [3,1,4]) and then reverse them (becoming [4,1,3]) and join them with the tail again. This would produce the list [4,1,3,2,5].

Now repeat the same procedure until the number 1 is first in the list. E.g. (from the beginning):

1) [3,1,4,2,5] -> [4,1,3] [2,5]
2) [4,1,3,2,5] -> [2,3,1,4] [5]
3) [2,3,1,4,5] -> [3,2] [1,4,5]
4) [3,2,1,4,5] -> [1,2,3,4,5] <- solved

Think of it as a deck of cards facing up and you get the idea. This particular sequence took 4 iterations to solve. Even though this problem is easy to solve it is really difficult to find long sequences. The longest sequence for n = 5 is 7.

currently I’ve gotten good results up to n = 17 but after that it is really difficult to find optimal solutions. Those of you that are interested there is a contest at which is now running (with a prize and everything :)) but I’m mostly in it for fun.

I’m looking mostly at how Erlang’s capabilities can be used wisely to solve problems such as these and currently looking at a distributed genetic algorithm but I haven’t come very far yet. If I have the time (or interest) to finish it I will post it here. If you enter the contest and use Erlang in a clever way then let me know 🙂

My solve function looks like this:

solve([1|_], N) -> N;
solve([I|_] = List, N) ->
    {L1, L2} = split(I, List),
    solve(append(reverse(L1), L2), N + 1).
Categories: Erlang Tags: , ,