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)

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