Positions 14-40

Note - program listings may not print correctly due to HTML conflicts.
RESET Program entry descriptions (continued)  positions 14-40

---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---
-()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()-
---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()---

============== 14 ====================== QuaSimOdo =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
         QuaSimOdo      1879997    389    358     31 75  Chris Hendrie
=================
QuaSimOdo was submitted by Chris Hendrie at cihendri@uwaterloo.ca
=================
++ Please summarize the algorithm used by QuaSimOdo
QuaSimOdo first computes for each subset of {0,...,9} the latest offset to
the necessary reset point, given only those digits for the trip-meter and
odometer suffix (hard to explain). This takes 1024 x 10 steps, but is
relatively quick. For each input number, it can then simply pick odometer
digits from left to right, verifying that the latest possible reset point
comes after the given input. This takes at most 6 x 10 steps, and so is very
fast.

++ What kind of tricks did QuaSimOdo use to minimize code length?
Everything I could think of. One #define, argc (aka. 'm') as a variable, ?:
wherever possible, etc. etc.

++ Here's what I hated (and loved) about this POTM's scoring:
I liked the combo of run time and code length. Looks to me like code-length
was the dominant factor, which I find a tad disappointing. I would perhaps
have made run time twice or three times as important.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
I'm a 3rd-year Computer Science undergraduate at the University of Waterloo.
I haven't found an interesting job yet. For fun, I juggle. Innermost secret:
I'm an arrogant young-un who chafes at losing to more experienced hackers.
How about a game-playing POTM?

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

============== 15 ====================== TheFinger =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
         TheFinger      1879997    402    314     88 84  =Neil Weinstock
=================
TheFinger was submitted by Neil Weinstock at nsw@ariel.com
=================
++ Please summarize the algorithm used by TheFinger

First, if the input number was >= 987532, I set it to 0, because it would
roll over, so same difference.  

For each number fetched, I called a recursive function that worked one 
digit at a time, from left to right.  For each digit, I do this:

	if (this digit is not "used")
		if (this is the rightmost (ones) digit)
			figure out trip odometer value from available digits
			if this solution works, print and return all the way up
		else 
			recurse, next digit to the right
	increment digit

That's basically it.  There's plenty of optimization, naturally.

++ What kind of tricks did TheFinger use to minimize code length?

Much was algorithmic. Other than that, my favorite little tricks were:

	1) Where possible, embed assignments into other statements, to
	   avoid the need for brackets.  My favorite spot was at the end
	   of an arg list for a function call.

	   Example:  printf("%d %d\n",v-t,v,h=0);

	2) Perl-like constructs to eliminate an if().

	   Example:  v-t= t, then it is possible to find a solution (in particular,
press reset at p - t) using the value under consideration for p[j],
and p[j] is fixed at its current value.  If not, other values of p[j]
are considered until one is found for which a solution exists.

When values for all six digits of p have been found, the answer is
displayed:  Reset is hit at p - t (where t is the smallest number made
from the digits not in p).

++ What kind of tricks did reset use to minimize code length?

Short variable names.

Maintained bit map of used digits instead of using an array of flags
and thus used less code for setting bits and initializing the list.

Removed all excess blanks, tabs, and newlines.
 
++ Here's what I hated (and loved) about this POTM's scoring:

I didn't like not knowing what the tiebreaker scores were.

I hated the "smallest source code size" scoring.

 
++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Lucent; Holmdel; Currently working on a storage technology product;
Sing, act, play chess, etc.; That's for me to know...; None at the
moment.
=================================================================

============== 17 ====================== brauciens =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
         brauciens      1879997    412    344     68 47  Krists Boitmanis
=================
brauciens was submitted by Krists Boitmanis at
acad.latnet.lv!ugale@kcig2.att.att.com
=================
++ Please summarize the algorithm used by brauciens
Array as follows:
[1|2|3|4|5|6!7|8|9|10]
First 6 - main odometer (D)
Last 4 - RESET odometer with digits in reverse oder (R)
Start at S[10]={9,8,7,6,5,4,3,2,1,0}
After some rotations of digits:
 for (i=0;i<6;i++) {
   k=S[9];
   for (j=9;j>i;j--) S[j]=S[j-1];
     S[i]=k;
     for (j=9;j>i;j--)
     /# making of D and R out of array #/
     if (D-R>[given number of miles]) break;
     else {k=S[j];S[j]=S[i];S[i]=k}
   }
everything is ready for output.

++ What kind of tricks did brauciens use to minimize code length?
Efficiency of algorithm allways does the job.

++ Here's what I hated (and loved) about this POTM's scoring:
Lots of thanks to Fred for this overcrowded POTM!  Everything was great!
More people, more enjoyment.
Congratulations to WINNERS!!!

++ COMPANY?  LOCATION?  DO FOR FUN?
Last year at Ugale Secondary School (high school).
Ugale is 40km from port Ventspils in LATVIA.
Programming, basketball.


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

============== 18 ====================== too_many_miles =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
    too_many_miles      1879997    413    324     89 112  Kurt VandenBranden
=================
too_many_miles was submitted by Kurt VandenBranden at 
	KVD2@bipsy.se.bel.alcatel.be
=================
++ Please summarize the algorithm used by too_many_miles
combinatorial (sorry, but I can't explain any 
better, it would take a few pages)

++ What kind of tricks did too_many_miles use to minimize code length?
Read every line of code 20 times, and check if it can't be skipped or
included in another statement.
Use the same variable if possible for different purposes.

++ Here's what I hated (and loved) about this POTM's scoring:
It's fun for once, but I wouldn't like to do this another time.
I worked a few hours on the base algorithm, and then the following weeks,
I was busy making it smaller and smaller and smaller and smaller...

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
I'm a software engineer at Alcatel Bell in Belgium.
I read SF, I juggle, I compete in POTM.
I would like a POTM that doesn't depend on the speed of the language
you are using. The last 2 POTM's were very much about speed. It would be
nice to have a POTM that depends on the algorithm you write, where it
doesn't make a difference if you implement it in C, PERL, JAVA or even shel.
(But I don't have any ideas for such a POTM)

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

============== 19 ====================== odomontade =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
        odomontade      1879997    421    300    121 65  D.McIlroy S.Dorward
=================
odomontade was submitted by D.McIlroy S.Dorward at doug@research.bell-labs.com
=================
/* Odomontade, by Doug McIlroy and Sean Dorward - programmers for fun
   and profit in computer science research, Bell Labs, Murray Hill, NJ.
   300 bytes when reduced to blank-free 80-character lines */

int f=1023, l, m, x[1024], t[90000];
main(i, j, k)
{
	g(4,0,0,0);
	g(6,f=0,0,0);
	for(f = fopen(1[(int*)j], "r");
	    i = fscanf(f, "%d", &l) > 0;
	    vprintf("%d %d\n", t+j%m))
		for(j=m; i t[k = i+j>>2<<1]?
				i = k+2
				:(j = k);
}
g(n, v, z, d){
	if(n)
		for( ; d<10; d++)
			z&1< l?
			t[m++] = l = n,
			t[m++] = v
			:0
	;
}

/*
The method is to generate all possible answers - a table of final
odometer readings and reset values - then look up the answers by
binary search on reset value.

Why precompute answers for 10!/4!=151,200 different mileages, when we
will only be asked 1000?  Because we don't know a good way to find the
next achievable final odometer reading.  The odometer may have to pass
as many as 246 all-digits-different mileages before reaching an
achievable one.  (Only 42171 are achievable.)  Thus a fiendish potm
master could set 1000 problems that caused us to consider 247,000
different mileages.  Betting that the potm master is not benevolent,
we arranged for our run time not to depend on his problems.  (This was
a delicious speculation - how many other entries would take several
times as long per problem for 10 times as many problems in the finals
vs the preliminaries, while our time scarcely increased?)

g(n,v,z,d) generates in lexicographic order permutations of digits
0..9 taken n at a time.
	d is a candidate for leading digit.
	v is numeric value of string of decimal digits.
	z is a bit mask giving the set of digits in v.
The loop in g tries digits in increasing order, checks (by testing
z&1< l) {
		t[m++]=l=n;
		t[m++]=v;
	}
	m is the table index.
	v is the final mileage.
	l is the previous final mileage.
	n is the reset mileage.


LOW CUNNING TO SAVE CODE

Table-update code is executed in g at all recursion levels, not just
the final level where it's needed.  In the first phase, this makes
entries in table cells that will never be used.  In the second phase,
the code to guard against unreachable final mileages happens also to
guard against updates at other levels of recursion.

Vprintf is supposed to be used in connection with va_args to index
arguments one at a time in a printf-style argument list.  The
misuse here to print two values from only one printf argument
happens to work on Suns.  That argument, t+j%m, also handles
odometer wraparound.

Tricks to save or shorten declarations
	omit header files
	use old-style function definitions
	reuse variables
	eschew non-int variables; mistype non-int as int
	use parameters, not local variables

Because table t has two-word entries, the binary search indexes the
low and high pointers, i and j, by two.  i is initialized not to 0
but to 1 (the return from an unrelated test!), but this off-by-one
error washes out when i+j is divided by 4 in the binary search.

Savor the benefits of addressing argv[1] thus: 1[(int*)j].
Also the multiple uses of f
	flag to distinguish first from second phase (f?)
	mask for doing set complement (x[z^f])
	test-free way to set argument of g conditionally (f&d)
	stdio file handle (f=fopen(...))


Plus all the usual coding tricks:

	embedding assignments in funny places, like argument lists,
	subscripts, and for statements, sometimes to avoid
	semicolons, sometimes to grab available values.

	using comma expressions to avoid {} brackets.

	using conditional expressions instead of if: || for 1-way;
	?: for 2-way.  For example, binary search becomes a
	"one-liner":
                for(j=m; i t[k = i+j>>2<<1]?
                                i = k+2
                                :(j = k);
*/
=================================================================

============== 20 ====================== The_first_try =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
     The_first_try      1879997    438    394     44 125  Rolandas Gricius
=================
The_first_try was submitted by Rolandas Gricius at 
lanteka.lt!rolandas@caig1.att.att.com
=================
++ Please summarize the algorithm used by The_first_try

  That's simple: take as basis miles entered, then calculate miles at
the end, and then - miles travelled, increasing every digit while  -  <= .
 
++ What kind of tricks did The_first_try use to minimize code length?

  Almost none. Standard ones are - one letter variable names, no
variable types in function declarations, freopen(..., stdin), you know,
they are standard ones.
 
++ Here's what I hated (and loved) about this POTM's scoring:

  Very difficult to predict impact of speed differences between my and
test machines, complicated by different test (100 entries) and actual
(1000 entries) runs. (I hated it, of course). 
 
++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

  UAB "Lanteka", Klaipeda, Lithuania. We are running three person ISP,
I'm the main UNIX administrator, programmer, consultant for leased lines
installation, etc. Secret? I almost hate computers sometimes. POTM
ideas? I have some. But not now :)

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

============== 21 ====================== eyes-on-the-road =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
  eyes-on-the-road      1879997    443    331    112 87  Clive Dawson
=================
eyes-on-the-road was submitted by Clive Dawson at Clive.Dawson@amd.com
=================
++ Please summarize the algorithm used by eyes-on-the-road

	The basic algorithm was simple:  

	Using the starting mileage (m), compute the next possible mileage
	that consists of unique digits (x).  Use the 4 leftover digits for
	the trip odometer (t).  Now check whether x-t >= m.  If so,
        this is a valid solution.  Otherwise, go back and compute the
        next higher value of x.

	I used a refinement to this algorithm which speeded it up considerably:
	Solve the problem by assuming that the rightmost n digits of both
	odometers don't exist, for n decreasing from 3 to 0.  This allows
	the more significant digits to be determined more quickly, cutting
	down on the number of times we need to iterate in the basic loop.

	Another significant speedup was obtained by using a precomputed
	array of powers	of 10.  This allowed much faster extraction of 
	individual digits.  The alternate approach of working with
	individual digits to begin with seemed to be a losing proposition,
	since you would then have to worry about doing your own arithmetic.
	(But given the vastly better performance of the winners, I'm
	beginning to have second thoughts about this!)

	Finally, I'm guessing that most everybody realized that you didn't
	have to worry about wrap-around on the odometer.  This was taken
	care of by just making sure that your answer was printed modulo
	1000000.


++ What kind of tricks did eyes-on-the-road use to minimize code length?

	Nothing particularly spectacular.  It was just a matter of trying
	various styles of loops and if statements to see which would be
	shorter.  Of course you want to take maximum advantage of compound
	statements, and creative use of the initialization, test, and 
	increment portions of 'for' loops.

	At one point I switched to gcc, since it allows end of line
        characters in literal strings.	I tried to make the ends of
        lines coincide with the places where a blank was required.

++ Here's what I hated (and loved) about this POTM's scoring:

	I didn't like the fact that we were left in the dark regarding
	specific scores.  Certainly knowing that somebody had succeeded
	in one third the time, or had a program which was half as long
	would have motivated me to try harder.  I think knowing more about
	what we were up against would have contributed to an overall
	improvement in the quality of the submissions.

	Another interesting aspect was that the tradeoffs made between
	execution time and program length depended on the speed of your
	computer, not mine.  This wasn't bad or good; just interesting.

	One last bothersome aspect of this POTM was that since we didn't
	know the contents of the input file or how it was generated, 
	it was hard to tune the algorithm.  If you had told us that the
	test file would consist of 1000 random numbers between 0 and 
	999999, my program might have been very different from one designed
	to perform best on the "worst cases" which might have been
	specially chosen.


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

============== 22 ====================== tracks =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
            tracks      1879997    454    372     82 131  =Franz Korntner
=================
tracks was submitted by Franz Korntner at korntner@xs4all.nl
=================
++ Please summarize the algorithm used by tracks

The algorithm is generally described as:

Calculate an array containing 4 digit numbers where the digits are in
ascending order. The array in indexed by bitmapping ie. the number 2456
has an index of 1<<2|1<<4|1<<5|1<<6.

Then for all 1 million 6 digit numbers, calculate the bitmap (as
described above) and find the matching 4 digit number in such a way that
the OR'ing of both bitmasks result in all 10 bit positions being set. If
a number combination has been found, then the 6 digit number will
represent the final milage and subtracting the 4 digit number from the 6
digit number will represent the starting milage.

Given a certain starting milage, it is sometimes wiser to wait a bit
longer before pressing the reset to get a better end position. To catch
this, the found starting milages must be in ascending order for them to
be accepted/processed.

This operation will create a list of starting positions and 'trip
lengths' where the starting positions are in ascending order. The list
will be 42171 combinations long.

Finally for each number in the input list will be searched using a
binary search method, displaying the milage when the reset button should
be pressed, and the milage to wait before the result is achieved.

++ What kind of tricks did tracks use to minimize code length?

Put all variables in registers for speed, and use a macro for the 10
used for loops.

++ Here's what I hated (and loved) about this POTM's scoring:

I hated not knowing the scores of the other contestants, because it
gives no indication on how well the entry actually is, it just tells you
that all solutions are correct, nothing else. If I knew that first place
was an entry 140 characters smaller than my 372 character entry, I would
have taken a very different approach and not concentrate on speed
issues.

 ++ COMPANY? ICT Netherlands. (www.ict.nl) which is a dutch contracting company
 LOCATION? Holland
 JOB? Contractor, specialized in low-level concepts ie. OS, compiler,
debugger, library, encryption, compression, TCP/IP, device drivers,
parallel processors.
 DO FOR FUN? POTM
 INNERMOST SECRET? Well, actually I --CENSORED-- about it.


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

============== 23 ====================== JustOnce =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
          JustOnce      1879997    475    439     36 23  Bob Lied
=================
JustOnce was submitted by Bob Lied at lied@lucent.com
=================
++ Please summarize the algorithm used by JustOnce
	Choose digits beginning from the most significant.  As each
	digit is chosen, form the largest possible number that will
	complete the odometer, and the smallest possible number that
	will fill the trip meter.  Then check that the constraint that
	the chosen digit will create an odometer reading in range:
		InitValue + TripMeter < Odometer + BiggestPossible
	Continue to choose the next smallest available digit until
	the constraint is satisfied.

	The weak part of this algorithm appears to be forming the smallest
	and largest numbers, which were the most expensive parts both in
	program size and execution speed.	

++ What kind of tricks did JustOnce use to minimize code length?
	Unreadability -- no white space, single-character variables,
		reuse of variables, no functions
	Side effects -- ++/--, comma operator, embedded assignment,
		coincidental calculation of values needed later
	Control flow -- only while loops, goto
	Correctness proof -- no bounds checking on loops because they were
		known to terminate, elimination of special cases

++ Here's what I hated (and loved) about this POTM's scoring:
	Never quite knowing whether speed or size could make a difference.	

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
	COMPANY:  Lucent Technologies
	LOCATION:  Naperville, Illinois, USA
	JOB:  software dilettante
	FUN:  basketball, classical guitar
	SECRET:  haven't produced a line of production code in three years
=================================================================

============== 24 ====================== rollback =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
          rollback      1879997    475    325    150 114  Warren Montgomery
=================
rollback was submitted by Warren Montgomery at warren@psp.ih.lucent.com
=================
++ Please summarize the algorithm used by rollback
Brute force, try each odometer reading starting with the given
mileage looking for a solution and stopping at the first one.  3
tables were built in advance to speed things up:  A mapping from 3
digits to a bit code (sum of 2^digit for each digit present) for
each 3 digit number with unique digits, an inverse mapping from bit
codes to lowest 4 digit number with remaining 4 digits for all bit
codes with 6 bits on, and a table giving the next higher 3 digit
number with unique digits for each one, allowing many impossible
numbers to be skipped.

++ What kind of tricks did rollback use to minimize code length?
Abusive (typeless) programming, comma expressions, ? expressions,
and a #define for a repeated loop.

++ Here's what I hated (and loved) about this POTM's scoring:
Combination of time and size was nice.  Standings should have either
given both time and size, or been based on the same number of
numbers as the finals.  The quirks of the POTM test machine
(e.g. lack of hardware multiply/divide, odd cache effects, no
optimization) make it very difficult to predict the space/time
tradeoff without seeing it perform under actual conditions.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
I work for Lucent/Bell-Labs in Naperville Illinois on Intelligent
Network Architecture.  I enjoy puzzles, and POTM is a pretty good one.

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

============== 25 ====================== odododo =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
           odododo      1879997    501    412     89 86  Bob Ashenfelter
odododo was submitted by Bob Ashenfelter at ash@att.com
=================
++ Please summarize the algorithm used by odododo

    The digits of the final odometer reading are computed one at a time
    starting with the most significant which is initially set to the
    corresponding digit of the starting odometer reading.  The remaining
    digits are sorted into the remaining odometer digits, highest to the
    left, and the last four smallest digits are sorted into the trip
    odometer, highest to the right.  The result is the final readings
    when the reset is pushed at the very latest point that leaves the
    initial value in the most significant digit.  Compute the mileage
    at reset by subtracting the trip odometer from the total odometer.
    If this is at or beyond the starting value, go on to the next digit.
    If not then the initial digit cannot possibly be right.  Increment
    it (mod 10) and try again.

    Subsequent digits are initialized to either the corresponding digit
    of the starting odometer reading or, if it had been necessary to 
    increment ANY previous digit, to 0.  (It is easier to just set all
    subsequent digits to 0, but the cost in extra execution time is more
    than the savings of 8 characters.)  Then the remaining digits are
    sorted and the reset is tested as above.  This continues until all
    six odometer digits are determined and then the answer is printed.
    
++ What kind of tricks did odododo use to minimize code length?

    These are all pretty obvious:
	* Use one-character variable names.
	* Use as few variables as possible, reusing them wherever possible.
	* Use pointer notation instead of array notation wherever it is
	  more concise.
	* Use "," to terminate statements (except the last) in a block
	  instead of ";" and then remove the "{}".
	* Move statements from the body of "for" loops into unused control
	  expressions and save the ";"s.
	* Remove all extraneous white space.
	* Use "#define" for repeated character sequences.  (I could only use
	  it once, for "for (", and it saved only a couple of characters.)
	* Use a new-line for unavoidable white space if it keeps line lengths
	  within the 80-character limit.

    Perhaps my most creative trick was to use a single array for both the
    final odometer digits and the trip odometer digits with the trip odometer
    digits reversed so only a single sort was needed for both.  And then I
    padded the array with two additional digits which were never changed
    from their default initializations of 0.  These extended the trip odometer
    to six digits and simplified the subtraction to obtain the reset mileage.

    Another cute trick was to reuse the "argc" and "argv" arguments of main().
    Of course I called them "c" and "v".  Even though the initial value of "c"
    was not used and it was not declared, it defaults to "int" and was sub-
    sequently used as such.  When I reused "v" as a pointer to an array of
    integers, the compiler complained bitterly.  So I lied to the compiler
    and declared it "int*v;" instead of "char**v;".  Not only was the compiler
    deceived (not even a whimper), but I shortened the code by two characters
    as well!

++ Here's what I hated (and loved) about this POTM's scoring:

    If you, or anyone else, expect me to complain about the encouragement
    of bad programming style, sorry..., I have no problem with that.

    The following is neither love nor hate--just a comment.  The score for
    time was too small in comparison with the score for size.  At the time
    this was determined you probably expected them to be comparable, but you
    really had no idea how efficient the best programs would be.  Perhaps
    you should have left this to be determined later, say by increasing the
    number of input values until the winning program scored equally for both
    time and size.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

    AT&T ... until they sell us out--I'm in Submarine Systems.
    Holmdel, N.J., U.S.A.
    Circuit design.
    Bicycling, sailing, grow orchids, travel.
    No way...
    You could publish the winning entry of this POTM as the problem for the
    next POTM.  First one to figure out what it does is the winner.
=================================================================

============== 26 ====================== outofgas =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
          outofgas      1879997    508    331    177 41  Matthias Ruhl
=================
outofgas was submitted by Matthias Ruhl at ruhl@informatik.uni-freiburg.de
=================
++ Please summarize the algorithm used by outofgas

The program starts with the current meter and iteratevly computes the next
meter setting with 6 different digits. If the smallest number that can be
built from the four remaining digits is smaller than the difference of the
this and the original meter setting, we are done. Otherwise continue.

The tricky part is obviously to determine the next meter setting where all six
digits are different. This is done by going from the highest value position to
lowest value position and checking each time whether the digit at that position
already occurred (to the left of it). If it has, then 
 a) zero all digits to its right
 b) repeatedly increase the digit by one until it
    1. hasn't occurred before. Then we continue with the next position.
    2. it is increased to 10. In this case, the overflow must be propagated
       to the next higher position, where the loop begins again.

To avoid handling the special case where the meter turns from 999999 to 000000,
all meter settings greater than 987531 (=987654-123) are mapped to 000000 at
the beginning of the program.

++ What kind of tricks did outofgas use to minimize code length?

Only 'garden variety' C-code shrinking (reusing variables, shortening
expressions, etc.) - nothing really problem specific. And not a single 
'#define' :)

++ Here's what I hated (and loved) about this POTM's scoring:

The scoring system itself (length+time) was, well, interesting :) 
But I think it would have been even more fun if the actual scores had been
distributed with the ranklist.
The scoring method may also put people who have access to a Sparcstation at a
slight advantage, since the tradeoffs between speed and (code) length are
often quite counter-intuitive and also very machine-dependent.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

I'm an undergraduate student majoring in Maths and CS at the University
of Freiburg, Germany, and will be graduating in summer 1997.
So hopefully I'll then have some more time to spend on a future POTM :)
=================================================================

============== 27 ====================== dodo =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
              dodo      1879997    556    510     46 93  Jeroen Moelands
=================
dodo was submitted by Jeroen Moelands at moelands@nlr.nl
=================
++ Please summarize the algorithm used by dodo
I use arrays of 10 bits that tells which digits are already used
as integer indices to two arrays. One array contains the trip odometer
standing, which consists of the four lowest digits that are not used yet,
lowest digit first. The other one contains the highest possible value that can
be made with the unused digits. These arrays are filled first.

To avoid the wrap-around stuff, if the odometer has a value
higher than a certain maximum, I print the lowest milage possible.

For other odometer standings, a simple backtracking algorithm is used that
finds the minimal odometer value without much backtracking, using the two
arrays. The algorithm creates the odometer number from left to right. If the
entire number is found, it is printed. Otherwise, the lowest possible digit
is 'added' to the odometer number "head"; if the resulting number 'plus' the
highest possible "tail" to form 6 digits is greater than or equal to the given
odometer standing 'plus' the lowest possible trip odometer standing, try to
'add' the next digit (the highest standing possible to create with the given
"head" must be at least as high as the given standing plus the lowest possible
trip). If no digits are possible, backtrack. In this way the odometer standing
is found without much backtracking.

++ What kind of tricks did dodo use to minimize code length?
Tricks? Just spent a *lot* of time.

++ Here's what I hated (and loved) about this POTM's scoring:
Creating a fast program is a lot more fun than creating a small one.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
I work as a Software Engineer at the National Aerospace Laboratory (NLR) in
Amsterdam, Holland. 
=================================================================

============== 28 ====================== Close_Enough =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
      Close_Enough      1879997    557    354    203 53  Vance Heron

	Sorry ... no description available for Close_Enough

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

============== 29 ====================== Hoovey =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
            Hoovey      1879997    562    312    250 128  A.Halverson J.Halverson
=================
Hoovey was submitted by A.Halverson J.Halverson at alanh@microsoft.com
=================
++ Please summarize the algorithm used by Hoovey

We used a 6-element array of integers to represent the digits of the
odometer.  To determine uniqueness, we employed a bit-field in which
bits were set if a digit was used in the main odometer.  We proceeded
left to right (most significant to least significant digit).  By
right-shifting 1 "current digit" times, we arrived at a unique bit in
the bit field.  If the bit was already set, increment the current digit
and zero out all less sig digits.  As soon as you found a digit not
already set in the bitfield, set it and move on to the next digit.  If
you roll a digit (9 -> 0), you have to remove the previous digit's bit
from the bitfield and increment it.  Once all six digits were found to
be unique, it was trivial to construct the trip odometer by testing bits
in the bitfield, LSB to MSB.  If bit j wasn't set, multiply the trip
odometer by 10 and add j.  This method guaranteed the smallest possible
trip odometer.  Finally, just subtract main odometer from trip odometer
and test against input odometer reading, looping back if the test
failed.

++ What kind of tricks did Hoovey use to minimize code length?

We used "#define W while(" - every loop in our program was a variant of
the while loop.  Also, the comma sequencing operator came in very handy
("f=x,y=j;" instead of "{f=x;y=j;}").  Another good one - define argv as
int*argv instead of char**argv.  This works because
sizeof(int)==sizeof(char*).  No #include files.  No functions other than
main().  Of course, getting rid of that pesky whitespace helped as well
... %^)

++ Here's what I hated (and loved) about this POTM's scoring:

Having code size share importance with speed of execution is a bummer.
Maybe if speed was worth 2/3 and code size 1/3 in the second tiebreaker.
 Maybe I'm just complaining because I don't have enough experience
writing unreadable C code ...

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM
IDEAS?

Company:	Microsoft Corporation
Location:	Redmond, WA
Job:		Quality assurance for a "popular database product"
Fun:		Music - play, sing, listen
Secrets:	You can't have any when you're married ... %^)

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

============== 30 ====================== gdrula =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
            gdrula      1879997    597    471    126 124  Catalin Drula
=================
gdrula was submitted by Catalin Drula at gdrula@pcnet.pcnet.ro
=================
++ Please summarize the algorithm used by gdrula
If "a" is the initial number, I considered all the numbers starting
with "a" that have all the digits different.
With the left 4 digits I formed the smallest number "c".
If the difference between the current number and the initial number
is less or equal than c, than the current number is the number
we're looking for.
That's all.
++ What kind of tricks did gdrula use to minimize code length?
Not many.The usual C syntax + flags...
++ Here's what I hated (and loved) about this POTM's scoring:
I think the code length has too much importance in the score:
Wouldn't something like: 5*time+length have been better?
I like that you send the weekly status and nobody knew the other
contestants scores. 
++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
I learn at Bucharest High School of Computer Science.  
I live in Romania and I'm 15.  
Yes, I do it for fun.
In future I think you should give more difficult problems.
The algorithm should count more than some tricks to make the source
shorter.
If possible don't use the source length in the score. 
Thanks for what you do,

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

============== 31 ====================== shortcut =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
          shortcut      1879997    614    327    287 58  Jan Venema
=================
shortcut was submitted by Jan Venema at jvenema@lucent.com
=================

++ Please summarize the algorithm used by shortcut
For each A1 on input:
a) Start with A2 = A1.
b) Check if all 6 digits in A2 are different.
c) If different, then calculate B2 by using the remaining 4 digits. 
   Check if B2 <= A2-A1 then print A2-B2, A2 and continue with next A1 input.
d) Else, increment A2 with 10^n (depending on digits used) and restart at b).

++ What kind of tricks did shortcut use to minimize code length?
- Roll over is prevented by starting A2 as 0 when A1 > 987531.
- Use gcc compiler since it is forgiving and makes correct assumptions when
  C input is incomplete (e.g.: no #includes used, direct parameter access from
  main(), no 'int' declarations needed, any pointer can be used for fopen() and
  fscanf() file parameter).
- Use a recursive algorithm: 6 deep recursion level, one for each digit in A2.
- Take advantage of priority ordering where possible, so fewer '()'
- I used a small program to reduce variable name length, remove spaces etc.

++ Here's what I hated (and loved) about this POTM's scoring:
To solve the POTM it was inevitable to write a second program that ensures
smallest possible code size.
Some hacking was required: how are parameters passed to main() program, and
to what extend can one fool passing of parameters to library functions.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
Systems Engineering, Lucent Technologies in Huizen, the Netherlands.
jvenema@lucent.com

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

============== 32 ====================== turtle =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
            turtle      1879997    659    392    267 38  Didier Barzin

	Sorry ... no description available for turtle

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

============== 33 ====================== odor =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
              odor      1879997    667    313    354 98  Edwin Berlin

	Sorry ... no description available for odor

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

============== 34 ====================== What_A_Trip =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
       What_A_Trip      1879997    668    429    239 25  Robert Morrison

	Sorry ... no description available for What_A_Trip

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

============== 35 ====================== bitsrock =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
          bitsrock      1879997    669    551    118 116  Pete Demoreuille
=================
bitsrock was submitted by Pete Demoreuille at pbd@gate.cybernex.net
=================
++ Please summarize the algorithm used by bitsrock
precalculate all valid 6 digit numbers and the digits used by
them.  also precalculate the all the lowest 4 digit numbers and 
the digits that they do not use.  then do a binary seach in the 
6 digit numbers for the first number greater than the given.  
while the differnece of the original number and the 6 digit number 
in the refrence place of the 4 digit number that does not use the 
digits in the 6 is less than the number of miles moved, try again.
else print the proper numbers.

++ What kind of tricks did bitsrock use to minimize code length?
efficiency, no redundancy by way of #defines when it would help...

++ Here's what I hated (and loved) about this POTM's scoring.
nothing.  it was pretty fair for the problem.

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

============== 36 ====================== Porsche =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
           Porsche      1879997    677    576    101 49  Michael Strauch
=================
Porsche was submitted by Michael Strauch at strauch@metronet.de
=================
++ Please summarize the algorithm used by Porsche

For every starting point [A], Porsche does the following:
a) Increase [A] until you find a point where all 6 digits are different.
Lets call this number [A2].
b) Let [B] be the smallest number containing the 4 remaining digits.
c) If ([A2]-[A]) MOD 10^6 >= [B], [A2] is the earliest point at which
ten different digits appear on the odometers, and ([A2]-[B]) MOD 10^6 is
the point where to press the reset button.
d) If ([A2]-[A]) MOD 10^6 < [B], replace [A] by [A2] and go back to step a).

How I tried to get the program fast
-----------------------------------
I used a lot of small tricks to increase the speed of the program. Here
are the main ideas:

- "Porsche" stores the mileages [A] as a vector of 6 Digits "int Dig[6]";
  when I need the mileages value, I use the expression
  (((((Dig[5]*10+Dig[4])*10+Dig[3])*10+Dig[2])*10+Dig[1])*10+Dig[0])
- Increasing of [A] is not done "one by one"; instead, "Porsche" increases
  the leftmost digit appearing twice first.
- Porsche adds "123" to the starting point before running the main
  calculation loop, because [B] cannot be smaller than that.
- Some "register" variables are declared (GCC then does some register
  optimization, even if the optimizer is not used)

I made a second implementation of Porsche, storing [A] as an "int", which
was more than 100 bytes shorter than my entry, but it needed approx. 4 seconds
more for 1000 numbers.

++ What kind of tricks did Porsche use to minimize code length?

I used an awk script to "compress" my program to a real short one:
- all comments, every empty line and all unneccessary whitespaces are stripped
  out of the text
- the lines are concatenated if they don't exceed 80 characters
- the variable and function names are replaced by short names of one letter

 
++ Here's what I hated (and loved) about this POTM's scoring:

- I think "code length" is overweighted by this POTM's scoring; letting
  the speed score be "seconds*1000" instead of "seconds*100" would
  be a much more interesting challenge (in my opinion), because you have
  much more room for inventing a real good algorithm.

- On the other hand, I never saw as many programmers as ever here at
  this contest - the problem makes it very easy to build a correct entry with
  less than 1000 bytes, and the scoring gives them all a chance to win the
  contest not by inventing a complicated mathematical solution, but by
  optimizing the code for shortness. I think, this is a very good point
  for this kind of scoring.


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

============== 37 ====================== vanb =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
              vanb      1879997    678    384    294 13  David Van_Brackle

	Sorry ... no description available for vanb

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

============== 38 ====================== thewinner =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
         thewinner      1879997    694    403    291 70  Ravi Nemlekar
=================
thewinner was submitted by Ravi Nemlekar at ravindra@airmail.hobl.lucent.com
=================
++ Please summarize the algorithm used by thewinner

Read the input number. Keep incrementing the number till all the
digits in it were unique.  The 4 digits not in the number are the
"trip" miles. If the  number - trip < input, goto incrementing.

++ What kind of tricks did thewinner use to minimize code length?

1. Removed unrequired code (like error checks, redundant code)
2. Improved the algorithm.

++ Here's what I hated (and loved) about this POTM's scoring:

Loved: Making the code faster
Hated: Making the code smaller.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
Company: Lucent Technologies, Holmdel, New Jersey
Do for fun: Meet people, action Movies, music.
Innermost secret: Motivated to do something.
POTM ideas:  Thinking...
=================================================================

============== 39 ====================== 1000000 =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
           1000000      1879997    727    561    166 105  David Wales
=================
1000000 was submitted by David Wales at david.wales@waii.com
=================
++ Please summarize the algorithm used by 1000000
In a loop : read the number in, setting up a lookup of integers used,
then, in an inner loop, check that we have a solution, else,
recursively, keep incrementing the rightmost number, doing sensible
things with the loookup on the way, until the next candidate is found
with non repeated integers. Checking for a solution is to use the
remaining four numbers in the lookup, in order.

++ What kind of tricks did 1000000 use to minimize code length?
Replace common code with function calls so long as run time didn't
increase too much. Replace code with macros, remove all blank space (
except end of lines ). Reuse variables, make all variables global, use
function parameters defaulting to int. Lots of pointer stuff.

> ++ Here's what I hated (and loved) about this POTM's scoring:
This became an obfuscated C contest. On my machine run time, for 1000
problems, is far less than code length so squashing code became a
priority. Maybe should have deducted points based on some measure of
unreadability? Alternatively could have issued a beautifier through
which all code would be crunched and do an ls -l on its result. Maybe,
if it's to be an obfuscated c contest, add a score measuring the
number of unique symbols in the code - the more the worse!?

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
Western Geophysical, Bedford UK. Software bloke.

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

============== 40 ====================== trees =============

=================================================================
            ENTRY       SCORE1   SCORE2 = CHARS+HSEC AGE  PROGRAMMERS
             trees      1879997    730    436    294 37  Dave Lynch
=================
trees was submitted by Dave Lynch at dflynch@att.com
=================
++ Please summarize the algorithm used by trees
	Increment the odometer until all digits are different.
	Permute the remaining 4 digits to get the trip odometer.
	If I haven't traveled this far, go another mile and repeat.

++ What kind of tricks did trees use to minimize code length?
	Just the obvious.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
	AT&T
	Holmdel, NJ
	Write software to design data networks.
	Stay away from work.
	Secret.












Make your own free website on Tripod.com