Here's an interesting problem: "Encode the order of a 52-card deck in 32 bytes". It's not as easy as it sounds! My solution is below.
#include <stdio.h>
#include <stdlib.h>
/* Encode array of ordinals [0 .. n-1] by using an ordered set as
* a binary search tree, removing the each leaf traversed until the
* set has 1 member. Traversal paths are the encoding. */
int encodeOrder(int* input, int* output, int n) {
int i,j;
int* o = malloc(sizeof(int)*n); /* ordered set */
for (i = 0; i < n; i++) { o[i] = i; }
int s = n; /* ordered set size */
int k = 0; /* output index */
for (i = 0; i < n; i++) {
int a = 0; /* interval [a,b] */
int b = s-1;
int c; /* center of [a,b] */
while (b - a > 0) { /* binary search in o */
int x;
c = (b - a) / 2 + a;
if (o[c] >= input[i]) {
output[k++] = 0; /* set next "bit" to 0 */
b = c;
} else {
output[k++] = 1; /* set next "bit" to 1 */
c ++;
a = c;
}
}
for (j = b+1; j < s; j++) { /* remove ordinal from o */
o[j-1] = o[j];
}
s --;
}
free(o);
return k;
}
/* Traverse ordered set as in encoding, returning and removing each
* leaf as the original ordinals. */
int decodeOrder(int* input, int* output, int n) {
int i,j,l;
int* o = malloc(sizeof(int)*n); /* ordered set */
for (i = 0; i < n; i++) { o[i] = i; }
int s = n; /* ordered set size */
int k = 0; /* input index */
for (i = 0, k = 0; i < n-1; i++) {
int a = 0; /* interval [a,b] */
int b = s-1;
int c; /* center */
while (b - a > 0) { /* binary search in o */
int x;
c = (b - a) / 2 + a;
if (input[k] == 0) /* if bit is 0, go left */
{
b = c;
} else {
c ++;
a = c;
}
k ++;
}
output[i] = o[c]; /* set next ordinal */
for (j = c+1; j < s; j++) { /* remove ordinal from o */
o[j-1] = o[j];
}
s --;
}
output[n-1] = o[0]; /* last ordinal is trivial */
free(o);
return k;
}