Positions 41-80

Note - program listings may not print correctly due to HTML conflicts.
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 */
#include

main(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(j201345). 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
=================================================================












Make your own free website on Tripod.com