## Monday, June 4, 2012

### 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 = freq;
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.