From news-rocq.inria.fr!univ-lyon1.fr!in2p3.fr!oleane!tank.news.pipex.net!pipex!newsfeed.internetmci.com!chi-news.cic.net!newsspool.doit.wisc.edu!night.primate.wisc.edu!nntp.msstate.edu!nntp.memphis.edu!nntp.rhodes.edu!hal.mathcs.rhodes.edu!graham Mon Nov 6 15:04:24 1995 Article: 2787 of rec.games.corewar Path: news-rocq.inria.fr!univ-lyon1.fr!in2p3.fr!oleane!tank.news.pipex.net!pipex!newsfeed.internetmci.com!chi-news.cic.net!newsspool.doit.wisc.edu!night.primate.wisc.edu!nntp.msstate.edu!nntp.memphis.edu!nntp.rhodes.edu!hal.mathcs.rhodes.edu!graham Newsgroups: rec.games.corewar Subject: My entry Message-ID: <1995Nov3.152538.3024@rhodes> From: graham@hal.mathcs.rhodes.edu (Randy Graham) Date: 3 Nov 95 15:25:37 -0500 Nntp-Posting-Host: hal.mathcs.rhodes.edu X-Newsreader: TIN [version 1.2 PL2] Lines: 168 Well, here is my sorter. I figure it is too late for anyone to make use of this competitively, so I can post it, even though the deadline for today's entries isn't past. Truth be told, I am not certain this will work for all cases. I haven't been able to get it to fail, but I didn't code C to redcode exactly from the algorithm I had. Then, when optimizing it, I really let loose and cut things out that seemed unnecessary to me. So, if this doesn't get everything right in the tournament, you know I won't be surprised. What I did was put a bubble sort like pass at the beginning. If there are no swaps, I immediately go to see if I need to delete duplicate. If there are swaps, then I fall through to my quicksort. Within the qsort, I use a lot of old instructions that won't ever be used again as my temporary storage spots. Also, I use pointers to things when possible so I can remove duplicate code and instead swap a- and b-numbers. Anyone who is familiar with quick sorts might have trouble figuring out how this code is tied to a quick sort, but that's why your cc compiler won't let you use -O and -g. That is, optimized code is often hard to detangle into the original. This started out at 129 instructions. It ended up being 96. For this particulr problem, my worst case extra memory use is 10 cells. On all my tests (up to 450 data cells), I have not used more than 4 cells, so I think I didn't have the best test arrays. I learned a good bit about optimization while doing this, but I expect there may be more to do. Especially if anyone could share a better way to test for "less then." I don't know that anyone will want to see this, but I am posting it with hopes of getting others to post their warriors, which I certainly want to see. Now that I am looking at this, I see at least one more line I can remove. But, it will only improve the speed a couple of cycles, so I am not going to try do it. I guess I'll leave that as an exercise for the reader. Later, Randy ----------------------------------------------------------------- ;redcode-94 ;name Consortium ;kill Consortium ;author Randy Graham ;contact hp715!rgraham@peridot.spawar.navy.mil ;NSFCWT round 4 ;assert 1 ;strategy Use an iterative (non-recursive) quicksort to sort data ;strategy Uses lg n stack space and O(n lg n) average run-time ;strategy To speed up on sorted list, do a one pass bubble. Skip ;strategy to delete routine if no swaps or qsort if there are swaps. FLAGS equ (first+4000) DATA equ (FLAGS+1) STACK equ first CLEAROUT equ fini+1 first dat.f 0, DATA ;a - stack pointer, b - end of data dat_ptr dat.f DATA, first-1 ;contains start & end of partition bubl_ptr dat.f DATA, DATA-1 bubl_new sne.i (CLEAROUT-bubl_dwn2), @(bubl_ptr-bubl_dwn2) ;first get our data list size, then sort begin seq.i CLEAROUT, @first ;once we find end, don't change it bloop jmp.a begin, >first ;bubble sort check is written assuming a decreasing sort sortbubl jmn.b bubl_dwn, FLAGS mov.x bubl_ptr, bubl_ptr ;got to change - sort increasing ptr2 mov.i bubl_new, bubl_dwn2 bubl_dwn nop.a }bubl_ptr, >bubl_ptr bubl_dwn2 sne.i CLEAROUT, *bubl_ptr ptr1 jmp.a chk_del, bubl_new ;we got here if there were no swaps slt.b @bubl_ptr, *bubl_ptr jmp_bubl jmp.a 2, 0 jmp_bubl2 jmp.a qsort, 0 sne.b @bubl_ptr, *bubl_ptr slt.a @bubl_ptr, *bubl_ptr jmp.a bubl_dwn, 0 qsort add.b first, dat_ptr qsetup mov.i dat_ptr, {first ;start our stack jmn.b sorter, FLAGS mov.x checkline check_end sne.ab checkline, counter ;make sure not at end of list jmp.a setup, >checkline check_emp sne.i CLEAROUT, *checkline ;don't compare blank lines jmp.a check_end, }checkline check_dif seq.f *checkline,chk_del ;make sure still could match jmp.a setup, >checkline seq.i *checkline,chk_del ;clear out duplicates jmp.a check_end, }checkline matches mov.i CLEAROUT, *checkline jmp.a check_end, }checkline ;now close up holes in data closedat dat.f DATA, DATA closeup sub.ab #(closedat-checkline), counter ;pointer to end chk_close sne.ab closedat, counter ;end on time at_last jmp.a fini, 0 seq.i CLEAROUT, *closedat mov.i *closedat, >closedat jmp.a chk_close, }closedat fini mov.i CLEAROUT, @closedat end begin