RESET

The details of the Autumn Programmer Of The Month (POTM) Contest:

                 ****  R  E  S  E  T  ****

My car dashboard (and probably yours) has two mile-measuring things on it:

A) an odometer that measures how many miles my car has traveled 
	since it was born;

        [_][_][_][_][_][_]       <-- this is A

B) a "trip" odometer that measures how many miles the car has
	traveled since I last reset it to zero by pushing a button.

              [_][_][_][_]  *    <-- this is B  (* is the reset button!)

   the button works fine ... and resets B to 0000 when I push it.
   (I had it fixed since the original odometer problem in 1993!)

Well, I often look at my dashboard, and the other day it looked like:

          1  2  3  4  5  6           (total miles traveled)
                1  3  6  2  *        (miles since last reset - no tenths)

The numbers on top were all different.  I was truly amazed but 
disappointed that those on the bottom were not "7890".  Obviously,
I should have hit the reset button back at 115566 ... but I didn't.

So, when should I NEXT press the reset to make 10 different numbers
appear at the earliest possible time???  When it wasn't obvious
how to figure this out ... I thought this might be worthy of a POTM!

You'll be given a bunch of starting points (A mileages) and asked to
find when to reset to achieve the earlist possible point at which ten
different digits appear on the odometers.

Your C, C++, PERL, JAVA, or SHELL program will read a file of starting
odometer readings and you will output a corresponding set of mileages.
==========================================================================

========= IF YOU'RE INTERESTED ... READ ON FOR THE GORY DETAILS.  IF NOT,
========= MAYBE WE'LL GET YOU INTERESTED IN THE NEXT POTM !!!!

DEADLINE is 11:59 PM EST on Saturday November 30, 1996 - I must receive
your entry by then ... you may enter early and update your entry as
often as you like - enter early and solve the porting problems!

(Please do not be afraid of all these details ... the intent of most POTMs
  is straightforward, but I've found that I need to be very explicit to try
  and close any "loopholes" for all you "requirements lawyers" out there.)

I.   WHAT DOES YOUR PROGRAM HAVE TO DO?

	a. Your program must take a single argument with the name of the
	   input file.  The input file will contain up to 1000 lines.  Each
	   line will have a number between 0 and 999999 in it. Each number
	   represents the starting mileage on the [A] odometer.  Assume
	   that the [B] odometer reads [0000] at this time.

	b. For each of the input lines, your program must deduce exactly
	   when to push the reset button in order to achieve the earliest
	   possible time at which all ten digits (in [A] and [B]) will be
	   different.

	c. Your program then must output two numbers for each input line:
	   the first number is the mileage reading of [A] when the reset
	   button is pushed; the second number is the mileage reading of
	   [A] when all ten numbers will be different (assuming that the
	   reset was pushed at the first mileage marker).


II.  HOW ABOUT A SIMPLE EXAMPLE

	a. your program reads in the number 212000 ... the starting
	   values for this problem are thus:

       [A1]=   2  1  2  0  0  0     (total miles traveled)
       [B1]=         0  0  0  0     (miles since last reset - no tenths)

	b. your program then works its magic and deduces that if you
	   push the reset button in 559 miles, at 212559, then 897
	   miles afterwards the readings will be as follows:

       [A2]=   2  1  3  4  5  6     (total miles traveled)
       [B2]=         0  8  9  7     (miles since last reset - no tenths)

	c. your program then prints out two numbers: 212559 213456

	[C]=212559 is the first number output, [A2]=213456 is the second.

	d. Here is how your answer will be checked: NUM1 is the final six 
	   digit odometer indicator and NUM2 is the final reading of 
	   the four digit trip odometer.

		NUM1 = [A2] = 213456 in our example
		NUM2 = [B2] = [A2] - [C] = (213456-212559) = 0897

	   NUM1 and NUM2 must be comprised of 10 different digits.
	   Assuming NUM1 and NUM2 satisfy this requirement, your score
	   will be [A2]-[A1] = 213456-212000 = 1456 in this example.
	   (special cases where one or the other odometer "roll over"
	   or pass through 0000 are covered below.)

III. TELL ME MORE ABOUT HOW THOSE ODOMETERS WORK

	a. forget about tenths of miles ... assume everything is miles
	   ("012345 0000" implies 12,345 miles ... it's just easier ...
	   no decimal points ... this is the POTM, not the real world!)
	   If your car measures things in meters, or fathoms, or rods,
	   or light years i really don't want to hear about it.

	b. they work like the ones in your car ... if you go a "mile", both
		of them increment by a "mile"

	c. both the odometer and "trip" odometer "roll over" as expected,
		from 999999 to 000000 and from 9999 to 0000.  When distances
		are computed, they are computed as in the real world - 
		the distance from 999999 to 000001 is two miles.

	d. don't even consider what happens when the odometers are "in the
		middle" of changing, with half numbers showing.  Just don't.

	e. no fiddling, no cheating, no mechanical messing, no going 
		backwards, no nothing that is even a little strange!


IV.  THE SCORING - HOW TO WIN!

    First Score:  for each line of input, your score will be the number
    of miles you travel before all the digits are different.  Your
    score will be the sum of the mileages traveled for all imput lines.
    If your solution for a line is not valid, you will receive a score
    of 999999 for that line.  Clearly, low scores are good and lowest
    first score on the final set of input will win.

    Second Score:  In the event that more than one program has the
    same lowest first score (something I expect in THIS POTM), the
    winner will be decided based on execution time and length of your
    source code according to the following equation:

	T = hundredths of seconds sys+user time to solve all of the
	      1000 lines in the final test (as measured by timex 
	      on my machine)  (e.g. sys+user = 3.45 => T=345)

	S = ls -l of your source code (or shell/awk/perl/etc.)

>>> ADDED 9/21:  THERE ARE SOME RESTRICTIONS ON YOUR SOURCE CODE:
>>>	a) When you send in your entry, please include your name and
>>>		email in the body of your email message, and include
>>>		some kind of  message followed by your Source
>>>	b) each line of your source must be no longer than 80 characters
>>>		followed by a carraige return
>>>	c) the last line must also end with a carraige return
>>>	d) no MAKEFILES allowed except as specifically granted by the
>>>		POTM-master - and no complex compile instructions.

	Smallest T+S wins the tiebreaker.  (Note: since timex may vary
	from run-to-run, a (T+S) difference <= 3 will be considered
	a tie and the earliest entry rule  (next tiebreaker) applied.  
	A program that is 500 bytes long and solves all 1000 problems
	in 10 seconds (sys+user) will have a T+S=1500.

	Anyone complaining about how I'm encouraging unreadable code
	will be penalized 100 points ... (not really, but if you
	complain TWICE your entry may mysteriously fail to compile).
	If you win, you've got to supply a readable, commented copy.

	Further (unlikely) ties will be awarded to the earliest entry!  

	THE FINALS WILL CONSIST OF a file with 1000 starting mileages
	in it ... no more, no less.

V.  INPUT/OUTPUT

	a. Input will be a single file with up to 1000 lines.  Each line
	   will have a single number on it that is >=0 and <=999999.
	   Leading zeroes will not be present in the input.  The number
	   represents the starting odometer reading for each problem.

	b. Your output should be one line per input line.  Each output
	   line must contain two numbers ... leading zeroes should not
	   be shown in your output.  The two numbers should be separated
	   by a space.  The first number is the odometer reading at 
	   which the reset button should be pushed and the second number 
	   is the odometer reading when all ten digits will be different.

	c. All input is derived from the file whose pathname is contained
	   in the single argument to the executable program:
	   e.g.:  myprogram filename


VI.  READ THE Frequently Asked Questions (FAQ) list distributed every
     week ... it often contains corrections to this problem statement!

There.  Wasn't that much easier than the LAST POTM???  No excuse not to enter
this one is there???  Why, you can practically see your name on the coveted
Programmer Of The Month trophy can't you????

=============================================================================
    The following items are standard stuff for ALL the POTMs ....
    (but they occasionally will change ... so READ 'EM!)
=============================================================================
I.  About your programming:

    a) I compile on one machine (usually) and execute on 
	another as follows:

        compilation machine: SunOS 5.3 Generic_101318-59 sun4m sparc
        execution machine  : SunOS 5.3 Generic           sun4c sparc

    b) The compilers I have available are (at least):

        SPARCompiler C++ 4.0
        SPARCompiler C   ANSI C compiler
         		 SVID compliant under SunOS 5.x
        gcc/g++ version 2.7.2
	PERL version 5.002
	Java version 1.0
	Scheme48 - a Lex variant

    All compilation will be done WITHOUT ANY OPTIMIZATION, and the
    standard math library will be loaded (even if not used).  While
    this might not reflect the real world, it is at least consistent.
    No makefiles are permitted, if there are special instructions
    please so indicate in your program header comments.

         Plus: ... whatever else I can support on the compilation 
         machine ... just ask and I'll try to find it!!!
         I have the ability to compile on several different
         boxes, so don't hesitate to ask!

>>>      IMPORTANT:  submit early so we can resolve any
>>>      portability problems!!!  

       NOTE: assembly code submissions are NOT acceptable.  I must be
       the one to compile your code so I can check for cheating!

    c) if you wish to submit a shell program, Bourne, Korn, and csh
         are available ... along with any bin or /usr/bin tools that
         are available as generic Unix tools - my judgement!!!
         (again - submit early in case there are version differences)

    d) Temporary files may be created in /tmp, but MUST be removed
         when you are done ... creation of files anywhere else is
         strictly prohibited.

    e) Maximum size of executable is 1 Megabyte ... please!!!!

    f) Maximum malloc'able space is a bit over 50 Meg ....

    g) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1

    h)	 a    = 0x80000000  = -2147483648
         a - 1 		    =  2147483647
         a + 1 		    = -2147483647
         {a} is true.	{a == 0} is false.

II.  The system testing ....
    
    a) mail me an entry as soon as possible - you can always submit
         another entry if you improve your solution .. but try and
         keep it down to one a week once the porting issues are 
	 resolved .... please!  The system test will have fewer than
	 1000 lines in the input file.  Specific answers to the
	 individual problems that your entry derives will NOT be shown
	 to the contestants.

    b) one entry per person (or team) please.  I associate each entry
         name with an email address and a person for communication
         purposes.  Communication is fine - and encouraged - but
         everyone's code should be their own unless there is a
         stated collaboration and a single team entry.  Honor system!

    c) on receipt of your entry, I'll run a system test to make sure
         your program works ... you'll receive the results and
         a weekly standing of how you fared against other entries.
         (I usually will get to new mail once a night but perhaps not!)
	 Standings on the system test may not indicate expected final 
	 results - in fact, they may be misleading!

    d) please make sure your program works on the system test problems.

    e) your program must perform the task specified within 10 minutes
       sys+user time as measured by timex on MY execution system.
       Your time will be provided along with your system test run
       so you can see the differences in speed between yours and mine.
       All execution time measurements used for tiebreakers (if any)
       will be measured using  time via timex (similar to
       time command).  NOTE: A code fragment to measure elapsed time
       is available from the POTM-master for the asking.

III.  SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!

   Please email (not uuto, no attachments) your source code to me at:

         enter@potm.ffast.att.com		(preferred)
         hicinbothem@att.com		 (use only as a last resort!)

    IMPORTANT:  ENTER EARLY - you will receive weekly standings and
    you will resolve any portability issues early.  You may improve
    your entry at any time by simply sending me another entry - so it
    pays to enter earlier!  (I process most everything in a day or so)
    For RESET, you may want to consider solving the problem correctly
    before you work on minimizing speed or code size.

    IMPORTANT:  If you don't hear from me within a few days - it may
    mean that the mail got screwed up .... please follow up with an 
    inquiry to hicinbothem@att.com ....

Thanks!  If you have any questions, mail 'em to me - if I answer them
I'll include them in the Frequently Asked Questions (FAQ) list I 
circulate with the weekly standings!!!  Don't call me ... please!

WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID
  ERRORS I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!

Looking forward to your entry!	(remember:  enter@potm.ffast.att.com)
=Fred












Make your own free website on Tripod.com