Home > Erlang > 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.
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).
Categories: Erlang Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: