The programming challenge at HHC MMX was to write a UserRPL program to sort a list of integers with the odd numbers appearing first and the even numbers appearing second. Entries were scored based on the run-time multiplied by the program size.
Just for fun, I wrote a solution in C code. Although this was clearly an invalid entry for the contest, I wanted to see if the huge increase in size would be offset by the increase in speed.
The UserRPL programs can be found here.
Here are the results. The input lists L10, L100 and L1000 are my own lists of 10, 100, and 1000 random integers. Note that these are not the input lists used by Joe Horn to judge the contest. Size is in bytes and runtime in seconds. Program names are as given in the link above, except that "dh2.c" is my C code implementation.
PROGRAM
BVB PRGM2 PRGM3 PRGM4 PRGM5 dh2.c
size 98.5 90 99 90 141 16433Run Time:
L10 0.27 0.42 0.40 1.15 0.90 0.05
L100 2.11 5.55 5.58 7.70 9.93 0.09
L1000 40.25 452.00 211.67 114.90 152.30 0.30Score (run time * size)
L10 26.1 38.1 40.0 103.6 127.4 828.2
L100 208.2 499.3 552.7 693.1 1400.5 1465.8
L1000 3964.5 40680.0 20955.2 10341.1 21474.3 4865.8
The C code is more than 100 times bigger than the biggest User RPL solution. For a 10-item list, it runs about 5 to 18 times faster, resulting in a "bytes times seconds" score far worse than any of the other programs. But when the list is 1000 items, it runs more than 100 times faster than the fastest User RPL program, which is itself almost three times faster than the next fastest entry. At 1,000 items, the C code's overall score is a close second place to the Bill Butler's winning program.
Note that with a 50G, it's easy to store the C program on an SD card and access it with a small stub program that just recalls and evaluates it.
Here is the C code:
#include <hpgcc49.h>
#include "hpobjects.h"// Callback function for quicksort. Sort by odd/even then by size
int
cmp(const void *p1, const void *p2)
{
long long ll1, ll2;
int mod1, mod2;ll1 = *(long long*)p1;
ll2 = *(long long*)p2;mod1 = ll1 % 2;
mod2 = ll2 % 2;if (mod1 && !mod2) {
// ll1 odd, ll2 even
return -1;
} else if (!mod1 && mod2) {
return 1;
}// both are odd or both are even
if (ll1 < ll2) return -1;
if (ll1 > ll2) return 1;
return 0;
}int main()
{
SatAddr oldList, newList;
SatAddr listOb, iter;
int size, i, j;
SatAddr *arr;
long long *llArray;sys_slowOff();
if (!STACKdepth()) {
return 0;
}
oldList = STACKpop();
if (!isLIST(oldList)) {
STACKpush(oldList);
return 0;
}size = LISTsize(oldList);
arr = calloc(size, sizeof(SatAddr));
llArray = calloc(size, sizeof(long long *));// Get the objects from the list
i = 0;
for (listOb = LISTfirstOb(oldList, &iter);
listOb;
listOb = LISTnextOb(&iter)) {if (isZINT(listOb)) {
ZINTdecodell(listOb, &llArray[i++]);
}
}qsort(llArray, i, sizeof(long long), cmp);
for (j=0; j < i; ++j) {
arr[j] = ZINTencodell(llArray[j], 0);
}
newList = LISTencodeN(i, arr, 0);
STACKpush(newList);
free(llArray);
free(arr);
sys_slowOn();
return 0;
}