## TopSwop

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.

`[3,1,4,2,5]`

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 http://azspcs.net/ 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).