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.

/* * 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