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