RESET Program entry descriptions (continued) positions 41-80 ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- -()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()- ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- ================================================================= ============== 41 ====================== best_name ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS best_name 1879997 738 615 123 97 David Roe ================= best_name was submitted by David Roe at roe@research.att.com ================= ++ Please summarize the algorithm used by best_name Step one is quick routine for finding the odometer setting that was at least as large as the current setting, but that uses all different digits. Then I arranged the remaining four digits and subtracted to see if this was consistent with the initial odometer setting. If not a solution, the program incremented the current setting and went back to step 1. Speed tricks: by looking at the results on all 1000000 initial odometer readings, I found that the final digit of the solution was never 0 or 1. And there was another trick if the result of the subtraction was too far below the initial odometer. ++ What kind of tricks did best_name use to minimize code length? Nothing enlightened: Short variable names, a couple of macros, and #ifdefs for expunging all the debugging code. I found it useful to automate all the code shortening stuff in a batch file that used lex so that I could shorten succesive version of the "real" code without having to do it by hand multiple times. ++ Here's what I hated (and loved) about this POTM's scoring: Last time Fred pulled this "minimum progam length" stunt I swore I'd never do it again. Well, what can I say? This time I mean it, I'll really truly never do it again. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T Labs - Research, speech recognition. I love to fool around programming. ================================================================= ============== 42 ====================== Jack ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Jack 1879997 789 477 312 118 Justin Legakis ================= Jack was submitted by Justin Legakis at legakis@graphics.lcs.mit.edu ================= ++ Please summarize the algorithm used by Jack Of the 10! combinations, only 42171 are "interesting" -- that is, you can always find the best answer by only considering those 42171 final positions. Jack first makes an array of these solutions. Then, for each input miliage, Jack finds the solution with a binary search through the array. Jack actually stores pairs of values, the final odometer value, and the greatest odomeder value at which the trip odometer can be reset to arrive at the final value with all 10 digits different. The search is simply looking for the smallest starting value greater than the input. (This algorithm is correct only after selecting the 42171 "interesting" solutions. It would fail if Jack did not weed out the others.) ++ What kind of tricks did Jack use to minimize code length? minimizing and reusing variables, ?: operator, #defines, nothing too fancy. Wished I could find alternatives to using fopen(), scanf(), and printf(). Here's my binary search, with logic to handle wrap- around: for(l=0,i*=p>*S&p<=S[i=n-1];i-l>1;p>S[t=(i+l)/2]?l=t:i=t); ++ Here's what I hated (and loved) about this POTM's scoring: I like POTM's that are determined by the first score, not the tiebreaker... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Graduate student at MIT. ================================================================= ============== 43 ====================== kindly.accept ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS kindly.accept 1879997 795 639 156 108 P.Harode P.Patwardhan ================= kindly.accept was submitted by P.Harode P.Patwardhan at pnh@ee.iitb.ernet.in ================= ++ Please summarize the algorithm used by kindly.accept /* Program */ #includemain(int argc, char *argv[]) { char num[12], not_used[11],*c; register i,j,k,l; FILE *fp; fp=fopen(argv[1],"r"); /*Open datafile*/ while(fscanf(fp,"%s",c=num+5)!=EOF) { /*Loop until EOF*/ while(strlen(c)<6) *--c='0'; /*Add leading zeros*/ k=atoi(c); for(i=0;i<10;) not_used[i++]=1; for(i=0;i<6 && not_used[j=c[i]-'0'];i++) /* get repeat digit loc. */ not_used[j]=0; do { if(i>5) { i=5; /* all digits different */ not_used[j=c[i]-'0']=1; } while(i>=0) { for(;++j<10;) if(not_used[j]) { c[i]='0'+j; /* next highest not used digit */ not_used[j]=0; break; } if(j>9) { i--; /* no higher digit is free */ not_used[j=c[i]-'0']=1; continue; } else { for(j=0;j<10&&i<5;j++) if(not_used[j]) { c[++i]='0'+j; not_used[j]=0; } break; } } if(i<0) for(i=0;i<6;) { c[i]='0'+i; not_used[i++]=0; } for(l=0,j=9,i=1; j>0;j--) if(not_used[j]) { l += i*j; /* ascii to int */ i *= 10; } i=atoi(c); j=i-k; if(j<0) j+=1E6; }while(j 201345). Store result in p[]. } r(){ return the next permutation p[]. (e.g. 201345 -> 201346) } main(){ Parse the original number into digits and store in array o[]. FOR (g();;r()){ construct n-the smallest number possible from digits not used in p[]. IF (n <= current - start) print solution } } ++ What kind of tricks did R use to minimize code length? Not too many. 1. pack as many operations in one statement as possible. 2. #define for repeated code 3. Relied on global vars being initialised to zero when first used in calculation 4. pack for loop statements in head to avoid curly brackets (i.e for (;;a=3,b=4,s+=a);) 5. using recursive procedures 6. use puts instead of printf where possible 7. no variable type declaration, all vars are int 8. global variables 9. variables reused to serve different purpose, and current value of the variable in its new role reused if possible 10. relying on int being size 4 (code is not portable) 11. pointers are the same size as integers 12. incrementing loop in the body where appropriate (i.e. for(;;) b[n=o[i++]];) 13. some redundant operations are added to the code to be able to reuse #defines 14. when algorithm was testing for var>=0 it was modified to test for var>0 (e.g. if(m>=0) -> if(m) ++ Here's what I hated (and loved) about this POTM's scoring: The ratio of source code to execution time doesn't look fair before seeing other people's entries. Speed and elegance of the algorithm are more important than the size of the program. I'm not much into cryptic programming. I believe the reasons for limiting the source code size is to prevent hardcoding of results, but could have been achieved in a better way. In the end I had great fun doing what I don't normally do: making my program unreadable. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Telstra (tele-communications) Melbourne Computer Consulting POTM Too many to mention ================================================================= ============== 46 ====================== shlem ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS shlem 1879997 829 257 572 90 Leonid Shikhmatov Sorry ... no description available for shlem ================================================================= ============== 47 ====================== bitdrive ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS bitdrive 1879997 857 476 381 67 Russ Cox =================== bitdrive was submitted by Russ Cox at rsc@research.att.com =================== ++ Please summarize the algorithm used by bitdrive Basically, generate a list of all the possible permutations of the mileage, using a convoluted nested for using #define's. As you generate the list, generate the smallest trip odometer mileages and save them. (Its easy - just concatenate the unused digits). For each number fed in, binary search for it in the list and then just search up until you find a mileage such that ( mileage - trip > current mileage ) modulo 1e6. ++ What kind of tricks did bitdrive use to minimize code length? I had a giant sed script that removed unnecessary white space, renamed variables using defines, etc. It also removed the error checking parts of the code that were marked as expendable. ++ Here's what I hated and loved about this POTM's scoring: We didn't get to see everyone else's scores. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? School. Delbarton School, Morristown NJ. I enter or help run other programming contests. Deep down inside, I understand Windows 95 networking completely. I just can't verbalize it. That's it... I'd like to see some more interactive programs like CHOMP. ================================================================= ============== 48 ====================== Seed_Racer ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Seed_Racer 1879997 898 297 601 50 =Chad Hurritz ================= Seed_Racer was submitted by Chad Hurritz at churritz@king.cts.com ================= ++ Please summarize the algorithm used by Seed_Racer your basic find the next uniquely 6 digited number and print out the results. I wish i coulda found a monotonic funciton that does it (which i'm sure someone found.) ++ What kind of tricks did Seed_Racer use to minimize code length? not many extravigancies like some others have sure to have done. you gotta pat those ones on the back who get it small AND keep/make it faster. ++ Here's what I hated (and loved) about this POTM's scoring: Only knowing where you stand doesn't "strive" people to do better since they don't know how much they need to work in order to move up a step... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? where's RANK? where's RANK? I want to be asked "RANK?"! company vaxa, location usa, job company, fun mountain, secret yes, potm yay. ================================================================= ============== 49 ====================== cruzin2 ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS cruzin2 1879997 934 687 247 113 Don Shugard ================= cruzin2 was submitted by Don Shugard at dshugard@lucent.com ================= ++ Please summarize the algorithm used by cruzin2 Used chars to represent the digits of the odometer. Kept a table of the used digits. Worked the odometer digits from left to right checking to make sure it was unique. If not took the next available small number to find the next unique odometer reading. Once I had a unique number I made the smallest possible number for the trip indicator if the math was right this was the answer. If not kept on going... Interesting problems involving 9's and rollovers. ++ What kind of tricks did cruzin2 use to minimize code length? Substituted single letters for variable names. One big #define that was used in several places. ++ Here's what I hated (and loved) about this POTM's scoring: Loved the problem easy to understand and create test cases for. Using the size of the source code is a horrible metric. ++ COMPANY? Lucent Technologies LOCATION? Holmdel NJ JOB? MTS DO FOR FUN? Fly and Build Model Airplanes INNERMOST SECRET? Constants aren't, variables won't. POTM IDEAS? I have shared a few with you previously. ================================================================= ============== 50 ====================== grumble ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS grumble 1879997 938 701 237 14 Robert Bonomi ================= grumble was submitted by Robert Bonomi at bonomi@delta.ece.nwu.edu ================= ++ Please summarize the algorithm used by grumble analysis showed that for any 'unique' odometer reading, there was precisely -one- 'push-the-button' point that gave a "best" result. Thus one could 'pre-compute' a table of possibilities. And do a simple table-lookup to solve any particular case. (this methodology is optimized for "production" use, solving a large number of cases -- elementary analysis indicated that this would be a faster solution on the 1000-value 'final'; although probably *significantly* slower on the 100-number test set) ++ What kind of tricks did grumble use to minimize code length? conventional 'bad C coding practices' short variable names, no whitespace, except where *absolutely* necessary multiple statements per line 'type abuse' of passed parameters overlaying distinct data into different parts of a single array CSE, into temporaries and/or as pre-processor macroes Did -not- spend a lot of effort on size reduction, as a little preliminary calculation/research showed -time- reduction to be _dramatically_ more sig- nificant to a good score. ++ Here's what I hated (and loved) about this POTM's scoring: I thought the 'space vs. time' trade-off was a neat idea. I didn't think the factor was reasonable. life would have been a -lot- more 'interesting' if the source-size had counted approx 10x higher than it did. (would have made the space/time balancing question *much* more difficult to resolve. :) ================================================================= ============== 51 ====================== Mach5 ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Mach5 1879997 942 564 378 101 Carleton Garrison ================= Mach5 was submitted by Carleton Garrison at cgarriso@dulles.dcn.att.com ================= ++ Please summarize the algorithm used by Mach5 1. Save original odometer reading. 2. Parse odometer reading into 7 individual digits (integers) (7th is used to denote odometer rollover). 3. Looking at digits from left to right, find the first digit that duplicates a prior digit. 4. If duplicate found 4a. Add one to digit (nine become zero). 4b. Increment each digit to left as necessary. 4c. Initialize digits to right to be zero. 4d. Set odometer to reflect newly defined digits. 4e. Go to step 3. 5. Construct smallest number using remaining four digits. 6. If the current odometer minus the original odometer is greater than the four digit "trip" number 6a. Set digit pointer to right most digit. 6b. Go to step 4a. 7. Print results. ++ What kind of tricks did Mach5 use to minimize code length? Single character variable names. Remove all unnecessary blankspace. Multiple instructions per line of code to 80 char limit. Macro substitution for any code fragment, when beneficial. ++ Here's what I hated (and loved) about this POTM's scoring: I hate single run scoring - three runs are necessary at mininum. The first run should be thrown away - the score includes the overhead of loading the executable into cache which is contrary to the contest premise of program execution (this is significant on the machines I've worked on). Continue executions/runs (should require two) until consistent results are observed eliminating the possiblity that some fluke system lock may have tied up a resource and skewed the first [second] outcome. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Consultant/Independent C/UNIX/DBA working for AT&T in Northern Virginia. ================================================================= ============== 52 ====================== Underworld ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Underworld 1879997 943 463 480 33 Douglas Zongker Sorry ... no description available for Underworld ================================================================= ============== 53 ====================== odomagic ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odomagic 1879997 952 685 267 54 Kevin Ryan ================= odomagic was submitted by Kevin Ryan at kryan@aoc.nrao.edu ================= ++ Please summarize the algorithm used by odomagic It read each number in one at a time and parsed the digits starting from the MSD until a duplicate was found. It bumped the duplicate digit to the next highest available one (from an array-based digit pool) and then filled in the rest of the number and tripmeter from the remaining digits in the pool. This number (which was the lowest one that contained unique digits) was tested to ensure that it minus the orginal mileage would be greater than the tripmeter's. If not, the next higher unique-digit mileage was found and tested until it statisfied the condition. ++ What kind of tricks did odomagic use to minimize code length? Obviously not very good ones :) Odomagic used a few while() statements so a '#define W while' was used to save some chars. Nothing much else outside of using single char variable names and removing all white space. ++ Here's what I hated (and loved) about this POTM's scoring: If I must complain, I guess I would say that probably too much weight went to program size. This is not to say there shouldn't be *some* size weighting to keep everyone from just using a giant lookup table. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a programmer for the National Radio Astronomy Observatory in Socorro, New Mexico. Ideas? Has POTM done anything along the lines of finding prime numbers or PI out to a zillion places in base-3? I'll share my innermost secret only if the internet promises not to tell anybody. ================================================================= ============== 54 ====================== counterSTEER ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS counterSTEER 1879997 958 377 581 15 Brace Stout ================= counterSTEER was submitted by Brace Stout at brace@stoutware.com ================= ++ Please summarize the algorithm used by counterSTEER counterSTEER originally used recursive algorithms for practically everything, since they typically use less code. I opted for an iterative algorithm when I saw how much time was being spent in recursion. I would imagine I took pretty much the same approach as most people, filling in an array with digits, using a bit mask to keep track of which digits were used, checking the resulting values to see if the reset would need to occur before the initial value, and if so, incrementing a particular digit and trying again. I realized late in the game that I could have used an array instead of a bit mask to save time and code length, but I didn't have time to pursue it. I also didn't get around to removing the call to printf, which I'm sure ate a significant amount of CPU time. ++ What kind of tricks did counterSTEER use to minimize code length? To minimize code length, I did the standard stuff: one-character variable names, ternary operators instead of if statements, squeezing as much use out of the for(;;) loop as I could, using the implicit short-circuit of the logical && and || operators, using a single macro to declare parameters and variables for all functions, making maximum use of the lexical separation caused by the required carriage returns. ++ Here's what I hated (and loved) about this POTM's scoring: The code-length attribute of the scoring was a killer for me, since it goes against everything I strive for in my job as a software engineer. My code was unreadable, unmaintainable, took advantage of little-known compiler features, didn't use parentheses to make order of evaluation clear, used implicit type casts between pointers and integers, read characters into integer storage, etc., etc. Felt like washing my hands every time I compressed it for entry. However, I understand the need for the code-length to be factored into the scoring. With such a straightforward problem, it would have been easy to decrease execution time at the expense of increased code size. The extreme example would be a simple array lookup for each of the possible 1,000,000 odometer values (not that such a large program would be allowed). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? StoutWare Software Engineering does software and systems engineering in the metro Phoenix area. Software is primarily Ada, C++, and 'C' in embedded and UNIX environments. My latest hobby is R/C truck building and racing. I'd like to see A POTM where entrant's programs interact with each other. I know this has been done in the past, but has not been done recently. Maybe something similar to RISK? Or populations competing for resources in a digital world? Another (pretty dry) possibility: I've occasionally wondered if one could come up with a minimum number of rectangular operations (set, clear, toggle) to generate a given pattern. I haven't looked at it, so son't know if it is a trivial problem or not. ================================================================= ============== 55 ====================== blush ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS blush 1879997 967 850 117 71 Hans vanderWal Sorry ... no description available for blush ================================================================= ============== 56 ====================== ken ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS ken 1879997 973 617 356 59 Ken Thompson Sorry ... no description available for ken ================================================================= ============== 57 ====================== LongStrangeTrip ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS LongStrangeTrip 1879997 979 474 505 34 Jeff Stone Sorry ... no description available for LongStrangeTrip ================================================================= ============== 58 ====================== AllClear ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS AllClear 1879997 1016 344 672 2 Byon Garrabrant Sorry ... no description available for AllClear ================================================================= ============== 59 ====================== jura ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS jura 1879997 1034 637 397 94 George Choolinin Sorry ... no description available for jura ================================================================= ============== 60 ====================== Beethoven ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Beethoven 1879997 1081 590 491 31 Stu Rowland ================= Beethoven was submitted by Stu Rowland at swr@mtatm.ho.lucent.com ================= ++ Please summarize the algorithm used by Beethoven Beethoven used a brute force approach. It started at the current odometer reading and proceeded to generate the next value that did not contain duplicate digits. It then generated the trip odometer reading from the remaining 4 digits using them in increasing order. If the difference between the generated value and the trip value was less than the starting value, the process was repeated with the next nonduplicate value until one was found where the difference was greater than or equal to the starting value. In order to avoid testing for the rollover condition, if the starting value was greater than 987654-0123 = 987531 (the last reset point before rolling over to 000000), the starting point was set to 0. A bit mask was used to keep track of the digits used when generating the nonduplicate values. ++ What kind of tricks did Beethoven use to minimize code length? The program was first written in an understandable manner. Its length was then reduced by folding in those subroutines that were called only once, replacing all variables with single letter identifiers, and removing all unnecessary white space without exceeding the 80 characters per line restriction. ++ Here's what I hated (and loved) about this POTM's scoring: Minimizing code size means unreadable code. I suspect that the winner will actually be one of the larger programs because the final run of 1000 values will overwhelm small differences in code size. ================================================================= ============== 61 ====================== odofuscato ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odofuscato 1879997 1164 536 628 7 Andreas Eisele Sorry ... no description available for odofuscato ================================================================= ============== 62 ====================== roll-em ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS roll-em 1879997 1171 517 654 4 Martin Kealey ================= roll-em was submitted by Martin Kealey at martin@kurahaupo.gen.nz ================= ++ Please summarize the algorithm used by roll-em Generate-and-test; generate the next permutation after a given starting point and see if it answers the constraint about when to hit the reset button. I think I had my generator running pretty well, but it could have done with more smarts for choosing starting points, especially when it's just failed the previous test; just too many iterations it seems. ++ What kind of tricks did roll-em use to minimize code length? All normal obfusticated C stuff really: Inlining function which are only called once (only main() left) Common subexpression ellimination Single letter identifiers Removal of whitespace Removing (on the POTM master's advice) some #includes ++ Here's what I hated (and loved) about this POTM's scoring: Hated: nothing Disliked: I didn't win :-) I suggest that any POTM where code space counts towards the result should count tokens, so that long identifiers, whitespace and comments wouldn't penalize an entry -- so you wouldn't need a separate version "for show". If you like I have a program that will do this for C & C++ programs. Liked: I didn't have to spend ages working on my entry, and this time I didn't get the booby prize for the last submission. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company: Nobody wants my company, that's why I'm all alone at my keyboard. Actually, I'm self-employed, and people never leave me alone to get on with things. Location: 36.88888=B0S, 174.72116=B0E. ================================================================= ============== 63 ====================== dawn ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS dawn 1879997 1208 643 565 127 Kim-hang Chung ================= dawn was submitted by Kim-hang Chung at khchung@cs.ust.hk ================= ++ Please summarize the algorithm used by dawn Pseudo code below: Let M = odometer that records the miles travelled by the car since it was born N = trip odometer that measures the miles travelled by the car since it was last reset Input: M Find the smallest number T such that the 6 digits of (M+T) are all different. Determine N' which is the smallest number formed by the rest 4 digits. While (T < N') Do Find the next smallest T such that the 6 digits of (M+T) are all different Determine N' which is the smallest number formed by the rest 4 digits. End While Print (M+T-N') and (M+T) ++ What kind of tricks did dawn use to minimize code length? Change some of the "if" statements to triary operations. Store large constants (e.g. 1000000) in variables. ++ Here's what I hated (and loved) about this POTM's scoring: ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Hong Kong University of Science and Technology. Hong Kong. WWW : http://www.cs.ust.hk/~khchung/ Computer Science Department, HKUST, Hong Kong ================================================================= ============== 64 ====================== Odie_the_wonder_button ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Odie_the_wonder_button 1879997 1256 794 462 80 Glenn Larratt ===================== Odie_the_wonder_button submitted by Glenn Larratt at glratt@rice.edu ===================== ++ Please summarize the algorithm used by Odie_the_wonder_button Traverse the given odometer reading left to right, checking off each digit in a table as it's used, incrementing where necessary, backing up to the right on rollover. Once this process is complete, you have an odometer reading with 6 unique digits: create the smallest number consisting of the unused four digits, and determine if that number is smaller than the number of miles travelled. If so, you're done; if not, advance to the next unique six-digit reading and try again. ++ What kind of tricks did Odie_the_wonder_button use to minimize code length? #define'd a macro or two typedef unsigned u; for the number of times I needed to declare u's stuck to primitive manipulations (no mult/div) for speed did the arithmetic in bcd, so used "%x" for i/o ++ Here's what I hated (and loved) about this POTM's scoring: Liked that getting a solution was fairly easy to do, so lots of competition for efficient code. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Rice University Houston, TX USA "LAN Specialist" Dance, sing, eat ...is my outermost joy: my wife Elizabeth traffic modelling? something with a potentially real application...or alternatively, something absurdly whimsical (cf. Lemmings) ================================================================= ============== 65 ====================== Excuse_Me! ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Excuse_Me! 1879997 1281 1019 262 78 Krishna Tripathi =============== Excuse_Me! was submitted by Krishna Tripathi at kct@hotmail.com =============== ++ The algorithm used by Excuse_Me! 1. Read the Numer ( Reading of Meter A ) ** say 037368 ( = I ) 2. Add the smallest four digit number possible to make by excluding two most significant digits. ** 037368 + 1245 = 038613 3. Store the digits in an array of integers starting from left , till any repeated digit is found. ** |0|3|8|6|1|*|*|*|*|*| 4. Fill this array by the remaining digits in increasing order. ** |0|3|8|6|1|2|4|5|7|9| 5. Now the first six will be the reading of meter A and last four will be reading of meter B when it is possible to have an event of our desire. ** meter A |0|3|8|6|1|2| meter B |4|5|7|9| 6 If A-I is less than B then do the following till A-I becomes either greater or equal to B, 1. take the sixth (say CurrentLocation) element in the array ( =2) 2. swap it with the digit which is smallest of the digits that are # in the right side of this digit ( from location 7 to 10 ) # and larger than this digit ( =2), 4 in this case. ** meter A |0|3|8|6|1|4| meter B |2|5|7|9| 3. If none of the digits satisfy these conditions then decrease CurrentLocation (make fifth) and do the same. as it can happen in this case : meter A |0|3|8|6|1|9| meter B |2|4|5|7| || \/ * meter A |0|3|8|6|2|9| meter B |1|4|5|7| 4. After swapping sort the section of the array that is right of the CurrentLocation. meter A |0|3|8|6|2|1| meter B |4|5|7|9| ++ What kind of tricks did Excuse_Me! use to minimize code length? No special trcicks than to keep variable names of one character and declaring global variables so that they can be used by all functions and need not be passed. ++ Here's what I hated (and loved) about this POTM's scoring: * You enjoy too much of power . The system system should be more democratic . We shold have full right to know the strength and weakness of the people with whome we are competing( I mean strength and weakness of their programms ). But I enjoyed the frustration arising out of putting my all efforts but program not moving upward , as if gravity has increased ! ( don't you think enjoying frustration is a weird thing !, a new philosophy in itself ! ) ++ COMPANY? Tata Unisys Ltd. LOCATION? Bombay. JOB? Analyst/Programmer/Peon/Manager as the need arises. DO FOR FUN? Travel and sleep during travel. INNERMOST SECRET? Let it remain innermost. POTM IDEAS? I won't give beacuse I want to participate. ================================================================= ============== 66 ====================== tono ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS tono 1879997 1302 307 995 9 Antonio Esguevillas Sorry ... no description available for tono ================================================================= ============== 67 ====================== delphi.guys ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS delphi.guys 1879997 1307 750 557 122 K.Symeonidis J.Tsoukalidis ================= delphi.guys was submitted by K.Symeonidis and J.Tsoukalidis at ksymeon@hypernet.hyper.gr ================= ++ Please summarize the algorithm used by delphi.guys The algorithm delphi.guys used is rather simple. It passed through thorough examination and is like this : 1- at first we take the odometer mileage. (START) 2- Then we try to find the first mileage that has all the six digits different. (CURRENT) 3- The remaining four digits form a number. (REMAIN) (note that the order we get the digits from the smallest to the largest, thus producing numbers like 2456 etc) 4- if the CURRENT-START >= REMAIN then we can produce this situation by pressing the reset button at CURRENT-REMAIN mileage else we goto step 2, where another mileage with 6 different digits will be computed. Explanation of STEP 2. How to find a six-diff-digit mileage. We have a number, we break it into 6 digits like : 355344 we try to find if digit M is same with digit L (M 356000 (because digit 2= digit 3) Iteration 2=> 356010 Iteration 3=> 356011 Iteration 4=> 356012 which is the first mileage after 355344 with six different digits. Explanation of STEP 3. For the example above we get the REMAIN = 4789. Of course 356012-355344 < 4789, so we can't possibly form the 4789 in the small odometer, and we go to STEP 2 again. we find 356014 and 2789 still not good, then we find 356017 and 2489 still not good, then ........ ++ What kind of tricks did delphi.guys use to minimize code length? We didn't do any special tricks, other than using small variable names, using less variables, less functions and combining assignments and conditionals in the same sentence like : if (d >= (f=a+b+c+d)) We find ourselves puzzled though with the problem to produce faster code. We constantly changed a bit of our code, and went out to OS, and timed the program (with a special "home-made" millisecond resolution timer). We started at 13000 ms (or 13seconds), went lower to 7000ms, to 1000ms, to 510ms for 1000 numbers in our machine of course. ++ Here's what I hated (and loved) about this POTM's scoring: What I loved? The continuous quest for faster code. I have written a decreasing list with my millisecond scores :-) Wanna see it? : 13271 12567 7902 7710 7478 7397 7396 -> our first entry went to position 94. 5312 (major breakthrough :-)) 5237 1428 (something good in mind!) 1087 (no we get closer to 1000ms for 1000 numbers, yeah!) 1084 -> our second entry, went to position 84. Why? :-( 1067 1057 1016 1014 (Is this getting somewhere? :-) 995 --------------!!!!! BROKE THE 1000ms barrier!! Great hopes arise! 577 (Am I blind, I didn't see that thing?) 544 540 527 515 512 511 510.69milliseconds (LAST ENTRY. Haven't got any results yet!) Awaiting for the jury's decision!!! :-) What I hated? That I had to minimize code length with small variables, unstructured code, and that when I finished a version of the program, I had to concatenate lines and delete indentation spaces to produce a smaller source file. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? NAME: Kostas Symeonidis, 27 COMPANY: ArtLogic LOCATION: Thessaloniki, GREECE JOB: Computer Programmer, Teacher in Informatics HOBBIES: Ski, Inline Skates, Swimming, Sports of all kind generally... :-) This was my first POTM, I'm a rookie. I wrote this program with my student and friend, John Tsoukalidis, who I train for the national informatics contest. I usually search the Internet to find computer exercises and often I give him some problems to solve. So some day we started working on this POTM in Delphi. We discussed it, solve it, and then the idea to compete came, so I translated it to C++. (Of course I had to explain C to John, 'cause we use Pascal for the moment. No problem. He's so smart, he learned the basics in 5 minutes). When we found our program a bit slow, we started thinking about how to make it faster. It was a great exercise, I can tell. Thanks POTM Master! ================================================================= ============== 68 ====================== hope.it.works ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS hope.it.works 1879997 1328 703 625 51 John_Zer0 InfraRED ================= hope.it.works was submitted by John Zer0 and InfraRED at john@graphisoft.hu ================= ++ Please summarize the algorithm used by hope.it.works The algorithm increases the counter, and then tries to get the start mileage setting, a kind of reverse-thinking. ++ What kind of tricks did hope.it.works use to minimize code length? Everithing we could think of. First of all, all variables are 1 char long (like 'a' to 'z'). Some #defines used also, we even defined 'a[i' (to char z), so 'a[i]+=b' looks like 'z]+=b;' after the conversion. Very funny ;) Note that k(;;) (k defined as 'for') is 3 chars shorter than while(1) ! ++ Here's what I hated (and loved) about this POTM's scoring: I think it was pretty interesting. Though we didn't know how much time the program takes to load/initialise on your computer (this info could've be used on the 100 items -> 1000 items time estimation). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? University, Technical. Pretty cool, but only 1/2 month util the exams! ;) Borland C++ was used to write the code, in ANSI mode... Oh, and concernig the timings, it seems as our lame PC (AMD PR100) was much faster than your Sun. But I really don't believe this... ================================================================= ============== 69 ====================== aleph ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS aleph 1879997 1353 919 434 130 Arie Tzvieli ================= aleph was submitted by Arie Tzvieli at atzvieli@lehman.com ================= ++ Please summarize the algorithm used by aleph PHASE 1 - PREPARE 1. Generate in ascending lexicographic order all 6 digits numbers having all digits different 2. For each number, check if it is eligible (if X denotes the numbers generated in Step 1, and Y are the corresponding MINIMAL 4 digits number such that XY has 10 different digits, and Z={x-y|x in X, y in Y, and y corresponds to x} then a is ELIGIBLE if there exists a number d for which z,a is the BEST solution. This is easy to implement by comparing the z value corresponding to the current x number with the z value of the last eligible number - the new z value has to be the greater of the two. Retain all eligible numbers in an array. PHASE 2 - SOLVE 3. For each given number find the best solution in the array generated in Step 2 using binary search. The solution is the first number in the array greater or equal to the given number. ++ What kind of tricks did aleph use to minimize code length? One character names for all variable, #define C continue, squeeze multiple instructions into one row ++ Here's what I hated (and loved) about this POTM's scoring: I liked the minumum mile criteria. I hated the length criterion, encouraging me to write ineligible code that was hard to debug. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY - ProLogica Inc. Job: Consulting at Lehman Brothers. Do for fun: meditation. ================================================================= ============== 70 ====================== another ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS another 1879997 1422 609 813 24 Mark Huizer ================= another was submitted by Mark Huizer at xaa@xaa.stack.urc.tue.nl ================= ++ Please summarize the algorithm used by another Hmm... * find the first permutation below the start number * while not possible - see if next permutation is possible from start point ++ What kind of tricks did another use to minimize code length? Ha ha! * beer, much beer! * funny modes * an evening with my neighbor behind a computer * 3 hours of laughing for every 10 bytes gain on the code ++ Here's what I hated (and loved) about this POTM's scoring: hated: finally writing down some permutation creating code loved: finally writing down some permutation creating code ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? fun, fun, fun ================================================================= ============== 71 ====================== matzke ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS matzke 1879997 1473 641 832 104 Robb Matzke ================= matzke was submitted by Robb Matzke at matzke@llnl.gov ================= ++ Please summarize the algorithm used by matzke 1: Based on the current odometer reading, choose the next larger odometer value with unique digits, mod 1000000 2: Choose the smallest possible trip meter value from the remaining four digits. 3: If odometer-trip (mod 1000000) is smaller than the initial odometer reading then go back to step 1. It typically takes about 80 iterations to find a solution. The smallest possible final trip meter reading is `0123', so we can travel 123 miles before we even start considering solutions. The function to return the next larger number with N unique digits worked from left to right always choosing the smallest available digit not smaller than the digit currently at that position (modulus 10). When a digit changed then all remaining digits were reset to zero before the process continued. When the digit wrapped from 9 to 0 then the left digits were increased by one (the carry from 9 to 0) and new left digits were generated recursively before continuing. ++ What kind of tricks did matzke use to minimize code length? One-letter variable names, no indentation, about 80 characters per line, spaces only where necessary. I also did `#define int I'. ++ Here's what I hated (and loved) about this POTM's scoring: I found out about the POTM contest two days before I left for Thanksgiving vacation so it was nice being able to see within 24 hours that my program compiled and ran correctly. However, since I only had one evening to program, it would have been nice to see the execution time and length of other entries to have a goal to shoot for and to help decide what speed/size tradeoffs to make. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a computer scientist for the Scientific Computing Applications Division of Lawrence Livermore National Laboratory in Livermore, CA. I work on various physics support codes including the publicly released MeshTV used for viewing scientific mesh data. For fun I bicycle (road), hike, watch birds and take pictures. ================================================================= ============== 72 ====================== road_warrior ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS road_warrior 1879997 1503 888 615 42 Jim Curran Sorry ... no description available for road_warrior ================================================================= ============== 73 ====================== Kicks_On_66 ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Kicks_On_66 1879997 1530 882 648 18 Scott Everett ================= Kicks_On_66 was submitted by Scott Everett at severett@gvmail.ih.lucent.com ================= ++ Please summarize the algorithm used by Kicks_On_66 1. If the starting mileage of odometer A was higher than 987654 or lower than 12345 then I automatically rolled it up to 12345. That is because there are no unique answers in that range for the A odometer, so there could be no unique answer overall. 2. B can not be unique for at least 123 miles, since 0123 is the lowest unique value. Therefore, odometer A is always advanced by at least this much at the start to save checking those first combinations. 3. Once the initial value of A had been modified by the first two steps above, I advanced the A odometer until all 6 digits were unique. This was not done by adding one to the mileage and re-checking, instead I looked for the first decimal location that duplicated an earlier digit and then I advanced that digit by one. The digits after that were then selected to be the lowest value for each digit that was unused from the digits already in use for the A odometer. 4. Finally, I selected potential odometer B values by using an array of 10 digits and marking off those that were used for the mileage on A. I then created a value for B by choosing those digits that were unused in A and arranging them lowest to highest. 5. It was essential to account for wrap-around of both the A and B odometers, but because of the method I used to generate B values I was able to ignore that case. ++ What kind of tricks did Kicks_On_66 use to minimize code length? Used single character variables, stripped out all comments, and put multiple statements on a single line (up to 80 char max) to minimize the number of carriage returns. Also, stripped out all unnecessary spaces. ++ Here's what I hated (and loved) about this POTM's scoring: I did not like having to strip out the comments and use single character variables to minimize the size of my entry. This meant each time I sent in a new entry I had to strip it down. I would prefer that the object size be used instead of the raw size of the file, it saves time and energy. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent Technologies in Lisle, IL. I am a 5ESS Product Manager. ================================================================= ============== 74 ====================== ugly ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS ugly 1879997 1549 1141 408 103 Paul Nelson Sorry ... no description available for ugly ================================================================= ============== 75 ====================== razorback ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS razorback 1879997 1670 591 1079 22 Mike Wilder Sorry ... no description available for razorback ================================================================= ============== 76 ====================== watsoncolin ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS watsoncolin 1879997 1698 1005 693 106 Colin Watson Sorry ... no description available for watsoncolin ================================================================= ============== 77 ====================== slow_but_long ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS slow_but_long 1879997 1865 336 1529 40 Steven vanEnk ================= slow_but_long was submitted by Steven vanEnk at vanenk@mpq.mpg.de ================= ++ Please summarize the algorithm used by slow_but_long Add 123, find next smallest 6-digit number A with different digits, construct smallest 4-digit number of remaining digits, and check if this is solution: if not add 1 to A, and repeat. ++ What kind of tricks did slow_but_long use to minimize code length? Not many, after submission of my first try I had no time to improve.... ++ Here's what I hated (and loved) about this POTM's scoring: It's nice to have an easy problem, except that since it's easy for everyone, it's difficult to win ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? University of Innsbruck, Austria, physicist. Participated to learn C. This could be a joke. ================================================================= ============== 78 ====================== yuguang ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS yuguang 1879997 1989 1505 484 39 Yuguang Wu Sorry ... no description available for yuguang ================================================================= ============== 79 ====================== DashBored-Lite ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS DashBored-Lite 1879997 2198 728 1470 85 John McMillan ================= DashBored-Lite was submitted by John McMillan at jcm@pegasus.att.com ================= ++ Please summarize the algorithm used by DashBored-Lite Algorithm? Watts an Algorithm? First hack just searched for the next "digit-unique" ODOMETER (6 digit) number at least 123 miles (minimum trip-meter amount) beyond the start-odometer setting. Once that 6-digit number was chosen, the minimum trip-meter setting was obvious and was tested for feasibility. (A trivial incrementation scheme was used any time a digit was found to duplicate an earlier (higher) digit. Further hacks used various algorithm speedups, such as tables of masks rather than bit-shifts. Alas, the TIMEX variability of all these speed-ups was so great on my home system that I couldn't identify which changes reduced times, so why bother Fred with'em?! %^) ++ What kind of tricks did DashBored-Lite use to minimize code length? 'Just wrote bad code -- shades of the original BASIC compilers using single letter names! If it boils down to a byte war, I lose as I failed to "#define R register". %^) ++ Here's what I hated (and loved) about this POTM's scoring: How could one hate anything Fred thought up? (Are there extra Brownie points?) ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Actually, on-the-beach (by own choice) these days. Hmmm... should face "reality" (yuck) and interview, shouldn't I? ================================================================= ============== 80 ====================== odoracle ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odoracle 1879997 2233 1184 1049 92 Ljupco Taseski ================= odoracle was submitted by Ljupco Taseski at cu151@fim.uni-erlangen.de ================= ++ Please summarize the algorithm used by odoracle Odoracle algorithm is really simple. The first step is to build list of all numbers between 0 and 999999 with all different digits. Then for every input line the program tries to find the smallest possible entry from the lookup list. ++ What kind of tricks did odoracle use to minimize code length? Mainly C shortcuts, one-letter variables and minimum blanks. In C is possible to write quite condensed statements. It's really amazing how many (unnecessary) spaces are there :)) ++ Here's what I hated (and loved) about this POTM's scoring: I cant's say I hated, but rather I didn't like the rule about code length. If you plan some other POTMs with the same rule, please tell us now - to start writing some script for "code compacting". Paradoxically, one of the things I liked was the same rule about code length. It reminded me of the past days and my (at the time) new HP41CV. It has a little more than 2KB memory, and every program was tightened to the maximum. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm starting (with two partners) a new company. Fun? Everything which is not part of the job. Even programming, like POTM :) Secrets are mine and only mine :) Ljupco Taseski Trilus d.o.o., Ljubljana SI-1000, Slovenija =================================================================