A 268 character entry that finished in the top ten ...


from T. Alexander Popiel at popiel@colorado.edu
main(a,v,b,c,i,z)int*v;{for(i=fopen(v[1],"r");~fscanf(i,"%d",&a);printf("%d %d
",b,c)){char*k,*p=v+3,*r;for(c=10;*--p=--c;);for(a*=a<987532;k=p++,p-9< v;)
for(c=c*10+z,b=-1;b< a;b-=*p*1000+p[1]*100+p[2]*10+p[3])
for(c-=b=z,c+=z=*k,*k++=b,b=c,r=v+3;--r>p+3;b=b*10+*r);}}
Note that spaces were added to allow for proper HTML presentation.

The annotated version with notes follows:

Spinner

T. Alexander Popiel


/*
 * POTM ENTRY: Spinner
 * Author:     T. Alexander Popiel
 * Email:      popiel@colorado.edu
 *
 * Submission #12
 *
 * 268 characters
 *
 * This code written in C, as understood by GCC.  It is a
 * dialectic mix of K&R and ANSI, using whichever takes fewer
 * characters.
 */

/* For each input number, Spinner first initializes a sorted pool of
 * all available numerals (initially all of 0 through 9 inclusive).
 * It then adjusts the input number to prevent odometer overflow.
 * 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.)
 *
 * All of this is complicated somewhat by the fact I went through the
 * code a couple times, flattening it to near-assembly (gotos and all),
 * performing dataflow analysis and peephole optimizations, then flipping
 * it all back into for-loop notation.  The code is far from readable.
 * If you're trying to strip this back down to the 268 character version,
 * make sure to change the \n in the output string to a hard newline...
 *
 * Variables used in this code:
 * a : starting mileage
 * b : working milage / milage when button pressed
 * c : final mileage
 * i : input file
 * k : index pointer into digit pool
 * p : start of free digit pool
 * r : index pointer into digit pool
 * v : program arguments
 * z : digit holder
 */

main(a, v, b, c, i, z)
    int *v;
{
  /* Preconditions:
   *  a >= 2  (not used)
   *  v[1] has a pointer to the file name
   *  There are at least 12 bytes of storage available, starting at *v.
   *    (10 of these bytes, starting at ((char*)v)[2], are used.)
   */

  /* First comes the easy outer loop: handle each input line. */
  for (i = fopen(v[1], "r");		/* open the input file */
       ~fscanf(i, "%d", &a);		/* read the starting milage */
       printf("%d %d\n", b, c)) {	/* write the solution */

    /* Make a couple more variables, and initialize p to the end of the
     * free digit pool.
     */
    char *k, *p = v + 3, *r;

    /* Initialize the free numeral pool. */
    for (c = 10; *--p = --c;) ;
    /* Now the free numeral pool contains each numeral 0 - 9.
     * p is pointing to the beginning of the pool.
     * c is 0.
     */

    /* Next loop: build the final milage, digit by digit.
     * Postcondition: c contains the destination milage, and b
     * contains the button-push time that makes it work.
     * During execution, c is built up as a prefix for the
     * destination milage.  p points to the start of the numeral
     * pool (which shrinks as the digits of the destination are
     * determined).
     */
    for (a *= a < 987532;		/* prevent odometer rollover */
	 k = p++,			/* reduce the size of the pool */
	 p - 9 < v;)			/* check for 6 digits done */

      /* At this point, k points to the beginning of the remaining pool.
       * z holds some arbitrary (possibly uninitialized) value.
       */

      /* Loop: find the proper value for the next digit of the final milage.
       * Postcondition: c contains a legal prefix for the destination
       * milage, and b contains the button-push time that makes it work.
       * During loop execution, k walks through the numeral pool and z holds
       * the current guess (also the last digit of c)... all done by
       * expression_1 of the next loop.
       */
      for (c = c * 10 + z,		/* shift milage to hold next digit */
	   b = -1;			/* ensure loop gets run */
	   b < a;			/* have the right value? */
	   /* subtract trip odometer from working milage */
	   b -= *p * 1000 + p[1] * 100 + p[2] * 10 + p[3])

	/* Loop: compute maximum destination milage with current guess.
	 * Postcondition: b contains the maximal value for the
         * destination milage, given the chosen leading digits from c.
	 * During execution, r walks backwards through the end of the
	 * numeral pool, pointing to the successive digits of the
	 * maximal milage.
         */
	for (c -= b = z,		/* subtract off old guess */
	     c += z = *k,		/* add in new guess */
	     *k++ = b,			/* put old guess back in pool */
	     b = c,			/* working milage = (partial) final */
	     r = v + 3;			/* set index to end of pool */
	     --r > p + 3;		/* have enough digits? */
	     b = b * 10 + *r) ;		/* build milage */
  }
}

------- End of Forwarded Messages














Make your own free website on Tripod.com