Positions 1-13

Note - program listings may not print correctly due to HTML conflicts.
86 of 131 entries returned program summaries ... THANKS!
Hope to see you all in the NEXT POTM!!!

I've divided the program summaries into four pieces of mail ...
covering the top 13 finishers, then 14-40, 41-80, and 81-131.

The mirror sites should be updated shortly ...

***  http://www.cs.washington.edu/homes/corin/POTM.PAGES/  
***  http://potm.ffast.att.com/                            INSIDE AT&T only
***  http://icds.micro.lucent.com/POTM			   INSIDE Lucent only

Thanks for participating!


RESET Program entry descriptions

		Beware of long mail .... but there ARE gems buried!
		Even if you don't study the whole thing, you might
		want to check out the first four or five writeups!

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).

There are also Code listings available on request.
  If you need even more detail - contact the authors - not ME!!!



============== 1 ====================== driveL =============

            driveL      1879997    274    232     42 102  W.Burley A.Goldstein
driveL was submitted by William Burley and Arthur Goldstein at
jolt!wburley@ffast.ffast.att.com and jolt!arthur@ffast.ffast.att.com
Here is the entire program ... an annotated version is available on
the POTM web sites (or request one by mail if you don't have web access)

)>0;printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),v*=v<=(r=987531);e;_=(a=
r-(e-i)*_[*_])= 342243 holds)
       swap 8 and 7:  347986 0125  (347986-0125 >= 342243 holds)
       swap 7 and 6:  346987 0125  (346987-0125 >= 342243 holds)
       swap 6 and 5:  345987 0126  (345987-0126 >= 342243 holds)
       swap 5 and 2:  342987 0156  (342987-0156 >= 342243 holds)

The next swap would be between the 2 and 1, but we don't do this swap
because it would violate the invariant.  Thus, we have determined that the
next digit is 2.  Note that, as stated above, the remaining available digits,
9, 8, 7, 6, 5, 1, and 0, are in decreasing order from left to right in the
odometer followed by right to left in the trip odometer.

Our implementation of this algorithm does not keep track of the odometer,
but only the trip odometer and the reset mileage.

We use an array to keep track of available digits.  We actually keep the
differences between available digits, with the first entry of the array
used as a pointer to the beginning of the list.  Initially the array is
{1,1,1,1,1,1,1,1,1,1,1}, which corresponds to the list 9,8,7,6,5,4,3,2,1,0.
To delete an element from the list, we change the value of its predecessor
to skip over it (or change array element 0 to skip over the first part of
the list).  Thus, if the array is {3,_,_,2,_,1,1,2,_,1,1} (where "_" means
the value doesn't matter), then the list of available digits is 7,5,4,3,1,0.
Keeping the list of available digits in this manner has the advantage that
when we swap two digits, the difference between the new reset mileage and
the old reset mileage depends on the difference between the digits - the
actual values of the digits doesn't matter.

For each position in the odometer and trip odometer, there is a value
that we call the "difference amount" for that position.  The difference
amount of a position tells how much the reset mileage changes when the
digit in that position is increased by 1.  The difference amounts for the
positions are as follows:

odometer:      100000  10000  1000    100    10      1
               ------ ------ ------ ------ ------ ------

trip odometer:                -1000   -100   -10     -1
                             ------ ------ ------ ------

When two digits are swapped, call the position of the first digit in the
odometer the "current position" (this is the position whose digit we are
trying to determine) and the position of the other digit the "swap position".
Thus, in the following two examples, "a" is the current position and "b"
is in the swap position.

                   _ _ a _ _ _          a _ _ b _ _
                       _ _ b _              _ _ _ _

When two digits are swapped, it is easy to compute the new reset mileage
as follows:

    let e = difference amount for the current position
        i = difference amount for the swap position
        X = difference between the two digits
        new reset mileage = old reset mileage - (e - i) * X

If the swap position is in the trip odometer, then the new trip odometer
is computed as follows:

        new trip odometer = old trip odometer - i * X

Here is the final version of the program:

)>0;printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),v*=v<=(r=987531);e;_=(a=
printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),r=987531,v*=v<=r,e=1e6;e;a=r-
(e-i)*p[*p],p=a0;    /* putting *p here sets b[0] to 1 if       */
                                   /* there's more input                      */

        printf("%d %d\n",r,r+d)

      for ( memcpy(b+4,b,d=123),   /* initialize list of available digits     */
                                   /* (this copies b[0] into b[1],b[2],...,   */
                                   /* setting b[11],...,b[123] unnecessarily, */
                                   /* but it saves characters)                */
            r=987531,              /* = 987654-0123                           */
            v*=v<=r,               /* set v=0 if it's too large               */
            e=1e6;                 /* really should be i=e=1e5 here.  This    */
                                   /* just happens to work - the first time   */
                                   /* through the loop is wasted (and b[]     */
                                   /* becomes {2,_,1,1,1,1,1,1,1,1,1,1}, so   */
                                   /* the previous description of b[] is a    */
                                   /* bit of a lie.)                          */

            a=r-(e-i)*p[*p],       /* compute new reset mileage for this swap */
            p= as+4;i=a-l<
++ Please summarize the algorithm used by POTM9609
To explain what the algorithm does, let us suppose that it has already
found the first two digits of the ending value for the large odometer
and it is searching for the third one:
    problem start value = 100109
    large odometer      10xxxx
    small odometer        xxxx
The smallest available digit is put in the third position:
    large odometer      102xxx
then, the algorithm check whether it is high enough, by composing the
highest value with those three initial digits and subtract the lowest
possible value for the small odometer:
    large odometer      102987
    small odometer        3456
The difference is 99531, that is less than the starting value: this
means that the mileage is not enough to allow the small odometer to
get to the wanted number (that is the minimum with the chosen initial
digits). Therefore, the program exchange the chosen third digit (2)
with the one immediately greater, among those not already used (3).
    large odometer      103987
    small odometer        2456
Now the difference is 101531, that is greater than the starting number:
this means that there is enough mileage to let the small odometer get to
the wanted number, i.e. 3 is the mimimal acceptable digit in that
position. Now the program shift to the next position, repeating the
    large odometer      103298
    small odometer        3456
etc.etc.   In the submitted program, this algorithm is implemented by
putting all digits as 1-byte binary numbers in an array and initializing
it to the value {0,1,2,3,4,5,6,7,8,9}, where the initial value for
the large odometer is 987654 and for the small odometer is 123. The 
algorithm just described is then executed by swapping and shifting elements
in that array.
++ What kind of tricks did POTM9609 use to minimize code length?
1) exploiting the weaknesses and tolerance of the C compiler (no
   header files, default types=int, int* to int assignment, etc.)
2) , (comma) operator whenever useful, for putting more instructions
   in a line and avoiding parenthesis; comma-separated are also 
   used in the second operand of conditional assignments (xxx?a,b,c:d)
3) careful usage of initial and final value of variables in 'for' loops
4) obviously, use of ++/-- operators.
++ Here's what I hated (and loved) about this POTM's scoring:
Not knowing the score got me nervous, but it compelled me not to give up.
COMPANY: I work as a partner in two companies: BLUESOFT and I.S.& O., the
first one making (mainly) PC-based software, the second one system 
integration and engineering for large accounts.
JOB:      System architect / engineer, consultant.
DO FOR FUN:  Reading, skiing, caring of my daughters and... programming.

============== 3 ====================== Spinner =============

           Spinner      1879997    309    268     41 82  Alex Popiel
Spinner was submitted by Alex Popiel at popiel@rintintin.Colorado.EDU
Note - expanded code is available on the web sites.  Alex's entry was:

main(a,v,b,c,i,z)int*v;{for(i=fopen(v[1],"r");~fscanf(i,"%d",&a);printf("%d %d

++ Please summarize the algorithm used by Spinner

In the course of the contest, I used three different algorithms
for Spinner.  In the beginning, I started with a simple counter
that ran through the successive odometer readings, looking for
ones that had all digits different and had a valid trip-odometer
value.  My second algorithm used ordered permutations to find
only mileages with all digits different, and again these were
successively tested until a valid solution was found.

My final algorithm was much different from the above. Instead of
testing multiple mileages for appropriateness, my final algorithm
builds a single mileage digit by digit such that it is guaranteed
to be a valid solution.  This is rather faster than the successive

Spinner starts by adjusting the input number to prevent odometer
overflow.  It next initializes a sorted pool of all available
numerals (initially all of 0 through 9 inclusive).  For each digit
in the destination mileage (working left to right), the lowest
value numeral which can produce a valid solution is picked.  The
validity is checked by building the highest value odometer reading
possible with that numeral in place, and subtracting off the
lowest value trip-odometer reading built from the remaining four
numerals; if the resulting number is not less  than the input number,
then the numeral picked for the digit in question is valid.  Each
digit of the destination mileage is filled in this way, until a
complete solution is found.  (As a note: having a sorted pool of
available numerals makes building the highest possible odometer
reading and the lowest possible trip-odometer reading _much_
easier; just read an appropriate number of numerals off each
end of the pool.)

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

Spinner uses many tricks to minimize code length:

1) Use K&R-style function declaration to avoid specifying the
   return type of main(), and the type of its parameters.

2) Put all int variables in the parameter list for main(), so
   their type does not have to be explicitly specified.  (Note:
   this will cause some implementations to core dump through
   trashing the stack.  In that case, put the int declarations
   in global scope, still leaving off the 'int' keyword.)

3) Use the comma operator to avoid need for compound blocks.

4) Use the memory space guaranteed available in argv instead
   of declaring an array.

5) Use for loops instead of while loops, and pack stuff into
   the expression_1 and expression_3 sections of the for loop
   instead of having compound blocks within the loop.

6) Use side effects in the expression_2 part of the for loops.

7) Don't #include anything.

8) Use operator precedence to eliminate parentheses.

9) Use pointer arithmetic on pointers to different size types,
   knowing the sizes of the various types, to reduce offsets
   of 12 to offsets of 3.

10) Use only implicit type conversions.

11) Don't initialize variables if their values don't matter.

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

I would have liked to see the full scores of everyone in the
weekly updates.  (I just had to say it...)

I would have preferred a token-counting size measurement instead
of the character counting measurement.  (Problem: what constitutes
a token in a perl/sed/awk regex?)


In order: No.  SF Bay Area.  Consultant for hire.  Think, code,
play games.  I'm not real.  Interference pattern simulators.


============== 4 ====================== potm_miles =============

        potm_miles      1879997    312    263     49 109  Alexey Zhelvis
potm_miles was submitted by Alexey Zhelvis at lesha@mcs.spb.su
A=2;f=9999;F(1);printf("%i %i\n",f-b,f);}}
++ Please summarize the algorithm used by potm_miles

I am constructing 6-digits numbers with all different digits,
then I calculate the lowest possible value of the second
odometer, and then I compare start value + value of the
second odometer with the 6-digits number I have constructed.
When this number is greater, I stop and print result.
In order to search faster, on first steps I am changing
the highest digits, assuming the lowest are all 9.

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

I replaced some "if" statements with ? : operator, some "if" statements I
replaced with || operator in order to execute second expression with
side-effects only if the first expression is false.


I am working as a programmer in Marine Computer Systems,
Jont British-Russian venture, located in Saint-Petersburg, Russia.


============== 5 ====================== alphabet_soup =============

     alphabet_soup      1879997    316    240     76 46  =Andre' Wilhelmus
alphabet_soup was submitted by Andre' Wilhelmus at wilhelmus@lucent.com
Here is the entire program ... an annotated version is available on
the POTM web sites (or request one by mail if you don't have web access)

"%d %d\n",e-r,e))for(s*=s<987532;u--&7;m=--m*10)for(b=4;b+=b;b&u?n(u^=b,9),n(4,

++ Please summarize the algorithm used by alphabet_soup
	The summary is longer than the whole program. ^_^
	If the start mileage causes the meter to go through zero then
	  the start mileage is bumped to zero.
	A bit field of unused digits is maintained.
	The end mileage is assembled digit by digit from left to right
	  with increasing digit values until 'end - reset >= start' is true.
	The end mileage is completed with unused digits from left to 
	  right and high to low.
	The reset counter is assembled with unused digits from left to 
	  right and low to high.

++ What kind of tricks did alphabet_soup use to minimize code length?
	Well, I wanted to rename alphabet_soup to "%d% d\n" to save 
	  7 characters but the POTM master does not like spaces, 
	  let alone a real linefeed. ^_^
	Break all the portability rules.
	Collapse two variables into one twice.
	Use a bit field instead of an array.
	Keep the for(;;) expressions filled.
	Avoid commas in for(;;) expressions.
	Avoid if.
	Use a function.

++ Here's what I hated (and loved) about this POTM's scoring:
I hate not seeing my and the other scores.

++ COMPANY? Lucent Technologies.
++ LOCATION? Hilversum, The Netherlands.
++ JOB? Application programmer.
++ DO FOR FUN? Trying to learn Japanese.
++ INNERMOST SECRET? I feel obfuscated. ^_^
++ POTM IDEAS? Something simpler next time, please. ^_^


============== 6 ====================== Mercedes =============

          Mercedes      1879997    330    261     69 62  Harm Jetten
Mercedes was submitted by Harm Jetten at hjetten@lucent.com
a[10],s,t,m;g(n,i){for(t=m=i=0;i<6;i++)t=10*t+a[in==t-m0;printf("%d %d\n",l-s-c[m],l-s))for(m=0,l=s*=s<987532,g=1000000;g/=
10;s-=x,m=n)for(v=s>0?s/g:0;m==(n=m|1<0;printf("%d %d\n",l-s-c[m],l-s))
    // go through each odometer digit starting with the most significant
    // shortcut wrap around large readings
      // shortcut first guess if s is positive
      // incrementally guess until a large enough number is found
      for(v=s>0?s/g:0;m==(n=m|1<= [A1] ==> [A2]=2..... is o.k.

  Second digit of [A2]:
  [A2]=21....(*)   worst case:  [A2]=219876
  [B2]=  ....                   [B2]=  0345
                                 [C]=219531 >= [A1] ==> [A2]=21.... is o.k.

  The same is repeated then for the third digit: [A2]=213... is o.k.
  Fourth digit: [A2]=2130.. rejected because [C]=208531<[A1];
                [A2]=2134.. o.k.
  Fifth digit:  [A2]=21340. rejected, [A2]=21345. o.k.
  Sixth digit:  [A2]=213450 rejected, [A2]=213456 o.k. with
                                      [B2]=  0789, [C]=212667>=[A1]

  (*) Here note, that I begin with [A2]=21.... instead of [A2]=20.... as
      in the description above. That is becase 20....<212000 despite
      the yet unknown digits, and not testing such cases extra made
      the program some hundredths of seconds faster (about 0.20 secs
      on average for the 1000 numbers on Fred's machine) by making the
      code about 15 chars larger.

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

  Huh! Too man too small tricks to tell about every one of
  them, or to call one or the other more important than
  the others. In general, I mostly tried not to compute
  something two times (in my first version I had to compute
  even [B2] twice, which saved me over 40 chars after changing
  it), to use as few parentheses and keywords as possible
  (by putting once two 'for'-loops together I had both of them:
  I saved the one 'for', the parentheses, and also the brackets
  for another for, making the code again about 7 bytes smaller...
  from that comes also the name 'forD' as I could 'D'elete one

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

  In the beginning I actually didn't like that there were so
  few input-lines, so that the code length was very important.
  But with time I liked it, being happy for just one or two
  bytes I could save here or there.
  But I still think it would be better, if you would show in
  the system-tests also the code-length and times of the
  other programs, as one would try harder having a 'target'
  instead of 'just do the best you can and see if you move
  up the list next week!' (not complaining, just an opinion ;-) )


  I am from Greece (the best greek entry if you didn't notice; two
  greek entries in the top-ten !!! :-) ) and making now my PhD
  in electrical engineering (neural networks) in the Technical
  University Munich (Germany).
  For fun I like computers (programming, linux, internet),
  travelling, taking photos (the last two can easily be combined :-) )
  and developing photos (black and white... just started with that
  one... still a beginner).
  Innermost secret ????? I thougt it was secret... It is so
  secret, that I even don't know myself.
  I would also like to thank you, Fred, for the nice contest
  you organize, and I am looking forward for the next problem.


============== 10 ====================== 14theRd =============

           14theRd      1879997    349    291     58 27  Happy Hacker

	Sorry ... no description available for 14theRd


============== 11 ====================== metritis =============

          metritis      1879997    349    304     45 129  Apostolis Dimitromanolakis
metritis was submitted by Apostolis Dimitromanolakis at apdim@hol.gr
++ Please summarize the algorithm used by metritis
The algorithm proceeds from the left to the right guessing each digit correctly
for the 6-digit odometer. We always start with 987531. After each step we
subtract 10^(digit-place-1) and a value choosen from the set
{-10000,-1000,-100,-10,-1,1,10,100,1000,10000} (starting with the first number
and proceeding to the right after each step). Note that this value does not
change for used digits but it IS subtracted. The rest is a bit complicated...

++ What kind of tricks did metritis use to minimize code length?
Many, but the most important are one-digit variables and common expression
elimination. (well I'm not a C expert, I learned C a few months ago)
++ Here's what I hated (and loved) about this POTM's scoring:
It was fun trying to make a small unreadable program, but the execution machice
was SLOW ( same speed as my old 386DX/40 ).

Greetings from Chania a small town at the island of Crete in Greece. I think
that I'm too young to have a real job but I take care of a unix server for an
ISP. What I enjoy to do is: electronics in general, microcontroller
programming, C/C++ and Linux (over all)...


============== 12 ====================== big-n-slow =============

        big-n-slow      1879997    362    287     75 95  Vladimir Schipunov

big-n-slow was submitted by Vladimir Schipunov at 

++ Please summarize the algorithm used by big-n-slow

	Recursion to iterate numbers with different digits. Precalculation
	of often used numbers (values of small odometer). Plus magic with
	digit 0 when it is on the first or second position of the input 
	number. Following statement is true:

	If N=_abcdef_ is input number, A=_ijklmn_ is value of big odometer
	and B=_xyzt_ is value of small odometer, where i,...,t are different,
	then none of a or b equals to x,y,z,t. 

	It means that if on the first or second position of N there is 0, 
	then A >= N+1234, otherwise A >= N+123. This saves up to 50% of time
	for simple recursion.

++ What kind of tricks did big-n-slow use to minimize code length?

	Reused code and variables
	Implicit declarations
	"a || b", "a ? b : c" instead of if/else
	Merging two cycles in one
	"," instead of ";" to eliminate "{}"

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

	Scoring was OK. The combination of algorithm and programming
	techniques determined the winners. There were a plenty of
	available algorithms and the problem was to pick up the right one. 

	However, I don't think it's a good idea to write in POTM_09_96
	manner more than one program in a year - it's spoiling style.	
	I did not like much the problem itself, but the competition was 
	really interesting. 

COMPANY?  		Velankani Information Systems, consultant in AT&T
LOCATION?  		Holmdel, NJ, USA
JOB?  			C++ in client/server project (PricerX)
DO FOR FUN?  		TV, PC, etc.
INNERMOST SECRET?  	Not at this time
POTM IDEAS?		What about short-term problems? Or several at once?


============== 13 ====================== fourfor =============

           fourfor      1879997    378    264    114 12  =Julius Collins
fourfor was submitted by Julius Collins at jpc@esun.ho.att.com
++ Please summarize the algorithm used by fourfor
precompute "minimum 4-digit values of unused digits" array
  e.g. m4dvud[{0,2,6,7,9}] is 1345.
  in the code, this is more like m[(1<<0)+(1<<2)+(1<<6)+(1<<7)+(1<<9)] = 1345.
/* the following ignores wraparound from 999999 to 000000 but easy to handle */
for each input:
  set g /* current guess */ = input
  for(k=1;k<=6;++k) /* actually implemented by (d=100000;d;d/=10) */{
    if(k'th digit of g matches an earlier digit
    || (input + m4dvud[first k digits of g])
		> (largest number matching g in first k digits) ) {
	reset g = 1 + (largest number matching g in first k digits)
	restart k loop
    if((input + m4dvud[first k digits of g]) > g)
	reset g = input + m4dvud[first k digits of g])
  print g - m4dvud[6 digits of g], g

++ What kind of tricks did fourfor use to minimize code length?
scratch and claw, lie about data types, avoid FILE*'s completely.

++ Here's what I hated (and loved) about this POTM's scoring:
didn't like the order-of-entry tiebreaker (but it turned out not to matter!)

AT&T HO(for now) 1E-423, software tools development/analysis.

Make your own free website on Tripod.com