Defcon 20 QUALS - urandom 300

Connect to the given host and port, with the provided password.

The problem is as follow:

  Here come 100000 uint16_t, please tell me how to sort them into
  ascending order by sending me pairs of indicies to exchange, one
  per line, in the format: <index1>:<index2>
  For example to exchange elements 123 and 9821 you should send:
  123:9821
  Valid indicies are in the range 0..99999 inclusive. Send a blank
  line when you are done. If you correctly sort the array in
  sufficiently few moves I will give you a key!
  You have about 10 seconds to finish, and a 5 minute wait between
  successive connections.

First, notice that UINT16_MAX < 100000, which means the sorting can be done efficiently in O(N).
Moreover, the number of swap allowed being limited, quicksort would be a terrible choice.

Since we need an in-place sorting algorithm to obtain the swaps, a solution could be to use a selection sort. We can then optimize it based on the fact that the number of elements is larger than the size of the pool these elements come from.

By walking through the array, we can figure out the frequency:

for (i = 0; i < N; i++)
    freq[array[i]]++;

and then compute the rank:

rank[0] = freq[0];
for (i = 1; i < 0x1000; i++)
    rank[i] = rank[i-1] + freq[i];

Now we just have to walk through the array and find out the first valid swap based on the rank of the element:

for (i = 0; i < N-1; i++) {
    if ((!i || i >= rank[array[i]]) && i < rank[array[i+1]])
        /* already on the right slot */
        continue;
    for (j = i + 1; j < N; j++ ) {
        if ((!array[j] || i  >= rank[array[j]-1]) && i < rank[array[j]] )
            /* found one matching */
            break;
        swap_and_send(array, i, j);
    }
}

Now let's compile with -O5 and run it on a decent computer with a decent uplink.

Download full code here.
Download server output dump here.