Entry Summaries

The attached mail is the collection of write-ups I received. As usual they are mostly unedited (only personal POTM-master insults were removed). Write-ups are provided in order of finish (more or less).

The attached is LONG mail.  The profiles that were returned are
presented below .... in order of finish (so you can read the tidbits
before you get tired).  If you sent in your form after 7:00 PM
on Wednesday - it wasn't included ... I apologize.  A shar file
with the top ten C programs is on the way ... watch for it!

=Fred
********************************************************************

============================================================
=== 1=> ==== odomatic ==== Vincent Goffin ==== mozart!vjg =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
1=>     odomatic    1000         0.89*     405    Oct 27 10:26        494*

===========================
PROGRAM: odomatic    FROM: Vincent Goffin    AT: mozart!vjg
APPROACH:
I went through 19 versions, and I started with a numerical approach that bumped
the odometer(s) just enough to remove the leading repeated digits. This
typically introduces new repeated digits somewhere else, and the process
continues until convergence (except for impossible cases).
Impossible cases had to be screened out by hand and that wasn't satisfying.
In the end, trying to speed up the numerical approach I found a hybrid method
where a symbolic "accelerator" routine took care of the last 4 digits AND
took care of the impossible cases. The speed jumped, the size fell and I
started counting my chicken.

WHAT DID YOU DO:
C's remarkable syntax can be packed tight; in addition, I converted all if
statements to ?: expressions, allowing them to be strung together with ',' and
avoiding braces. I also looked for ways around return and break statements.
Final touch: I delayed calculations to the point where it was clear that
they were needed, even if that meant doing them within the [] of an array indx.

COMMENTS, LESSONS?
It is a wonderful opportunity to focus on a small problem and try to reach
the bottom of it. You can't do that with real world problems and that's
what's frustrating.  For unrepentant reductionists, the POTM is a break!

WHAT, WHERE, AND WHY ARE YOU?
I'm in the BL0591120 (Softw. Tech. Center), because that's where I ended up.
It's the 2nd time I joined the POTM and it's great fun each time
(and now I get to catch up on everything, which is an even more fun!).

============================================================

=== 2=> ==== palith ==== Palith Balakrishnabati ==== toucan!pb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
2=>       palith    1000         1.61      413    Nov 1  16:13        574

===========================
PROGRAM: palith    FROM: Palith Balakrishnabati    AT: toucan!pb
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
              
 For each value of odo and tripodo, recursively generate the entire set
 of pairs of four digit numbers (abcd, efgh) such that: 1) all the digits
 a-h are distinct and 2) the differences abcd - efgh and odo - tripodo
 are congruent mod 10,000.  For each member of this set, use table
 lookup to find the two unused digits (say i and j) and consider the two
 six-digit numbers ijabcd and jiabcd.  Keep track of the smallest of
 numbers these encountered greater than odo, (mod a million); This will
 be the answer we seek.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?       
 To make it small, I used very ugly obfuscating techniques, such as
 "#define _ define", making local vars into params so I don't have to
 declare them, forcing bits of code to look similar for maximum macro
 compression.  Please do nottry this at home, kids.

LESSON: Very tough to speed-optimize for a particular machine type
 when you don't have a one of the beasts on hand for testing.

WHAT, WHERE, AND WHY ARE YOU?
 I am Palith Balakrishnabati, and my field is theoretical CAD/CAM.
 I am 32 years old, unmarried and a Scorpio.

============================================================

=== 3=> ==== qcd ==== Julius Collins ==== esun!jpc =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
3=>          qcd    1000         2.71      372*   Oct 31 22:09        643

===========================
 PROGRAM: qcd    FROM: Julius Collins    AT: esun!jpc
 WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	kind of a depth-first tree-search algorithm (but tree is not stored).
	a potential 6-digit answer, say 145268, is a leaf, with
		parents labeled 5268, then 268, 68, 8, and then the root.
	if a node, say 268, causes any digit duplication, then its
		children need not be examined.
	search whole tree (except as above) and save best answer.
	finds common no-solution cases (e.g. 123456, 9876) quickly --
		only checks 10 nodes.

 WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
	small:  tried every trick in the book; wrote some new chapters!
		used horrid macros, ignored proper datatypes

 COMMENTS, LESSONS?
	dont you have a real job?  i hope i still do!
	really i appreciate you running these...
		and hope i'm not so interested in the next one.
	really amazed how much my first tiny program could be shrunk.

 WHAT, WHERE, AND WHY ARE YOU?
	julius collins, HO (NJ8460?) 1E-423, esun!jpc
	math/comp.sci., software, puzzles, POTMs, no time for life anymore!

============================================================

=== 4=> ==== pumpkin ==== Steve Sommars ==== ihlpl!sesv =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
4=>      pumpkin    1000         1.81      615    Oct 16 16:16        796

===========================
PROGRAM: pumpkin    FROM: Steve Sommars    AT: ihlpl!sesv
APPROACH:
General approach was to start at current odometer 10K-ade,
construct all solutions (if any) in that 10K-ade.  Stop when
one is found, use smallest.  The no-solution cases are all of the
form: (Here x=A-B%10,000, symmetric about x=5000.
 x%10==0 || x < 25 || x%1000<3 || x%1000>997 ||abs(x-100)<3 ||abs(x-200)<2
(I kept hoping to find a shorter representation for this, but failed.)
****There should be a clever algoritm for this problem using
****perhaps combinatorics and number theory, couldn't find it though.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
The speed came naturally from the algorithm.  Making it small
was a pain.  Numerous ugly tricks were used.  I suspect I had
a small advantage because my host here is an Amdahl.  
The final code is fragile, non-portable.  

COMMENTS, LESSONS?	
Interesting problem.  The size part was a pain though.  I would
have preferred that the importance of size be decreased in overall score.

WHAT, WHERE, AND WHY ARE YOU?
Systems Engineering for NSD-5ESS applications.

============================================================

=== 5=> ==== igottagodad ==== Keith Vollherbst ==== mtqua!keithv =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
5=>  igottagodad    1000         2.02      597    Oct 30 23:55        799

===========================
PROGRAM: igottagodad    FROM: Keith Vollherbst    AT: mtqua!keithv
APPROACH: First test difference between meters to see if a solution is possible.
 If so, calculate a digit by digit difference between the last 4 digits
 of the meters (e.g., readings 123456 6543 produce differences of 6,9,1,3
 (123456-6543=116913)).  Then, recursively build the final meter readings by
 adding a digit at a time to a blank total odometer reading.  Possible digits in
 the trip reading are calculated from the digit diffs.  If the possible digit
 isn't already used, recursively add the next digit to the total reading;
 otherwise try a different digit in the total reading or return a failure
 indication if all have been tried.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
 Nothing fancy here -- mostly just trial and error.

COMMENTS, LESSONS? One lesson was that I may generally make too much of the
 "you can always trade space for time" adage.  I found my biggest improvements
 came from eliminating unnecessary code -- thereby reducing both time and space!
 I wonder how much waste is in our released products?
 As usual -- THANKS FRED!

WHAT, WHERE, AND WHY ARE YOU? I think anybody who entered who doesn't respond
 "Nerd" to this one is probably just kidding themselves!  My job is Key/PBX
 communication system software development for GBCS in Middletown.

============================================================

=== 6=> ==== rollon ==== Warren Montgomery ==== iexist!warren =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
6=>       rollon    1000         2.92      547    Oct 29 17:30        839

===========================
PROGRAM: rollon    FROM: Warren Montgomery    AT: iexist!warren
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?  scan the first 10,000
cases starting with the given reading looking for cases where the last
4 digits of the odometer and trip-meter were all distinct.  In
each case, report an immediate solution if the remaining digits match
the upper two digits of the odometer, else track the solution closest
to the original reading of the two possible.  If no solution in
first 10K is found, the closest combination found during the
search is reported or -1 for no solution.  Major insight was use of
bit code representation to represent numbers with unique
digits. (2^n set if digit n is present).

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?	Pre-computed tables
mapping 4 digits to a bit code and indicating which 4 digit combinations
were unique.  Abusive use of the pre-processor, table talk, and
minimal declarations saved lots of space

COMMENTS, LESSONS? Nice problem.  I was particularly impressed
that space and time were both significant, and nobody found a trivial
solution.  Brought back memories of systems programming in BASIC and FORTRAN

WHAT, WHERE, AND WHY ARE YOU? Someone whose other interests and
job have little to do with programming!

============================================================

=== 7=> ==== bighorn ==== Dennis Sanger ==== bighorn!drs =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
7=>      bighorn    1000         1.01      764    Oct 12 11:39        865

===========================
PROGRAM: bighorn    FROM: Dennis Sanger    AT: bighorn!drs
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
  First, I tried the obvious approach, adding miles until I hit a solution.
  Even with a few clever enhancements (e.g. incrementing by 9 miles at a
  time), this approach wasn't nearly speedy enough. My final entry
  constructs possible solutions (i.e. solutions with the appropriate
  difference between the odometer and the trip odometer) digit by digit
  until it manages to find one.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
  I obviously didn't do enough to make it small. To make it fast, the key
  is to be able to recognize problems with no solution rather than wasting
  time searching for nonexistent solutions. Another time-saving hint:
  if there exists no solution of the form "abxxxx", there won't be a solution
  of the form "baxxxx" either.

COMMENTS, LESSONS?
  What a great creative outlet for those of us working in software
  sweatshops! :-)

WHAT, WHERE, AND WHY ARE YOU?
  WHAT? Definity(TM) G3 switch product support  WHERE? Bell Labs in Denver
  WHY? ummmmm, I dunno....

============================================================

=== 8=> ==== odjjaz ==== Joost Zalmstra ==== intgp1!jzalmst =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
8=>       odjjaz    1000         4.13      560    Oct 22 05:48        973

===========================
PROGRAM: odjjaz    FROM: Joost Zalmstra    AT: intgp1!jzalmst
There are two interesting points I found during developing this program.
At first I started going from 'right' to 'left', i.e., I first made the
4 least significant digits of the total counter together with the trip
counter unique. The top two digits of the total counter could then be
chosen freely. The problem is that when you find a solution you do not yet
know if it is the shortest. Therefore I would have to try 5000+ situations
to be sure I had the shortest solution. When I found then the fastest solution
to date was 20 times faster than my solution I knew I would have to go from
left to right, but I could not find a way how to do it. Then a colleague
hinted on the way he was working his solution I got a brain waive. Although
my final solution was quit different from what he did, just a small hint
triggered my imagination.

Another interesting point was compacting. My first version was 764 bytes. I
was convinced that I was close to optimum. In the end I got more then 200
bytes off!!. So never conclude too fast that something is optimal!!

============================================================

=== 9=> ==== dbk_odo ==== Donald Knudsen ==== sirius!dbk =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
9=>      dbk_odo    1000         4.25      583    Oct 11 15:31       1008

===========================
PROGRAM: dbk_odo    FROM: Donald Knudsen    AT: sirius!dbk
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?

 First do straightforward brute force version, generate some
 trusted answers plus time benchmark.  Notice that 1) no solution
 if last digits of both odometers match and 2) solution guaranteed
 if last 8 digits all different.  Used space for time trade-off,
 i.e., precompute large array to avoid lots of computation in loops.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
 Tried to use only ints in inner loops.  Precompute arrays of masks.
 Eliminate boundary condition tests in loops by using double-length arrays.
 Use registers for variables in loops.

COMMENTS, LESSONS?
 C compilers tend to have bugs relating to register use.  Using compiler
 optimization can make a program not work!

WHAT, WHERE, AND WHY ARE YOU?
 I'm at MH.  Interested in puzzles (programming and other).

============================================================

=== 10> ==== osu_odo6 ==== David Jones ==== jonesd@kcgl1.eng.ohio-state.edu =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
10>     osu_odo6    1000         1.03      957    Oct 11 08:11       1060

===========================
PROGRAM: osu_odo6    FROM: David Jones    AT: jonesd@kcgl1.eng.ohio-state.edu
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
  The general solution is to first find all offsets which when added to the
  low 4 digits of each odometer result in 8 unique digits.  For each of these
  offsets, some multiple of 10,000 can be added to make the high 2 digits
  in the odometer unqiue from the other 8.  The answer is the lowest multiple
  plus offset found.  The trick to getting an answer fast is how fast you can
  test the 10,000 base offsets.  My algorithm incrementally builds a list of
  valid offsets incorporating succeedingly higher powers of 10.  This approach
  optimizes the scan by eliminating checks for ranges of offsets that would
  fail anyway (i.e. if digits 'nm' added to the low two digits of the odo-
  meters do not result in four unique digits, 'xynm' fails for all xy).

COMMENTS, LESSONS?
  I think the scoring system is way too skewed in favor of program size.
  Until it's changed, every month's problem degrades to the same problem.

WHAT, WHERE, AND WHY ARE YOU?
  I'm a systems programmer III at The Ohio State University.  I support
  networking and VMS systems for the college of Engineering.

============================================================

=== 11> ==== stab ==== Jim Porter ==== longs!jwp =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         stab    1000         4.23      866    Oct 28 15:43       1289

===========================
PROGRAM: stab    FROM: Jim Porter    AT: longs!jwp
 WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
 Initial approach was simple iteration of trip choosing top 2 digits of
 odom when other 8 were unique.  This gives a search with 10000 iterations
 (not so good).  Final solution involved determining the difference between
 odom/trip digits and setting (recursively) the bottom 4 digit values of
 odom from trip.  The trip digits were chosen by a depth first recursive
 search of possible digit values.  The final 2 odom digits were still
 determined when other were unique.  This was 4* faster with 100 test data.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
 Sleepless nights ... pulled hair ... uh, wait really-->make all variables
 and functions single character, #define common used terms, got rid of
 all indenting and extra spaces, used 'c' default arg type of int.
COMMENTS, LESSONS?
 I would have like to try search odom recursively. Search space is larger
 but digit allocation and deterministic trip digit assignment might have
 yielded a faster solution since a branch&bound could be used.
WHAT, WHERE, AND WHY ARE YOU?
 Work in GBCS on a PBX adjunct called CMS (c++ appl. running on 486/UNIX).
 I like puzzles.  This one sounded fun (Thanks Fred).  Also play racquetball.

============================================================

=== 12> ==== mile6 ==== Jim Hahn ==== cblph!jrh3 =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        mile6    1000         7.86      623    Oct 14 10:56       1409

===========================
PROGRAM: mile6    FROM: Jim Hahn    AT: cblph!jrh3
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Note the digits working from left to right.  When a duplicate appears, add
just enough to the current value to increment the duplicate digit.  As for
no-solution cases, the only special case for which I checked was the same
right-most digit in the two readings.  All other no-solution cases were
identified by two carries out of the left-most digit.  To even get a program
into the top entries, it had to be small; this tended to eliminate any of
the algorithms I had in mind to pre-calculate stuff to speed it up.  Instead
I had to focus on finding a simple algorithm.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
To make it small, I wrote a general purpose program, shrink, that shortens
variable names and replaces often used keywords with shorter #define symbols.
Thus I write & debug a legible program, but I submit a shrunken program.

COMMENTS, LESSONS?
I was amazed and impressed at the turn-around time when I submitted a new
version.  Solving these problems can be addictive, but certainly spawns
creative thinking.  Nevertheless, there came a point when I just had to stop!

WHAT, WHERE, AND WHY ARE YOU?
I'm in Columbus working on a product called StarRep(tm) PROES.  My interests
include optimization problems; hence this POTM problems struck a chord.

============================================================

=== 13> ==== odm_potm ==== John Berry ==== cdsdb1!jlb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     odm_potm    1000         5.22     1041    Oct 31 00:11       1563

===========================
... No form returned

============================================================

=== 14> ==== odie ==== Brian Davies ==== ihlpl!bdavies =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         odie    1000         4.31     1249    Oct 7  11:20       1680

===========================
... No form returned

============================================================

=== 15> ==== odor ==== David Roe ==== research!roe =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         odor    1000        10.59      664    Oct 1  21:32       1723

===========================
... No form returned

============================================================

=== 16> ==== krrOD ==== Ken Rodemann ==== qsun!krr =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        krrOD    1000         2.43     1827    Sep 28 20:59       2070

===========================
... No form returned

============================================================

=== 17> ==== mr.bill ==== Scott Kennedy ==== homxb!tsk =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>      mr.bill    1000         9.58     1212    Sep 28 14:26       2170

===========================
... No form returned

============================================================

=== 18> ==== odyssey ==== Debbie Brown ==== homxb!dwb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>      odyssey    1000        20.50      733    Oct 7  16:01       2783

===========================
... No form returned

============================================================

=== 19> ==== hold_da_fort ==== Ken Haruta ==== mhcnet!kh =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==> hold_da_fort    1000        13.78     1475    Oct 21 14:40       2853

===========================
 PROGRAM: hold_da_fort    FROM: Ken Haruta    AT: mhcnet!kh
 WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
  A. If the least significant digits of the OD (odometer) and TR (trip d)
     are the same, there is no solution.	
  B. Stuff the last 4 digits of OD and TR starting from the top into n array
     of 0 - 9 and if there is a duplication, bump n miles on OD and TR; n
     depends on which digits are duplicated.
  C. When the 8 digits are all different, see if the top 2 digits of D are
     different from the 8 digits. If so, that's the solution. If not, hange
     the top 2 till I find the
     smallest N to satisfy the condition, store N, etc. and keep going.
     After the sum of all N's >= 9999, the smallest M is the solution.

 WHAT DID YOU DO TO MAKE THE THING SMALL?
  Removed all the white spaces except in the statement number field.

 COMMENTS, LESSONS?
  I can't believe where you find time to run POTM, Fred. This is my first
  entry, and had a lot of fun. Keep up the great job!
  By the way, the weekly leaderboard is a must. Can't do without it.

 WHAT, WHERE, AND WHY ARE YOU?
  B.A. from Colby College, Waterville, ME, Ph.D. in physics from .I.T. ('63)
  I'm crazy about tennis - but someone please tell me how to improve.

============================================================

=== 20> ==== bigrun ==== Dave Lynch ==== esun!dfl =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       bigrun    1000        23.91      849    Oct 29 14:25       3240

===========================
PROGRAM: bigrun    FROM: Dave Lynch    AT: esun!dfl
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
If the one's digits were the same, I printed -1.  Otherwise, I rolled the two
odometers until all the digits were different.  First, I would roll the
ten-thousands, then the thousands, then the hundreds, etc.  For example, if
given 575213, 3456, my first step would be 576000, 4243.  If I changed a column,
I would go back to the ten-thousands; otherwise I would move on to the next
column.  If the odometer rolled over twice, I printed -1.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
The obvious.  Nothing tricky.

COMMENTS, LESSONS?
Thanks for running the thing!

WHAT, WHERE, AND WHY ARE YOU?
Develop network design software.

============================================================

=== >20 ==== bmw ==== Doug Murphy ==== ios!djm3 =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          bmw    1000        23.49     1225    Sep 22 11:50       3574

===========================
PROGRAM: bmw    FROM: Doug Murphy    AT: ios!djm3

WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?

1)  Eliminate all "no solution" cases (known algorithm)
2)  Treat the number as an array of digits.
3)  Compute plausible increment range for each decimal place.
4)  From these ranges, compute the smallest possible solution.
5)  From there, increment and check, subject to increment ranges.
	
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
1)  C++ inline functions
2)  Used preprocessor macros as a source compression technique
3)  Other usual hacks...

COMMENTS, LESSONS?
1)  No matter how much I compressed it, Object-Oriented C++ code will
    be bigger than C code.  Information hiding in C++ is too verbose
    if we're being measured on code size.
2)  I need a better algorithm.

WHAT, WHERE, AND WHY ARE YOU?
	Architect/Lead Developer
	Operations Manager - Switch Provisioning
	AT&T-BL,  Holmdel, NJ

============================================================

=== >20 ==== leepfrog ==== David Stephenson ==== mlsma!dstephen =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     leepfrog    1000        17.91     1869    Oct 15 12:49       3660

===========================
PROGRAM: leepfrog    FROM: David Stephenson    AT: mlsma!dstephen
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
I started a the most significant end and worked towards the least
significant end, When I found a duplicate digit I called another function
which jumped forward enough miles so that the clock had changed the
duplicate digit.
Optomization took the form of working how far I could jump the clock.
But that only inproved the performance by about 50% not enough !!
the no-solution check was restricted to just checking that the two unit 
digits were not the same.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Small, I just created a 'sed' script that went through and removed any
unneeded while space and swaped variable names for shorter ones.
	DOES ANYONE HAVE A GOOD PROGRAM TO DO THIS ??????

COMMENTS, LESSONS?
I learnt from the last POTM that I entered that Algoritham optomization
must come before code optomization.

WHAT, WHERE, AND WHY ARE YOU?
I am a Software Engineer interested in Operating System Design and OOP.

============================================================

=== >20 ==== s5 ==== Ramachandran Subramanian ==== cblpe!subra =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>           s5    1000        45.84      894    Oct 25 09:17       5478

===========================
PROGRAM: s5    FROM: Ramachandran Subramanian    AT: cblpe!subra
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
 Compute a list of 4 digit numbers with 4 distinct digits; Assuming that the
 odometer's last 4 digits are one of these numbers, compute the value of
 trip meter. If the 8 digits (from the odometer and trip meter) are 
 distinct, prepend the remaining 2 digits to odometer value and compute
 difference from the given pair of values. The pair with least difference is
 the solution. If the difference is a multiple of 10 or is less than 25, no 
 solution. If there is no pair with 8 distinct digits, there is no solution.
 The trade-off is run-time memory vs speed.
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
 Use 1 char variable names, reduce number of variables, use smallest size 
 variables, eliminate unnecessary syntax, use the side-effect capability, use
 register variables, optimize inner loop to reduce number of computations
COMMENTS, LESSONS?
 It was addicting initially. After I saw the preliminary results, I
 figured that I did not stand a chance of winning. But I still completed
 to enter the contest.
WHAT, WHERE, AND WHY ARE YOU?
 2STP Project Management in Columbus OH. Interests are too many ... music,
 programming,PC,mathematics,stocks,simulation,travel,people etc.

============================================================

=== >20 ==== drex ==== David Magagnosc ==== dmagagno@mcs.drexel.edu =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         drex    1000        31.92     2362    Oct 29 20:40       5554

===========================
... No form returned

============================================================

=== >20 ==== meter1 ==== Yong Li ==== honet4!yong =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       meter1    1000        50.73      495    Oct 29 15:29       5568

===========================
... No form returned

============================================================

=== >20 ==== pz ==== Y.C. Tao ==== lzsc!tao =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>           pz    1000        42.51     1594    Oct 21 15:57       5845

===========================
1.Program logic: (Answer is the answer, Initialze each time to High number)
 First to find all 4-digit unique numbers  (no two digits are same, e.g. 0123,
  0124, ..., 9876) put into array of 10000.  If number is not unique, the
  value is of smallest number larger than the current one as pointer.
 Check if both last 4-digit of 6-digit (Odom) number AND the 4-digit
   Trip number are unique numbers.  If yes, get first 2-digit (2-d)
   of Odom number and Answer= 2-d*10000.
 Loop to (find out both new 4-digit Odom number AND new 4-digit
   Trip number are unique numbers by searching above 4-digit number array)
   Get the Gap between 4-digit Current & Orig(inal) Odom number.
   Add the Gap to Orig Trip number & get Current 4-digit Trip number.
   IF Current Trip number is unique number then
      Get smallest 2 digit number (2-d) > first 2-digit of Odom number from
      the 2 remaining digits. Possible new-answer = 2-d*10000 + Gap
      (Some instance may need adjustment because of Gap >9999)
      Compare with the old Answer, if samller, Answer= new-answer.
   Get the next unique of last 4-digit Odom number.
 
2. I do not think my program is either small nor fast.
3-4. This POTM is kind of fun.  Personal stuff, couldn't give your answers.

============================================================

=== >20 ==== rams ==== Ram Ramachandran ==== iwtgo!rams =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         rams    1000        47.16     1718    Oct 15 13:55       6434

===========================
... No form returned

============================================================

=== >20 ==== hydra ==== Mike Gagle ==== inuxy!kessler =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        hydra    1000        65.91      929    Oct 20 15:05       7520

===========================
... No form returned

============================================================

=== >20 ==== potm2 ==== Bill Mielke ==== cbosgd!wfm =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        potm2    1000        53.30     2382    Oct 30 13:20       7712

===========================
... No form returned

============================================================

=== >20 ==== masses ==== Joe Miller ==== hogpa!jmil =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       masses    1000        18.81     6144    Oct 1  08:58       8025

===========================
... No form returned

============================================================

=== >20 ==== olds ==== Perin Jathavedam ==== mare!pnj =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         olds    1000        52.21     3681    Oct 31 10:25       8902

===========================
PROGRAM: olds    FROM: Perin Jathavedam    AT: mare!pnj
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
The overall approach was to move from the left to right (rather than		
actual right to left operation of the odometer) so as to zero in  on the
result quicker.  Did not really care much about using ints vs chars.
The main idea in the left to right algorithm was to determine the valid
combinations that can occur in the corresponding digits of the odometer
and the trip meter at any instant.  And used a recursive algorithm
to find the result.  Once a cycle completes unsuccessfully for the
most significant digit in the odometer, then it means there is no answer.
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
After timing my program run, it made more sense to reduce the size as much
as possible than try to make it run faster.    Used one letter vars, no in-
dentations etc. and reduced the size to bare minimum.
COMMENTS, LESSONS?
This got me almost addicted to the POTM, though got frustrated sometimes
when things did not work as I expected.   Thanks to you for running the tests
as quickly as you did.
WHAT, WHERE, AND WHY ARE YOU?
Background is Structural Engineer turned into Software Engineer.  Interested
in problems involving innovative algorithms.  Job - Software development.

============================================================

=== >20 ==== dds ==== Don Shugard ==== boole!dds =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          dds    1000        85.41      550    Sep 15 16:57       9091

===========================
PROGRAM: dds    FROM: Don Shugard    AT: boole!dds
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Brute force: I did a naive algorithm just to get into it with the
hope of refining the algorithm. A November 15 deadline shot any hopes
of achieving the final goal. 

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Lots of #defines

COMMENTS, LESSONS?  Thanks for the puzzle. It lead to several enjoyable
lunch time discussions. It also gave me something to think about while
driving. Instead of source size use size of stripped executable. This
would be a better engineering constraint.
WHAT, WHERE, AND WHY ARE YOU?  I've been doing VLIS design and hacking on
VLSI tools for the past eight years. I used to be in MH and now I reside
in HO 4G-526.


============================================================

=== >20 ==== mtrmaster ==== Frank Rahoi ==== nwsca!fer =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>    mtrmaster    1000        72.64     2103    Oct 1  21:06       9367

===========================
PROGRAM: mtrmaster    FROM: Frank Rahoi    AT: nwsca!fer
APPROACH:
I got some code to work reasonablly well, and found all 'impossible' solutions
using this code and all combinations of the following: 000000 XXXX.
The last version of the code checked for impossible solutions quickly by
finding the miles for a 6 digit turnover (all 0's), adjusting the 4 digit 
value accordingly, and checking against the (small) list of 'impossible' 
numbers.  To find the solution for solvable numbers, the algorithm found the
max of (minumum miles that would alter all but one of the duplicate digit (0-9))
and incremented until a solution was found.   
Great Problem, waiting to see the other approaches especially those under 
1s cpu.  Felt a bit stupid on this one.

GRIPES: I made no attempt at decreasing the code size.
I thought this was a stupid criteria and hope it is never used again.

I also think that if 'nothing' can be discerned from the weekly leader board
that it should not be distributed ... more useless mail.  I would like to
see the leader board given meaning, by using NEW random data to generate it
each week. 

============================================================

=== >20 ==== rgk_odom ==== Bob Kramek ==== hotsb!rgk =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     rgk_odom    1000        73.28     2041    Oct 8  19:46       9369

===========================
... No form returned

============================================================

=== >20 ==== howd.i.do ==== Michael Bailey ==== mlsma!mbbailey =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>    howd.i.do    1000        77.61     1619    Sep 29 21:36       9380

===========================
PROGRAM: howd.i.do    FROM: Michael Bailey    AT: mlsma!mbbailey
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?

	Very simple, Just add 1 to the odometer and trip counter
	and check each number against each other, if a
	number was already present repeat the cycle.
	I could not think of any clever ideas 

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
	Remove charcaters

COMMENTS, LESSONS?
	frustration

WHAT, WHERE, AND WHY ARE YOU?
	New to the company at Network Systems UK (mlm)
	ex Royal-Air-Force ( simulation engineer )
	now software engineer ISUP
	interests: basketball, software engineering ( what a mix ! )

============================================================

=== >20 ==== hcy ==== James Yang ==== cbncp51!hcy =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          hcy    1000        97.53      373    Sep 28 11:46      10126

===========================
... No form returned

============================================================

=== >20 ==== miles2go ==== Ravi Sharma ==== bhopal!sharma =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     miles2go    1000       100.91      795    Oct 26 10:45      10886

===========================
... No form returned

============================================================

=== >20 ==== racoco ==== Rich Coco ==== wibls!racoco =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       racoco    1000        75.73     3555    Sep 21 20:21      11128

===========================
PROGRAM: racoco    FROM: Rich Coco    AT: wibls!racoco
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
   all possible odometer/tripometer pairs can be partitioned into equivalence	
   classes (EC) based on difference (mod 10) of low order digit. the EC cont-	
   aining 0 differences has no tuple whose digits are different. the 10!
   tuples whose digits are all different are equally distributed among the	
   remaining 9 ECs. So, for each initial tuple read in, look at last digits	
   If difference is 0, no solution possible. I COULD NOT DERIVE AN ALGORITHM
   WHICH GOT ME FROM THE INPUT TUPLE TO THE NEAREST SOLUTION TUPLE (other	
   than the obvious 'add 1' and check) - Waaaaaaaaa	
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
   since i felt that the real solution involved finding the algorithm	
   alluded to above, i didn't waste time find tuning what i had.

COMMENTS, LESSONS?
   Travel and work prevented me from spending much time on this. i'm hoping	
   someone derived the EC algorithm i wasn't able to. I beieve the answer is	
   in Residue theory (number thy). PLEASE CONTACT ME IF YOU DID IT!
WHAT, WHERE, AND WHY ARE YOU?
   rich coco  racoco@wibls.att.com   508-960-4071		
   1600 Osgood St No Andover, Ma  Rm 30-2B4  NB719AD00  Col A-16

============================================================

=== >20 ==== may.not.run ==== Raju Datar ==== hogpa!datar =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>  may.not.run    1000        63.71     5009    Oct 31 19:13      11380

===========================
PROGRAM: may.not.run    FROM: Raju Datar    AT: hogpa!datar
Overall approach: find the duplicate numbers within tripmeter, odometer
and between trip and odometer. Increment the duplicate number by 1.

I used int to represent each digit. Converted each read char to int by
substracting char '0' from it and adding int 0.

Works for most cases but should check for digit 9 being multiple.
that should reduce the number of cases where my answer is not minimum.

Overall I really enjoyed this POTM acitvity. Wish I had more time to completely
debug the program. I am currently not getting right answers for about 13 cases.
(see above for what I think I would like to do).

============================================================

=== >20 ==== ads_potm ==== Al Schapira ==== mhcnet!ads =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     ads_potm    1000        77.83     3962    Oct 15 12:42      11745

===========================
PROGRAM: ads_potm    FROM: Al Schapira    AT: mhcnet!ads
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?

I pre-generated the 151200 permuations of the 10 digits of length six,
recording which digits got used in each.  For each 6-digit target, using
a binary search I found the smallest permutation greater than it,
and its index, and then tested each permutation onward
until one was found which yielded a solution, or wrapped around to the original
number.  I also pre-built a table of the 10000 4-digit numbers
recording which digit each used so that the solution testing could
be done efficiently.

I tested separately for trivial solutions, and for no solution (F == J).
Aside form pruning the search to known permutations, I used brute force.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?

I spent NO effort reducing program size.  In fact, I put in extra 
argument handling and extra debugging stuff to help me figure out what was
going on. I never took this stuff out.

For speed, I pruned the inner loops and got rid of scanf.
Using the same basic algorithm my times dropped like this

==>     ads_potm     100        51.99     3657    Sep 30 13:28      55647
==>     ads_potm     100        12.31     3610    Oct  1 11:12      15920
==>     ads_potm     100         9.49     3931    Oct  4 13:43      13421
==>     ads_potm     100         5.81     3791    Oct 12 13:11       9601
==>     ads_potm     100         4.77     3962    Oct 15 12:42       8732

Replacing fread() with read() actually increased run time.
I suspect that one read of all 12000 inout characters, and a few pointer
operations would reduce the time slightly, but not significantly.
Since the fastest times were over an order of magnitude faster than mine,
I must have missed a better approach.
I found some optimizations which ran fine on my sparc1+ which
failed on your Amdahl.

COMMENTS, LESSONS?
	get a life, addiction, frustration, amazement,
		thank me for running the thing, FUN, etc.`
All of the above!

WHAT, WHERE, AND WHY ARE YOU?

538620000, CAD/CAE simulation tools for VLSI design and verification.


============================================================

=== >20 ==== holland ==== Warren Koontz ==== hvlpa!wlkoontz =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>      holland    1000       102.09     1852    Oct 4  08:29      12061

===========================
PROGRAM: holland    FROM: Warren Koontz    AT: hvlpa!wlkoontz
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
   
   Observation:  Last four digits of odometer "track" trip odometer.
   Algorithm:
   	Note: "valid" means no repeated digits

   	best so far = 1000000
   	for all valid trip odometer values {
   		compute corresponding last four digits of odometer
   		if (trip odometer  LFDO is valid) {
   			generate two candidates using last two digits
   			update "best so far" using elapsed miles criterion
   		}
   	}
   	print "best so far"

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
   Smallness:  nothing explicit
   Fastness:
   	- Used ugly nested for loops to enumerate valid trip
   	odometer values
   	- Combined some functions to avoid double work
   	- Used integer arithmetic rather than logic where
   	possible

COMMENTS, LESSONS?
   Try to optimize in the mathematical, or other problem domain
   before resorting to programming tricks.

WHAT, WHERE, AND WHY ARE YOU?
   I took my first programming course in 1966 (MAD language)
   and went through various phases involving FORTRAN, PL/I,
   SIMSCRIPT and finally C. In the meantime, I joined the
   management ranks and I haven't done any real programming for
   many years. Still, I like to play every now and then and,
   who knows, I may have to program for a living again some
   day!

============================================================

=== >20 ==== milo ==== Dave Kristol ==== allegra!dmk =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         milo    1000       107.70     2426    Sep 30 11:32      13196

===========================
PROGRAM: milo    FROM: Dave Kristol    AT: allegra!dmk
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Let each digit, 0-9, be represented by a bit in a word 1 << digit.
If all 10 digits are present, 10 bits will be set.  Now, how do we
cheaply tell what bits are present in the 6- and 4-digit numbers?
Two pre-computed tables contain those bits for 0-9999 and 0-999999.
Increment the 4- and 6-digit numbers, combine their table entries,
and stop when their logical OR has all 10 bits set.

There appear to be optimizations possible because there are long
sequences of numbers (for example, all numbers below 010000) that
have duplicate digits and therefore fail immediately.  But I didn't
have time to explore these possibilities further.

I didn't make any attempt to minimize the size of my program,
because I didn't have time, and the improvements I could make were
unlikely to put me near the top of the standings anyway.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Nothing especially surprising.

COMMENTS, LESSONS?
Once again I find that it's not too hard to write a program that runs
within a factor of 10 of the leaders, but that I obviously fail to see
some clever trick that will yield the extra order of magnitude.

WHAT, WHERE, AND WHY ARE YOU?
David Kristol, Dept. 11382, Murray Hill, NJ


============================================================

=== >20 ==== are_we_there ==== Brian Urch ==== addams!bcu =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==> are_we_there    1000       139.39     3857    Oct 1  15:09      17796

===========================
... No form returned

============================================================

=== >20 ==== odomEE ==== Ed Eng ==== cdsdb1!ed =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       odomEE    1000       251.54      755    Sep 30 18:09      25909

===========================
... No form returned

============================================================

=== >20 ==== odo ==== Dave Dykstra ==== graceland!dwd =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          odo    1000       342.62     1846    Sep 14 11:36      36108

===========================
PROGRAM: odo    FROM: Dave Dykstra    AT: graceland!dwd
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
First tried brute force to get something working.  After that, I realized
that some numbers could be skipped and tried again to skip those with
repeated digits, starting from the most signficant digits down.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
As I said in the last question, I improved speed by skipping sets of
numbers where digits were repeated by higher signficant digits.  I got
a factor of 10 improvement.  Once I saw other people getting factors
of 10 better than mine (and later more factors of 10) with smaller code,
I decided I had spent enough time on it and didn't bother to make it small.

COMMENTS, LESSONS?
I wasted too much time on it.

WHAT, WHERE, AND WHY ARE YOU?
I'm a Resource Link associate in software development, most recently
working on layers and now working on the Broadband Switching System.  I
have about 10 years professional experience in software development and
a CS Phd.

============================================================

=== >20 ==== odo_sent ==== Alan Javornik ==== mopar@dr.att.com =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     odo_sent    1000       437.78     3747    Oct 27 12:34      47525

===========================
PROGRAM: odo_sent    FROM: Alan Javornik    AT: mopar@dr.att.com
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	The first decision was how to decide when all digits were distinct.		
	I used a unique bit position to represent each digit and xor'ed
	them to determine uniqueness.  One would think there would be
	a mathematical solution rather than an iterative solution but I
	haven't found one yet.
	The second was how to determine when the problem was unsolvable (-1).
	When the LSD's were the same was a simple case but there were 
	others that were not as obvious.
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
	Took out the function calls after program was verified.
	Used int rather than short for speed even though the space 
	wasn't fully needed.
COMMENTS, LESSONS?
	
	

WHAT, WHERE, AND WHY ARE YOU?
	The thing about these kinds of problems is that I tend to think
	about them until I come up with a solution, but, they are fun.


============================================================

=== >20 ==== gdo ==== Gary Oswald ==== ihlpm!gdo =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          gdo    1000      1091.16      732    Sep 30 15:08     109848

===========================
... No form returned

============================================================

=== >20 ==== focus ==== Steve Palmer ==== ho1focus!srp =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        focus    1000      1178.59      732    Sep 28 17:17     118591

===========================
	PROGRAM: focus    FROM: Steve Palmer    AT: ho1focus!srp
	WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
		
			don't check cases where least significant digit
			is the same
			otherwise, loop checking for all digits - if not,
			bump up both counters and check again until
			999999 loops are done or a match
			used char strings for the counters to make the
			all digits check
		
	WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
		
			wrote a filter to take the long variables used in
			the original program and make them smaller
	
	COMMENTS, LESSONS?
			thank you for running the thing, it is FUN
			How 'bout that?
			Actually, this is a great idea!!!  Something to
			do on those cold rainy weeknights.
	
	WHAT, WHERE, AND WHY ARE YOU?
			What's going on with the Redskins?

============================================================

=== >20 ==== open_road ==== Dom Gurrera ==== mtqua!dom =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>    open_road    1000      1461.82     1898    Oct 27 16:10     148080

===========================
PROGRAM:   open_road       FROM: Dom Gurrera       AT: mtqua!dom
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM
 Ended up using arrays - did try to convert to a number
 for incrementing, but that took longer. 

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Squeezed code into not so readable concoctions, no comments and
did not check for absencs of an input, also didn't close the file.

COMMENTS, LESSONS?
It was a fun problem.  I did run my own speed runs before submitting.
Even looked for speed in using > instead of ==. Fun and educational.

WHAT, WHERE AND WHY ARE YOU?
        Software developer in the PARTNER small business telephone
        group in GBCS.

============================================================

=== >20 ==== steve ==== Steve Beckle ==== ihlpl!srbeckle =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        steve    1000      1487.24     3526    Oct 22 10:52     152250

===========================
PROGRAM: steve    FROM: Steve Beckle    AT: ihlpl!srbeckle
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
 For each input pair, ran iterative algorithm until solution found or no
 solution after 1 million miles. First, make all digits in main (odo1)
 unique. For instance 434687. The 4 appears twice. Add 313 -> 435000.
 then work on 435000 etc, until 435126. Now do the same for odo2.
 Since moving odo2 changes odo1, must see if odo1 digs still all different.
 If so, resolve any digits common to odo1 and odo2. Go back and test
 for odo1 unique, repeat entire process as needed.  All mileage
 increments were based on determing what integer had to be added
 to eliminate the rightmost "culprit" or duplicate digit, either
 within the same odo or between the two. New tack:Tried to
 generate all possible "winning" combinations then do lookup for each
 input pair based on diff between odo1 and odo2, but insufficient
 memory. Could have really gone fast after initial table was built!!
 Ran several test pairs to identify instant losers based on diff btwn
 odo1 and odo2. Put test for these diffs up front in program to save
 time finding null solutions. Frustrations?? That I didn't figure out
 the mathematical solution and had to use an iterative one.
 Hey. This was fun!!! A chance to do real programming. A challenge!
 Clever ideas?? How can I claim any when I'm not even close to
 the best time? :-) This was the first POTM I participated in since
 it didn't seem so bizarre/impossible/mind-bending.

============================================================

=== >20 ==== jfernan_odo ==== Jesus Fernandez ==== hzsbg01!jfernan =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>  jfernan_odo    1000      1991.67     3410    Oct 8  19:47     202577

===========================
... No form returned

============================================================

=== >20 ==== jims_odo ==== James Stuhlmacher ==== intgp1!jims =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     jims_odo    1000      2146.12     2585    Sep 30 10:32     217197

===========================
... No form returned

============================================================

=== >20 ==== brute ==== Phil Gillis ==== whservh!pwg =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        brute    1000      2270.36     1684    Oct 25 12:41     228720

===========================
... No form returned

============================================================

=== >20 ==== contest64 ==== Joe Kruskal ==== research!kruskal =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>    contest64    1000      2722.45     1762    Oct 10 23:41     274007

===========================
PROGRAM: contest64    FROM: Joe Kruskal    AT: research!kruskal

I entered the contest as a way of learning to use Perl.  I was successful
in learning about Perl, and my program worked, though not very fast.

The approach was to generate all 5040=10*9*8*7 4-digit numbers which
have no repeated digits, and to try each one as the final four digits
of the 6-digit odometer reading. Arithmetic then generates the 4-digit
odometer reading.  A very simple hashing using powers of 6 and
guaranteed not to produce false agreements was applied to the eight
digits and looked up in an associative table with 45=10*9/2 entries.

If the hash code was not in the table, the 8 digits were not all
distinct, so the case was discarded.  If the entry was found, it
yielded the two unused digits, which were tried in both orders.  The
additional miles were calculated in each case, the minimum was found.

Since Perl is quasi-interpretive (source code is always parsed and
compiled at run time), the source code is the running code.  No attempt
was made to reduce the size of the code.

-------------------------------------------------------------------
Joseph B. Kruskal  908-582-3853 mh 2c-281  Sent  Tue Nov  2 10:15:11 EST 1993

============================================================

=== >20 ==== snail ==== Thierry Mataigne ==== hvlpa!tmataign =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        snail    1000      2767.71     2040    Oct 11 12:02     278811

===========================
... No form returned

============================================================

=== >20 ==== small ==== Narcus Hall ==== iwtlc!marcus =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        small    1000      2797.59      723    Sep 15 13:41     280482

===========================
... No form returned

============================================================

=== >20 ==== potm ==== Gregg Wonderly ==== intgp1!gregg =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         potm    1000      3017.36     1048    Sep 12 11:19     302784

===========================
PROGRAM: potm    FROM: Gregg Wonderly    AT: intgp1!gregg
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	I decided that I would just try exhaustive search by
	simulating the wrap around of the TPO and ODO and then
	looking for unique digits.  An extremely inefficient
	method, but to the best of my knowledge the program
      worked the first time I ran it.
	
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
      Nothing special...

COMMENTS, LESSONS?
	I spent little time on a problem which obvious has some
	very efficient answers that are orders of magnitude from
      my solution, but I had other things to do...

WHAT, WHERE, AND WHY ARE YOU?
	My background involves mostly just-do-it programming which
      is the basis of my brute force solution.  It is sometimes
      easier to get the answer in 4 hours after working for 4 minutes
      than to work for four hours to get the answer in 4 minutes!

============================================================

=== >20 ==== dlkmain ==== David Koeberle ==== vilya!djdlk =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>      dlkmain     999         8.76      868    Oct 29 11:52       1744

===========================
... No form returned

============================================================

=== >20 ==== odoway ==== Bruce Brandon ==== esun!bgb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>       odoway     999        31.21      990    Oct 22 12:41       4111

===========================
... No form returned

============================================================

=== >20 ==== dbb ==== Dave Brown ==== cbskat!dbb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>          dbb     999       199.91     1326    Oct 20 23:24      21317

===========================
... No form returned

============================================================

=== >20 ==== odoretentive ==== Tim Tjarks ==== iesde!tjarks =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==> odoretentive     997         2.74      589    Oct 31 11:01        863

===========================
PROGRAM: odoretentive    FROM: Tim Tjarks    AT: iesde!tjarks
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
   My first approach was to recognize that (A-B) mod 10000 was constant as
   you travelled, so I generated all values of A and B using digits only
   once and built a table indexed by the difference.  This proved to be
   slow and use too much memory (exceeded brk ulimit on Amdahl,  but it
   did give me the pattern of which differences yielded no solution, so I
   incorporated that into the next try.  Next, I tried the brute force method
   of incrementing and checking the digits.  That wasn't so bad.  I refined
   it by a) figuring the next best guess for the increment rather than just
   incrementing by one, and b) recursing so that previously checked digit
   positions were not re-checked.

WHAT DID YOU DO TO MAKE THE THING SMALL?
   Assume a 32-bit int, use one-character variables and only necessary
   whitespace.  Use ?: rather than if-else.  #defines proved not worth the
   effort, but I did use global variable for a couple constants.  Declare
   varaiable only if the default wouldn't work or didn't save space.

WHAT, WHERE, AND WHY ARE YOU?
   Tim Tjarks,  tjarks@iesde,  IHP 2F-547
   Switching Systems - Software Development Environment

============================================================

=== >20 ==== woody ==== Fred Hicinbothem ==== homxb!fah =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        woody     997         3.71     1251    Oct 11 16:48       1622

===========================
PROGRAM: woody    FROM: Fred Hicinbothem   AT: homxb!fah
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Nobody will read this far anyhow, so I need not be embarrassed.
* worked from left to right		* no mod (%) or division (/)
* worked only with numbers <10		* didn't use int odo values
* keep a MASK with bits to indicate digits in current solution
* working from left to right, look for digits already used, if one
	is found, then add enough to cause a carry into that position
	and then repeat.  Note: I added enough to make the last digits
	something like 0123 as opposed to 0000 - a cycle here, a cycle there.
* problem issue was situations involving 9s that created unexpected
	carrys into positions further left than I expected
* as for the quick-checks ... I checked only the units digits ... the other
	checks took too many characters for "unlikely" payback.
	
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
	Nothing you haven't read already.  Speed was all algorithm since
	I am a particularly rotten programmer.

COMMENTS, LESSONS?
	If you are the one making up the final tests, your entry ought to
	be able to pass them.  Otherwise, a shitty programmer with a good
	algorithm can be competitive with the converse.

WHAT, WHERE, AND WHY ARE YOU?
	I am the POTM-master ... email is my life.  I do have a REAL job
	working for the Fast Features Adjunct Systems Technology (FFAST)
	department - our products are better than our acronym!

============================================================

=== >20 ==== perma10t ==== Chip Webb ==== allegra!cwebb =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     perma10t     997       223.99     1095    Oct 9  18:00      23494

===========================
 PROGRAM: perma10t    FROM: Chip Webb    AT: allegra!cwebb
 WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	
	build table of known possible 6-digit combinations.
	numbers like xxxxxi and xxxi always fail.
	building the table takes lotso time & fair amount of space


 WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?

	cpp (ugh, don't make us do this again, for your sake Fred!)

 COMMENTS, LESSONS?
	It is fun to work on a solution, but the weekly results can
	be discouraging if you're behind by a factor of 100. :-)
	Please keep doing the contest!


============================================================

=== >20 ==== mink ==== Harry Pilafis ==== mink!hbp =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         mink     995       417.44      818    Oct 11 11:57      42562

===========================
... No form returned

============================================================

=== >20 ==== simple_code ==== Richard Toeniskoetter ==== cblpe!rtoe =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>  simple_code     995      2245.57     2361    Sep 28 14:35     226918

===========================
PROGRAM: simple_code    FROM: Richard Toeniskoetter    AT: cbskat!rtoe
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
My approach was to initially classify all 6 digit numbers with unique 
digits into equivalence classes based on the 6 digits present, and do the 
same with 4 digit numbers.  Then given any 4 and 6 digit pair, increment
the 6 digit up to next number with all unique digits, add the same delta
to the 4 digit number, and check to see if the equivalence classes were
complements (indicating all 10 digits present).  Submitted code used 
prime number categorizations of the equivalence classes, had planned on
changing to bit masks for speed but didn't get that far.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Nothing was done since the original run was so far off of the leaders
that it was apparent the algorithm I was using was not competitive, no
matter what I did.

COMMENTS, LESSONS?
I was amazed at solutions that were 1000 times faster than mine,
and much shorter as well.  So amazed that I gave up ...
Looking forward to the next problem.

WHAT, WHERE, AND WHY ARE YOU?
working in Bell Labs Columbus OH, primarily supporting Switching
projects with quality activities.

============================================================

=== >20 ==== odom ==== Kevin Ahrens ==== ihlpm!kea =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         odom     985       300.66     1439    Oct 29 09:30      31505

===========================
PROGRAM: odom    FROM: Kevin Ahrens    AT: ihlpm!kea
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
  After receiving the original problem and thinking about what could be done
to solve the problem other than brute force, I came up with the following
reasoning:
      The trip meter and the bottom 4 digits of the odometer are dependent on
each other.  One can't be changed without affecting the other.  It is only
necessary to check the first 10,000 "miles" for 8 unique characters between
the trip meter and the odometer.  If 8 unique digits are found, the upper 2
digits of the odometer can be calculated to give the minimal distance.  If
8 unique characters can't be found in 10,000 iterations, there is no solution.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Didn't concentrate much on fast.  For small, I removed all 
	unnecessary spaces and renamed all variables, classes, etc, 
	to 1 character each.  Removed comments.

WHAT, WHERE, AND WHY ARE YOU?
I'm just another programmer that likes to write programs to solve problems.
Also gives me an opportunity to play around with C++.  Thanks to Fred for
running this thing.  Looking forward to the next challenge.

============================================================

=== >20 ==== poot ==== Andrew Hume ==== research!andrew =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>         poot  KILLED      9999.99     2349    Sep 22 08:23

===========================
... No form returned

============================================================

=== >20 ==== oct93 ==== David Simen ==== uhura!dcs =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        oct93  KILLED      9999.99     1044    Oct 25 17:02

===========================
PROGRAM: oct93    FROM: David Simen    AT: uhura!dcs
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
Overall approach:  determine "obvious" approach (simple algorithm) and lang.
(C), code it.  Run >= 3 times for timing; also reduce size by eliminating
white space, using some #define macros.  Then go in 2 directions in parallel:
(1) look for incremental improvements in algorithm or program (e.g.,
    eliminate function calls; fiddle with algorithm.
(2) look at the mathematics for a "short-cut" idea.

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
Speed:  (1) algorithmic improvements (e.g., rather than go step by step, try
to increment the counter in larger increments by doing a little more analysis;
(2) speed-ups, e.g., eliminating function calls by putting code in-line.

COMMENTS, LESSONS?
Will probably participate again, but was disturbed at finding myself tweaking
msecs off run time vs. improving program organization, maintainability, etc.

WHAT, WHERE, AND WHY ARE YOU?
Object-oriented design/development for > 5 years, use C++.  Lots of GUI work.

============================================================

=== >20 ==== short ==== Ajay Gupta ==== intgp1!ajgupta =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>        short  KILLED      9999.99      561    Oct 8  17:15

===========================
... No form returned

============================================================

=== >20 ==== initial ==== Steve Keefe ==== ihlpf!keefe =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>      initial  KILLED      9999.99     1337    Oct 22 14:31

===========================
PROGRAM: initial    FROM: Steve Keefe    AT: ihlpf!keefe
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	
I was going to try several methods, unfortunately I only had time
for the the brute force method ... (ie. just add 1 to both numbers
until I either found the answer or the numbers wrapped back on themselves)

WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?

My approach is so slow that I didn't bother to make the program
small.

COMMENTS, LESSONS?

I wish I could remain anonymous since my program stinks so badly.

WHAT, WHERE, AND WHY ARE YOU?
	I've been programming in some form or another for 14 years 
for AT&T and I love a challenge.  I think this is a great opportunity
for programmers to have some fun doing things they love to do.

============================================================

=== >20 ==== s.forward ==== Bruce Hartman ==== cbvox!bruce =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>    s.forward  KILLED      9999.99      608    Sep 23 20:19

===========================
... No form returned

============================================================

=== >20 ==== potm.bas ==== Greg Fiore ==== aluxpo!fiore =====

         PROGRAM    SCORE   SYS+USR(sec) CHARS    DATE RECEIVED  TIEBREAKER
==>     potm.bas  NO RUN         0.00     2197    Oct 29 16:40

===========================
PROGRAM: potm.bas    FROM: Greg Fiore    AT: aluxpo!fiore
WHAT WAS YOUR APPROACH TO SOLVING THE PROBLEM?
	
 I incremented B until it differed from A, then used a simple
 fast algorithm to go through combinations of the other letters.		
	
WHAT DID YOU DO TO MAKE THE THING SMALL?  OR FAST?
 I tryed to minimize the steps, calculations and decision statements
 nested inside the algorithm.

COMMENTS, LESSONS?
 I realize that a more numerical approach is necessary to reduce time.
 If I want my entries to be run I must use C!

WHAT, WHERE, AND WHY ARE YOU?
 I work at Allentown and evaluate the reliability of I.C.'s. Most of
 the equipment I use is old and runs on PC Basic. 

============================================================
Make your own free website on Tripod.com