The 232 character winner ... compiles with the GNU
C compiler - the shortest entry and the overall winner!
from William Burley and Arthur Goldstein at jolt!wburley@ffast.ffast.att.com
d,r,i,v,e,L;*_;main(a,b){for(L=fopen((_=b)[1],"r");*_=fscanf(L,"%d",&v,e=1e6
)>0;printf("%d %d\n",r,r+d))for(memcpy(b+4,b,d=123),v*=v<=(r=987531);e;_=(a=
r-(e-i)*_[*_])< v?*_+=_[*_],i=e/=10,b:(r=a,_+*_))i*=i<0?d-=i**_,10:i-1?.1:-1;}
(note - space added on last line so that HTML would show entire line)
The annotated version with notes follows:
driveL
William Burley and Arthur Goldstein
Algorithm summary
-----------------
For each input mileage, we start with the odometer = 987654 and the trip
odometer = 0123. For each position of the odometer, from left to right, we
determine the smallest unused digit that fits in that position. This is done
by swapping the digit currently in that position with the next smaller unused
digit as long as the following invariant is kept - that the current reset
mileage (which equals the odometer minus the trip odometer) is greater than
or equal to the input mileage.
A digit is available if its position has not yet been fixed. Because of the
way the swapping is done, at the time the digit for the next position is
finally fixed, the remaining (available) digits will always be in decreasing
order from left to right in the odometer followed by right to left in the trip
odometer.
As an example, suppose the input mileage is 342243. After determining
that the first two digits of the odometer are 34, the current odometer value
will be 349876 and the current trip odometer will be 0125. To determine the
3rd digit of the odometer, we swap in each smaller available digit as long as
the invariant holds, as follows:
start with 349876 0125
swap 9 and 8: 348976 0125 (348976-0125 >= 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
then
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
--------------------------------------------------------------------------------
The final version is unnecessarily obfuscated.
Replacing "_" with "p" and rearranging a bit,
and adding some comments and white space:
--------------------------------------------------------------------------------
d, /* current trip odometer */
r, /* current reset mileage */
i, /* difference amount for swap position */
v, /* input mileage */
e, /* difference amount for current position */
L, /* pointer to input file */
*p; /* pointer to "previous" element on the list of available digits (which */
/* is actually a list of the differences betweeen the available digits) */
main(a,b)
/* a - test reset mileage */
/* b - pointer to an array: */
/* b[1] is initially a pointer to the input file. */
/* After initialization, b[0],...,b[10] is used for the list of available */
/* digits. */
{
for ( p=b,
L=fopen(p[1],"r"); /* use p to avoid declaring b */
*p=fscanf(L,"%d",&v)>0; /* 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.) */
e;
a=r-(e-i)*p[*p], /* compute new reset mileage for this swap */
p= a-->