RESET Program entry descriptions (continued) positions 14-40 ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- -()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()- ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- ============== 14 ====================== QuaSimOdo ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS QuaSimOdo 1879997 389 358 31 75 Chris Hendrie ================= QuaSimOdo was submitted by Chris Hendrie at cihendri@uwaterloo.ca ================= ++ Please summarize the algorithm used by QuaSimOdo QuaSimOdo first computes for each subset of {0,...,9} the latest offset to the necessary reset point, given only those digits for the trip-meter and odometer suffix (hard to explain). This takes 1024 x 10 steps, but is relatively quick. For each input number, it can then simply pick odometer digits from left to right, verifying that the latest possible reset point comes after the given input. This takes at most 6 x 10 steps, and so is very fast. ++ What kind of tricks did QuaSimOdo use to minimize code length? Everything I could think of. One #define, argc (aka. 'm') as a variable, ?: wherever possible, etc. etc. ++ Here's what I hated (and loved) about this POTM's scoring: I liked the combo of run time and code length. Looks to me like code-length was the dominant factor, which I find a tad disappointing. I would perhaps have made run time twice or three times as important. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a 3rd-year Computer Science undergraduate at the University of Waterloo. I haven't found an interesting job yet. For fun, I juggle. Innermost secret: I'm an arrogant young-un who chafes at losing to more experienced hackers. How about a game-playing POTM? ================================================================= ============== 15 ====================== TheFinger ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS TheFinger 1879997 402 314 88 84 =Neil Weinstock ================= TheFinger was submitted by Neil Weinstock at nsw@ariel.com ================= ++ Please summarize the algorithm used by TheFinger First, if the input number was >= 987532, I set it to 0, because it would roll over, so same difference. For each number fetched, I called a recursive function that worked one digit at a time, from left to right. For each digit, I do this: if (this digit is not "used") if (this is the rightmost (ones) digit) figure out trip odometer value from available digits if this solution works, print and return all the way up else recurse, next digit to the right increment digit That's basically it. There's plenty of optimization, naturally. ++ What kind of tricks did TheFinger use to minimize code length? Much was algorithmic. Other than that, my favorite little tricks were: 1) Where possible, embed assignments into other statements, to avoid the need for brackets. My favorite spot was at the end of an arg list for a function call. Example: printf("%d %d\n",v-t,v,h=0); 2) Perl-like constructs to eliminate an if(). Example: v-t= t, then it is possible to find a solution (in particular, press reset at p - t) using the value under consideration for p[j], and p[j] is fixed at its current value. If not, other values of p[j] are considered until one is found for which a solution exists. When values for all six digits of p have been found, the answer is displayed: Reset is hit at p - t (where t is the smallest number made from the digits not in p). ++ What kind of tricks did reset use to minimize code length? Short variable names. Maintained bit map of used digits instead of using an array of flags and thus used less code for setting bits and initializing the list. Removed all excess blanks, tabs, and newlines. ++ Here's what I hated (and loved) about this POTM's scoring: I didn't like not knowing what the tiebreaker scores were. I hated the "smallest source code size" scoring. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent; Holmdel; Currently working on a storage technology product; Sing, act, play chess, etc.; That's for me to know...; None at the moment. ================================================================= ============== 17 ====================== brauciens ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS brauciens 1879997 412 344 68 47 Krists Boitmanis ================= brauciens was submitted by Krists Boitmanis at acad.latnet.lv!ugale@kcig2.att.att.com ================= ++ Please summarize the algorithm used by brauciens Array as follows: [1|2|3|4|5|6!7|8|9|10] First 6 - main odometer (D) Last 4 - RESET odometer with digits in reverse oder (R) Start at S[10]={9,8,7,6,5,4,3,2,1,0} After some rotations of digits: for (i=0;i<6;i++) { k=S[9]; for (j=9;j>i;j--) S[j]=S[j-1]; S[i]=k; for (j=9;j>i;j--) /# making of D and R out of array #/ if (D-R>[given number of miles]) break; else {k=S[j];S[j]=S[i];S[i]=k} } everything is ready for output. ++ What kind of tricks did brauciens use to minimize code length? Efficiency of algorithm allways does the job. ++ Here's what I hated (and loved) about this POTM's scoring: Lots of thanks to Fred for this overcrowded POTM! Everything was great! More people, more enjoyment. Congratulations to WINNERS!!! ++ COMPANY? LOCATION? DO FOR FUN? Last year at Ugale Secondary School (high school). Ugale is 40km from port Ventspils in LATVIA. Programming, basketball. ================================================================= ============== 18 ====================== too_many_miles ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS too_many_miles 1879997 413 324 89 112 Kurt VandenBranden ================= too_many_miles was submitted by Kurt VandenBranden at KVD2@bipsy.se.bel.alcatel.be ================= ++ Please summarize the algorithm used by too_many_miles combinatorial (sorry, but I can't explain any better, it would take a few pages) ++ What kind of tricks did too_many_miles use to minimize code length? Read every line of code 20 times, and check if it can't be skipped or included in another statement. Use the same variable if possible for different purposes. ++ Here's what I hated (and loved) about this POTM's scoring: It's fun for once, but I wouldn't like to do this another time. I worked a few hours on the base algorithm, and then the following weeks, I was busy making it smaller and smaller and smaller and smaller... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a software engineer at Alcatel Bell in Belgium. I read SF, I juggle, I compete in POTM. I would like a POTM that doesn't depend on the speed of the language you are using. The last 2 POTM's were very much about speed. It would be nice to have a POTM that depends on the algorithm you write, where it doesn't make a difference if you implement it in C, PERL, JAVA or even shel. (But I don't have any ideas for such a POTM) ================================================================= ============== 19 ====================== odomontade ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odomontade 1879997 421 300 121 65 D.McIlroy S.Dorward ================= odomontade was submitted by D.McIlroy S.Dorward at doug@research.bell-labs.com ================= /* Odomontade, by Doug McIlroy and Sean Dorward - programmers for fun and profit in computer science research, Bell Labs, Murray Hill, NJ. 300 bytes when reduced to blank-free 80-character lines */ int f=1023, l, m, x[1024], t[90000]; main(i, j, k) { g(4,0,0,0); g(6,f=0,0,0); for(f = fopen(1[(int*)j], "r"); i = fscanf(f, "%d", &l) > 0; vprintf("%d %d\n", t+j%m)) for(j=m; i t[k = i+j>>2<<1]? i = k+2 :(j = k); } g(n, v, z, d){ if(n) for( ; d<10; d++) z&1< l? t[m++] = l = n, t[m++] = v :0 ; } /* The method is to generate all possible answers - a table of final odometer readings and reset values - then look up the answers by binary search on reset value. Why precompute answers for 10!/4!=151,200 different mileages, when we will only be asked 1000? Because we don't know a good way to find the next achievable final odometer reading. The odometer may have to pass as many as 246 all-digits-different mileages before reaching an achievable one. (Only 42171 are achievable.) Thus a fiendish potm master could set 1000 problems that caused us to consider 247,000 different mileages. Betting that the potm master is not benevolent, we arranged for our run time not to depend on his problems. (This was a delicious speculation - how many other entries would take several times as long per problem for 10 times as many problems in the finals vs the preliminaries, while our time scarcely increased?) g(n,v,z,d) generates in lexicographic order permutations of digits 0..9 taken n at a time. d is a candidate for leading digit. v is numeric value of string of decimal digits. z is a bit mask giving the set of digits in v. The loop in g tries digits in increasing order, checks (by testing z&1< l) { t[m++]=l=n; t[m++]=v; } m is the table index. v is the final mileage. l is the previous final mileage. n is the reset mileage. LOW CUNNING TO SAVE CODE Table-update code is executed in g at all recursion levels, not just the final level where it's needed. In the first phase, this makes entries in table cells that will never be used. In the second phase, the code to guard against unreachable final mileages happens also to guard against updates at other levels of recursion. Vprintf is supposed to be used in connection with va_args to index arguments one at a time in a printf-style argument list. The misuse here to print two values from only one printf argument happens to work on Suns. That argument, t+j%m, also handles odometer wraparound. Tricks to save or shorten declarations omit header files use old-style function definitions reuse variables eschew non-int variables; mistype non-int as int use parameters, not local variables Because table t has two-word entries, the binary search indexes the low and high pointers, i and j, by two. i is initialized not to 0 but to 1 (the return from an unrelated test!), but this off-by-one error washes out when i+j is divided by 4 in the binary search. Savor the benefits of addressing argv[1] thus: 1[(int*)j]. Also the multiple uses of f flag to distinguish first from second phase (f?) mask for doing set complement (x[z^f]) test-free way to set argument of g conditionally (f&d) stdio file handle (f=fopen(...)) Plus all the usual coding tricks: embedding assignments in funny places, like argument lists, subscripts, and for statements, sometimes to avoid semicolons, sometimes to grab available values. using comma expressions to avoid {} brackets. using conditional expressions instead of if: || for 1-way; ?: for 2-way. For example, binary search becomes a "one-liner": for(j=m; i t[k = i+j>>2<<1]? i = k+2 :(j = k); */ ================================================================= ============== 20 ====================== The_first_try ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS The_first_try 1879997 438 394 44 125 Rolandas Gricius ================= The_first_try was submitted by Rolandas Gricius at lanteka.lt!rolandas@caig1.att.att.com ================= ++ Please summarize the algorithm used by The_first_try That's simple: take as basis miles entered, then calculate miles at the end, and then - miles travelled, increasing every digit while - <= . ++ What kind of tricks did The_first_try use to minimize code length? Almost none. Standard ones are - one letter variable names, no variable types in function declarations, freopen(..., stdin), you know, they are standard ones. ++ Here's what I hated (and loved) about this POTM's scoring: Very difficult to predict impact of speed differences between my and test machines, complicated by different test (100 entries) and actual (1000 entries) runs. (I hated it, of course). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? UAB "Lanteka", Klaipeda, Lithuania. We are running three person ISP, I'm the main UNIX administrator, programmer, consultant for leased lines installation, etc. Secret? I almost hate computers sometimes. POTM ideas? I have some. But not now :) ================================================================= ============== 21 ====================== eyes-on-the-road ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS eyes-on-the-road 1879997 443 331 112 87 Clive Dawson ================= eyes-on-the-road was submitted by Clive Dawson at Clive.Dawson@amd.com ================= ++ Please summarize the algorithm used by eyes-on-the-road The basic algorithm was simple: Using the starting mileage (m), compute the next possible mileage that consists of unique digits (x). Use the 4 leftover digits for the trip odometer (t). Now check whether x-t >= m. If so, this is a valid solution. Otherwise, go back and compute the next higher value of x. I used a refinement to this algorithm which speeded it up considerably: Solve the problem by assuming that the rightmost n digits of both odometers don't exist, for n decreasing from 3 to 0. This allows the more significant digits to be determined more quickly, cutting down on the number of times we need to iterate in the basic loop. Another significant speedup was obtained by using a precomputed array of powers of 10. This allowed much faster extraction of individual digits. The alternate approach of working with individual digits to begin with seemed to be a losing proposition, since you would then have to worry about doing your own arithmetic. (But given the vastly better performance of the winners, I'm beginning to have second thoughts about this!) Finally, I'm guessing that most everybody realized that you didn't have to worry about wrap-around on the odometer. This was taken care of by just making sure that your answer was printed modulo 1000000. ++ What kind of tricks did eyes-on-the-road use to minimize code length? Nothing particularly spectacular. It was just a matter of trying various styles of loops and if statements to see which would be shorter. Of course you want to take maximum advantage of compound statements, and creative use of the initialization, test, and increment portions of 'for' loops. At one point I switched to gcc, since it allows end of line characters in literal strings. I tried to make the ends of lines coincide with the places where a blank was required. ++ Here's what I hated (and loved) about this POTM's scoring: I didn't like the fact that we were left in the dark regarding specific scores. Certainly knowing that somebody had succeeded in one third the time, or had a program which was half as long would have motivated me to try harder. I think knowing more about what we were up against would have contributed to an overall improvement in the quality of the submissions. Another interesting aspect was that the tradeoffs made between execution time and program length depended on the speed of your computer, not mine. This wasn't bad or good; just interesting. One last bothersome aspect of this POTM was that since we didn't know the contents of the input file or how it was generated, it was hard to tune the algorithm. If you had told us that the test file would consist of 1000 random numbers between 0 and 999999, my program might have been very different from one designed to perform best on the "worst cases" which might have been specially chosen. ================================================================= ============== 22 ====================== tracks ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS tracks 1879997 454 372 82 131 =Franz Korntner ================= tracks was submitted by Franz Korntner at korntner@xs4all.nl ================= ++ Please summarize the algorithm used by tracks The algorithm is generally described as: Calculate an array containing 4 digit numbers where the digits are in ascending order. The array in indexed by bitmapping ie. the number 2456 has an index of 1<<2|1<<4|1<<5|1<<6. Then for all 1 million 6 digit numbers, calculate the bitmap (as described above) and find the matching 4 digit number in such a way that the OR'ing of both bitmasks result in all 10 bit positions being set. If a number combination has been found, then the 6 digit number will represent the final milage and subtracting the 4 digit number from the 6 digit number will represent the starting milage. Given a certain starting milage, it is sometimes wiser to wait a bit longer before pressing the reset to get a better end position. To catch this, the found starting milages must be in ascending order for them to be accepted/processed. This operation will create a list of starting positions and 'trip lengths' where the starting positions are in ascending order. The list will be 42171 combinations long. Finally for each number in the input list will be searched using a binary search method, displaying the milage when the reset button should be pressed, and the milage to wait before the result is achieved. ++ What kind of tricks did tracks use to minimize code length? Put all variables in registers for speed, and use a macro for the 10 used for loops. ++ Here's what I hated (and loved) about this POTM's scoring: I hated not knowing the scores of the other contestants, because it gives no indication on how well the entry actually is, it just tells you that all solutions are correct, nothing else. If I knew that first place was an entry 140 characters smaller than my 372 character entry, I would have taken a very different approach and not concentrate on speed issues. ++ COMPANY? ICT Netherlands. (www.ict.nl) which is a dutch contracting company LOCATION? Holland JOB? Contractor, specialized in low-level concepts ie. OS, compiler, debugger, library, encryption, compression, TCP/IP, device drivers, parallel processors. DO FOR FUN? POTM INNERMOST SECRET? Well, actually I --CENSORED-- about it. ================================================================= ============== 23 ====================== JustOnce ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS JustOnce 1879997 475 439 36 23 Bob Lied ================= JustOnce was submitted by Bob Lied at lied@lucent.com ================= ++ Please summarize the algorithm used by JustOnce Choose digits beginning from the most significant. As each digit is chosen, form the largest possible number that will complete the odometer, and the smallest possible number that will fill the trip meter. Then check that the constraint that the chosen digit will create an odometer reading in range: InitValue + TripMeter < Odometer + BiggestPossible Continue to choose the next smallest available digit until the constraint is satisfied. The weak part of this algorithm appears to be forming the smallest and largest numbers, which were the most expensive parts both in program size and execution speed. ++ What kind of tricks did JustOnce use to minimize code length? Unreadability -- no white space, single-character variables, reuse of variables, no functions Side effects -- ++/--, comma operator, embedded assignment, coincidental calculation of values needed later Control flow -- only while loops, goto Correctness proof -- no bounds checking on loops because they were known to terminate, elimination of special cases ++ Here's what I hated (and loved) about this POTM's scoring: Never quite knowing whether speed or size could make a difference. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? COMPANY: Lucent Technologies LOCATION: Naperville, Illinois, USA JOB: software dilettante FUN: basketball, classical guitar SECRET: haven't produced a line of production code in three years ================================================================= ============== 24 ====================== rollback ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS rollback 1879997 475 325 150 114 Warren Montgomery ================= rollback was submitted by Warren Montgomery at warren@psp.ih.lucent.com ================= ++ Please summarize the algorithm used by rollback Brute force, try each odometer reading starting with the given mileage looking for a solution and stopping at the first one. 3 tables were built in advance to speed things up: A mapping from 3 digits to a bit code (sum of 2^digit for each digit present) for each 3 digit number with unique digits, an inverse mapping from bit codes to lowest 4 digit number with remaining 4 digits for all bit codes with 6 bits on, and a table giving the next higher 3 digit number with unique digits for each one, allowing many impossible numbers to be skipped. ++ What kind of tricks did rollback use to minimize code length? Abusive (typeless) programming, comma expressions, ? expressions, and a #define for a repeated loop. ++ Here's what I hated (and loved) about this POTM's scoring: Combination of time and size was nice. Standings should have either given both time and size, or been based on the same number of numbers as the finals. The quirks of the POTM test machine (e.g. lack of hardware multiply/divide, odd cache effects, no optimization) make it very difficult to predict the space/time tradeoff without seeing it perform under actual conditions. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work for Lucent/Bell-Labs in Naperville Illinois on Intelligent Network Architecture. I enjoy puzzles, and POTM is a pretty good one. ================================================================= ============== 25 ====================== odododo ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odododo 1879997 501 412 89 86 Bob Ashenfelter odododo was submitted by Bob Ashenfelter at ash@att.com ================= ++ Please summarize the algorithm used by odododo The digits of the final odometer reading are computed one at a time starting with the most significant which is initially set to the corresponding digit of the starting odometer reading. The remaining digits are sorted into the remaining odometer digits, highest to the left, and the last four smallest digits are sorted into the trip odometer, highest to the right. The result is the final readings when the reset is pushed at the very latest point that leaves the initial value in the most significant digit. Compute the mileage at reset by subtracting the trip odometer from the total odometer. If this is at or beyond the starting value, go on to the next digit. If not then the initial digit cannot possibly be right. Increment it (mod 10) and try again. Subsequent digits are initialized to either the corresponding digit of the starting odometer reading or, if it had been necessary to increment ANY previous digit, to 0. (It is easier to just set all subsequent digits to 0, but the cost in extra execution time is more than the savings of 8 characters.) Then the remaining digits are sorted and the reset is tested as above. This continues until all six odometer digits are determined and then the answer is printed. ++ What kind of tricks did odododo use to minimize code length? These are all pretty obvious: * Use one-character variable names. * Use as few variables as possible, reusing them wherever possible. * Use pointer notation instead of array notation wherever it is more concise. * Use "," to terminate statements (except the last) in a block instead of ";" and then remove the "{}". * Move statements from the body of "for" loops into unused control expressions and save the ";"s. * Remove all extraneous white space. * Use "#define" for repeated character sequences. (I could only use it once, for "for (", and it saved only a couple of characters.) * Use a new-line for unavoidable white space if it keeps line lengths within the 80-character limit. Perhaps my most creative trick was to use a single array for both the final odometer digits and the trip odometer digits with the trip odometer digits reversed so only a single sort was needed for both. And then I padded the array with two additional digits which were never changed from their default initializations of 0. These extended the trip odometer to six digits and simplified the subtraction to obtain the reset mileage. Another cute trick was to reuse the "argc" and "argv" arguments of main(). Of course I called them "c" and "v". Even though the initial value of "c" was not used and it was not declared, it defaults to "int" and was sub- sequently used as such. When I reused "v" as a pointer to an array of integers, the compiler complained bitterly. So I lied to the compiler and declared it "int*v;" instead of "char**v;". Not only was the compiler deceived (not even a whimper), but I shortened the code by two characters as well! ++ Here's what I hated (and loved) about this POTM's scoring: If you, or anyone else, expect me to complain about the encouragement of bad programming style, sorry..., I have no problem with that. The following is neither love nor hate--just a comment. The score for time was too small in comparison with the score for size. At the time this was determined you probably expected them to be comparable, but you really had no idea how efficient the best programs would be. Perhaps you should have left this to be determined later, say by increasing the number of input values until the winning program scored equally for both time and size. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T ... until they sell us out--I'm in Submarine Systems. Holmdel, N.J., U.S.A. Circuit design. Bicycling, sailing, grow orchids, travel. No way... You could publish the winning entry of this POTM as the problem for the next POTM. First one to figure out what it does is the winner. ================================================================= ============== 26 ====================== outofgas ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS outofgas 1879997 508 331 177 41 Matthias Ruhl ================= outofgas was submitted by Matthias Ruhl at ruhl@informatik.uni-freiburg.de ================= ++ Please summarize the algorithm used by outofgas The program starts with the current meter and iteratevly computes the next meter setting with 6 different digits. If the smallest number that can be built from the four remaining digits is smaller than the difference of the this and the original meter setting, we are done. Otherwise continue. The tricky part is obviously to determine the next meter setting where all six digits are different. This is done by going from the highest value position to lowest value position and checking each time whether the digit at that position already occurred (to the left of it). If it has, then a) zero all digits to its right b) repeatedly increase the digit by one until it 1. hasn't occurred before. Then we continue with the next position. 2. it is increased to 10. In this case, the overflow must be propagated to the next higher position, where the loop begins again. To avoid handling the special case where the meter turns from 999999 to 000000, all meter settings greater than 987531 (=987654-123) are mapped to 000000 at the beginning of the program. ++ What kind of tricks did outofgas use to minimize code length? Only 'garden variety' C-code shrinking (reusing variables, shortening expressions, etc.) - nothing really problem specific. And not a single '#define' :) ++ Here's what I hated (and loved) about this POTM's scoring: The scoring system itself (length+time) was, well, interesting :) But I think it would have been even more fun if the actual scores had been distributed with the ranklist. The scoring method may also put people who have access to a Sparcstation at a slight advantage, since the tradeoffs between speed and (code) length are often quite counter-intuitive and also very machine-dependent. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm an undergraduate student majoring in Maths and CS at the University of Freiburg, Germany, and will be graduating in summer 1997. So hopefully I'll then have some more time to spend on a future POTM :) ================================================================= ============== 27 ====================== dodo ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS dodo 1879997 556 510 46 93 Jeroen Moelands ================= dodo was submitted by Jeroen Moelands at moelands@nlr.nl ================= ++ Please summarize the algorithm used by dodo I use arrays of 10 bits that tells which digits are already used as integer indices to two arrays. One array contains the trip odometer standing, which consists of the four lowest digits that are not used yet, lowest digit first. The other one contains the highest possible value that can be made with the unused digits. These arrays are filled first. To avoid the wrap-around stuff, if the odometer has a value higher than a certain maximum, I print the lowest milage possible. For other odometer standings, a simple backtracking algorithm is used that finds the minimal odometer value without much backtracking, using the two arrays. The algorithm creates the odometer number from left to right. If the entire number is found, it is printed. Otherwise, the lowest possible digit is 'added' to the odometer number "head"; if the resulting number 'plus' the highest possible "tail" to form 6 digits is greater than or equal to the given odometer standing 'plus' the lowest possible trip odometer standing, try to 'add' the next digit (the highest standing possible to create with the given "head" must be at least as high as the given standing plus the lowest possible trip). If no digits are possible, backtrack. In this way the odometer standing is found without much backtracking. ++ What kind of tricks did dodo use to minimize code length? Tricks? Just spent a *lot* of time. ++ Here's what I hated (and loved) about this POTM's scoring: Creating a fast program is a lot more fun than creating a small one. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I work as a Software Engineer at the National Aerospace Laboratory (NLR) in Amsterdam, Holland. ================================================================= ============== 28 ====================== Close_Enough ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Close_Enough 1879997 557 354 203 53 Vance Heron Sorry ... no description available for Close_Enough ================================================================= ============== 29 ====================== Hoovey ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Hoovey 1879997 562 312 250 128 A.Halverson J.Halverson ================= Hoovey was submitted by A.Halverson J.Halverson at alanh@microsoft.com ================= ++ Please summarize the algorithm used by Hoovey We used a 6-element array of integers to represent the digits of the odometer. To determine uniqueness, we employed a bit-field in which bits were set if a digit was used in the main odometer. We proceeded left to right (most significant to least significant digit). By right-shifting 1 "current digit" times, we arrived at a unique bit in the bit field. If the bit was already set, increment the current digit and zero out all less sig digits. As soon as you found a digit not already set in the bitfield, set it and move on to the next digit. If you roll a digit (9 -> 0), you have to remove the previous digit's bit from the bitfield and increment it. Once all six digits were found to be unique, it was trivial to construct the trip odometer by testing bits in the bitfield, LSB to MSB. If bit j wasn't set, multiply the trip odometer by 10 and add j. This method guaranteed the smallest possible trip odometer. Finally, just subtract main odometer from trip odometer and test against input odometer reading, looping back if the test failed. ++ What kind of tricks did Hoovey use to minimize code length? We used "#define W while(" - every loop in our program was a variant of the while loop. Also, the comma sequencing operator came in very handy ("f=x,y=j;" instead of "{f=x;y=j;}"). Another good one - define argv as int*argv instead of char**argv. This works because sizeof(int)==sizeof(char*). No #include files. No functions other than main(). Of course, getting rid of that pesky whitespace helped as well ... %^) ++ Here's what I hated (and loved) about this POTM's scoring: Having code size share importance with speed of execution is a bummer. Maybe if speed was worth 2/3 and code size 1/3 in the second tiebreaker. Maybe I'm just complaining because I don't have enough experience writing unreadable C code ... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company: Microsoft Corporation Location: Redmond, WA Job: Quality assurance for a "popular database product" Fun: Music - play, sing, listen Secrets: You can't have any when you're married ... %^) ================================================================= ============== 30 ====================== gdrula ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS gdrula 1879997 597 471 126 124 Catalin Drula ================= gdrula was submitted by Catalin Drula at gdrula@pcnet.pcnet.ro ================= ++ Please summarize the algorithm used by gdrula If "a" is the initial number, I considered all the numbers starting with "a" that have all the digits different. With the left 4 digits I formed the smallest number "c". If the difference between the current number and the initial number is less or equal than c, than the current number is the number we're looking for. That's all. ++ What kind of tricks did gdrula use to minimize code length? Not many.The usual C syntax + flags... ++ Here's what I hated (and loved) about this POTM's scoring: I think the code length has too much importance in the score: Wouldn't something like: 5*time+length have been better? I like that you send the weekly status and nobody knew the other contestants scores. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I learn at Bucharest High School of Computer Science. I live in Romania and I'm 15. Yes, I do it for fun. In future I think you should give more difficult problems. The algorithm should count more than some tricks to make the source shorter. If possible don't use the source length in the score. Thanks for what you do, ================================================================= ============== 31 ====================== shortcut ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS shortcut 1879997 614 327 287 58 Jan Venema ================= shortcut was submitted by Jan Venema at jvenema@lucent.com ================= ++ Please summarize the algorithm used by shortcut For each A1 on input: a) Start with A2 = A1. b) Check if all 6 digits in A2 are different. c) If different, then calculate B2 by using the remaining 4 digits. Check if B2 <= A2-A1 then print A2-B2, A2 and continue with next A1 input. d) Else, increment A2 with 10^n (depending on digits used) and restart at b). ++ What kind of tricks did shortcut use to minimize code length? - Roll over is prevented by starting A2 as 0 when A1 > 987531. - Use gcc compiler since it is forgiving and makes correct assumptions when C input is incomplete (e.g.: no #includes used, direct parameter access from main(), no 'int' declarations needed, any pointer can be used for fopen() and fscanf() file parameter). - Use a recursive algorithm: 6 deep recursion level, one for each digit in A2. - Take advantage of priority ordering where possible, so fewer '()' - I used a small program to reduce variable name length, remove spaces etc. ++ Here's what I hated (and loved) about this POTM's scoring: To solve the POTM it was inevitable to write a second program that ensures smallest possible code size. Some hacking was required: how are parameters passed to main() program, and to what extend can one fool passing of parameters to library functions. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Systems Engineering, Lucent Technologies in Huizen, the Netherlands. jvenema@lucent.com ================================================================= ============== 32 ====================== turtle ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS turtle 1879997 659 392 267 38 Didier Barzin Sorry ... no description available for turtle ================================================================= ============== 33 ====================== odor ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS odor 1879997 667 313 354 98 Edwin Berlin Sorry ... no description available for odor ================================================================= ============== 34 ====================== What_A_Trip ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS What_A_Trip 1879997 668 429 239 25 Robert Morrison Sorry ... no description available for What_A_Trip ================================================================= ============== 35 ====================== bitsrock ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS bitsrock 1879997 669 551 118 116 Pete Demoreuille ================= bitsrock was submitted by Pete Demoreuille at pbd@gate.cybernex.net ================= ++ Please summarize the algorithm used by bitsrock precalculate all valid 6 digit numbers and the digits used by them. also precalculate the all the lowest 4 digit numbers and the digits that they do not use. then do a binary seach in the 6 digit numbers for the first number greater than the given. while the differnece of the original number and the 6 digit number in the refrence place of the 4 digit number that does not use the digits in the 6 is less than the number of miles moved, try again. else print the proper numbers. ++ What kind of tricks did bitsrock use to minimize code length? efficiency, no redundancy by way of #defines when it would help... ++ Here's what I hated (and loved) about this POTM's scoring. nothing. it was pretty fair for the problem. ================================================================= ============== 36 ====================== Porsche ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS Porsche 1879997 677 576 101 49 Michael Strauch ================= Porsche was submitted by Michael Strauch at strauch@metronet.de ================= ++ Please summarize the algorithm used by Porsche For every starting point [A], Porsche does the following: a) Increase [A] until you find a point where all 6 digits are different. Lets call this number [A2]. b) Let [B] be the smallest number containing the 4 remaining digits. c) If ([A2]-[A]) MOD 10^6 >= [B], [A2] is the earliest point at which ten different digits appear on the odometers, and ([A2]-[B]) MOD 10^6 is the point where to press the reset button. d) If ([A2]-[A]) MOD 10^6 < [B], replace [A] by [A2] and go back to step a). How I tried to get the program fast ----------------------------------- I used a lot of small tricks to increase the speed of the program. Here are the main ideas: - "Porsche" stores the mileages [A] as a vector of 6 Digits "int Dig[6]"; when I need the mileages value, I use the expression (((((Dig[5]*10+Dig[4])*10+Dig[3])*10+Dig[2])*10+Dig[1])*10+Dig[0]) - Increasing of [A] is not done "one by one"; instead, "Porsche" increases the leftmost digit appearing twice first. - Porsche adds "123" to the starting point before running the main calculation loop, because [B] cannot be smaller than that. - Some "register" variables are declared (GCC then does some register optimization, even if the optimizer is not used) I made a second implementation of Porsche, storing [A] as an "int", which was more than 100 bytes shorter than my entry, but it needed approx. 4 seconds more for 1000 numbers. ++ What kind of tricks did Porsche use to minimize code length? I used an awk script to "compress" my program to a real short one: - all comments, every empty line and all unneccessary whitespaces are stripped out of the text - the lines are concatenated if they don't exceed 80 characters - the variable and function names are replaced by short names of one letter ++ Here's what I hated (and loved) about this POTM's scoring: - I think "code length" is overweighted by this POTM's scoring; letting the speed score be "seconds*1000" instead of "seconds*100" would be a much more interesting challenge (in my opinion), because you have much more room for inventing a real good algorithm. - On the other hand, I never saw as many programmers as ever here at this contest - the problem makes it very easy to build a correct entry with less than 1000 bytes, and the scoring gives them all a chance to win the contest not by inventing a complicated mathematical solution, but by optimizing the code for shortness. I think, this is a very good point for this kind of scoring. ================================================================= ============== 37 ====================== vanb ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS vanb 1879997 678 384 294 13 David Van_Brackle Sorry ... no description available for vanb ================================================================= ============== 38 ====================== thewinner ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS thewinner 1879997 694 403 291 70 Ravi Nemlekar ================= thewinner was submitted by Ravi Nemlekar at ravindra@airmail.hobl.lucent.com ================= ++ Please summarize the algorithm used by thewinner Read the input number. Keep incrementing the number till all the digits in it were unique. The 4 digits not in the number are the "trip" miles. If the number - trip < input, goto incrementing. ++ What kind of tricks did thewinner use to minimize code length? 1. Removed unrequired code (like error checks, redundant code) 2. Improved the algorithm. ++ Here's what I hated (and loved) about this POTM's scoring: Loved: Making the code faster Hated: Making the code smaller. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company: Lucent Technologies, Holmdel, New Jersey Do for fun: Meet people, action Movies, music. Innermost secret: Motivated to do something. POTM ideas: Thinking... ================================================================= ============== 39 ====================== 1000000 ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS 1000000 1879997 727 561 166 105 David Wales ================= 1000000 was submitted by David Wales at david.wales@waii.com ================= ++ Please summarize the algorithm used by 1000000 In a loop : read the number in, setting up a lookup of integers used, then, in an inner loop, check that we have a solution, else, recursively, keep incrementing the rightmost number, doing sensible things with the loookup on the way, until the next candidate is found with non repeated integers. Checking for a solution is to use the remaining four numbers in the lookup, in order. ++ What kind of tricks did 1000000 use to minimize code length? Replace common code with function calls so long as run time didn't increase too much. Replace code with macros, remove all blank space ( except end of lines ). Reuse variables, make all variables global, use function parameters defaulting to int. Lots of pointer stuff. > ++ Here's what I hated (and loved) about this POTM's scoring: This became an obfuscated C contest. On my machine run time, for 1000 problems, is far less than code length so squashing code became a priority. Maybe should have deducted points based on some measure of unreadability? Alternatively could have issued a beautifier through which all code would be crunched and do an ls -l on its result. Maybe, if it's to be an obfuscated c contest, add a score measuring the number of unique symbols in the code - the more the worse!? ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Western Geophysical, Bedford UK. Software bloke. ================================================================= ============== 40 ====================== trees ============= ================================================================= ENTRY SCORE1 SCORE2 = CHARS+HSEC AGE PROGRAMMERS trees 1879997 730 436 294 37 Dave Lynch ================= trees was submitted by Dave Lynch at dflynch@att.com ================= ++ Please summarize the algorithm used by trees Increment the odometer until all digits are different. Permute the remaining 4 digits to get the trip odometer. If I haven't traveled this far, go another mile and repeat. ++ What kind of tricks did trees use to minimize code length? Just the obvious. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T Holmdel, NJ Write software to design data networks. Stay away from work. Secret.