HHC MMC Programming challenge inC code - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: HHC MMC Programming challenge inC code (/thread-176088.html) HHC MMC Programming challenge inC code - David Hayden - 12-20-2010 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 16433 Run 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.30 Score (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 #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; } ``` Re: HHC MMC Programming challenge inC code - Oliver Unter Ecker - 12-24-2010 David, Thanks for the interesting read. It inspired me to find out how ND1 (http://naivedesign/ND1) would do on this challenge. Here's my would-be entry: ` f(v)=v.sort(function(a,b){return(a&1&&!(b&1))?-1:(!(a&1)&&b&1?1:a-b)})` 71 bytes. This code is MorphEngine's "natural math" syntax for maximum compaction. Easier to read (but slightly larger; and we're sweating bytes hereā¦), it would be written like this: ``` function(v) { return v.sort(function(a, b) { return (a%2 && !(b%2)) ? -1 : (!(a%2) && b%2 ? 1 : a-b); }); }``` Run-time for a 1000-element vector is 0.035s on my iPhone 3GS. B*T score would be ~2.5 (71*0.035). Run-time for the original 64-element vector from the competition is 0.002s. Score: 0.142 (That's almost a factor 1000 higher than the UserRPL winner.) Run-time for a 100,000-element vector (generated in a little over a second) is 5.9s. The integer vector is created either through this RPL program ` \<< \-> n \<< [] 1 n START RAND 2E12 * RND 1E12 - + NEXT \>> \>>` or, for higher speed, this equivalent JavaScript program ``` function (n) { var v = []; for (var i=0; iR SORT DUP SIZE 3. ROT + \<< HALT DUP R\->I SWAP 2. MOD { OVER ROLLD } { UNROT 1. + } IFTE \>> STREAM DROP \->LIST \>> ``` Now you can SST into that code section as well. The top of the stack keeps track of where the odd numbers are inserted. With each even number inserted this pointer is incremented. HTH Thomas PS: Just tested this on a HP-48 emulator, but I assume this is similar on the HP-50. Re: HHC MMC Programming challenge inC code - Glenn Shields - 12-28-2010 Thank you Thomas, that did it - I could follow the ifte process, and the use of that counter to let higher odd numbers "hop over" the accumulated even numbers in the stack. Amazing what these RPL experts can do with the tools available. Regards, Glenn Re: HHC MMC Programming challenge inC code - Thomas Klemm - 12-28-2010 You might want to compare the programs in message #5 and #6 of this previous Programming Challenge. STREAM (or fold or reduce in other programming languages) is a powerful tool though some consider it harmful. Cheers Thomas Edited: 28 Dec 2010, 12:08 p.m. Re: HHC MMC Programming challenge inC code - David Hayden - 12-31-2010 Quote: Hello all, I'm still trying to figure out what is happening in the winning RPL program in the link. They are all amazing, but what is STREAM doing with the stack? It's mysterious, because going step by step leaves a list with the size on top. Debug seems impossible with this parallel list processing. Any help? cheers, Glenn Glenn, I have submitted an article to Datafile that analyzes all five entries to the programming challenge. Dave