/* The actual entry comes first - followed by the annotated code #define R return #define W while H[99],F,d,n,o,Z=10000;char*P,O[99],T[8]="1",D[4];A(c,y,n)char*y;{int t= *y++,p,j,h;W(t<58){if(!H[t]++){T[c]=t;if(c>2){j= -1;if(c>5)j=0;W(j<1){p=t-D[c-3]+j;h=0;if(p<48)h= -1,p+=10;if((n==h||c<4)&&!H[p]++){if(c>5||A(c+1,y,j))R 1;H[p]=0;}j++;}}else if(A(c+1,y))R 1;H[t]=0;}y="00000";t+=c<2&&t>56?-9:1;}R 0;}G(){d=(n=((o=atoi(O))+Z-atoi(P))%Z)>5000?Z-n:n;if(d%10<1|d<25|d>97&d<103|d>198&d<202||(d%=1000)<3||d>997)R-1;P=D+4;W(P>D)*--P=n%10,n/=10;d=48;W(d<58)H[d++]=0;A(1,O);R atoi(T)-o;}main(c,v)char**v;{F=open(*++v,0);W(read(F,O,12))P=O+7,printf("%d\n",G()%1000000);} */ /* ENTRY: igottagodad FROM: Keith Vollherbst AT: mtqua!keithv */ /****************************************************************/ /* */ /* igottagodad.c */ /* */ /* - sorry, you'll have to wait until all 10 digits */ /* show up on the odometers! */ /* */ /****************************************************************/ /* ** "return" and "while" are used enough that we save some source ** bytes by #defining them */ #define R return #define W while /* ** some global integer variables ** H[] - array to keep track of whether we already Have used a digit ** (only indices '0' thru '9' are actually used) ** F - File descriptor ** d,n - temporary variables used to analyze difference between ** overall odometer and trip odometer readings ** o - used to save original overall odometer reading ** Z - really a #define, but save a couple source bytes by ** making it a variable. ** note that F is local to main() and d,n and o are local to G(). However, ** we save a couple of source bytes by making them globals and assuming ** the default "int" type, without sacrificing much execution time. */ H[99],F,d,n,o,Z=10000; /* ** some global character variables ** O[] - input line -- original overall odometer reading in O[0]-O[5], ** trip reading in O[7]-O[10] -- made 99 elements long for ** no particular reason. ** *P - dual function -- used to point at beginning of original ** trip reading and also as pointer into D[]. ** D[] - digit by digit difference array. Each element in D is ** the corresponding digit in (overall+10000-trip)%10000. ** T[] - calculated final overall odometer reading. The mileage ** traveled is computed from (atoi(T)-atoi(O)). Note that ** T[] is 2 chars longer than the original reading. We ** prefill a "1" into the first position in case the odometer ** wraps around during the calculation. The other additional ** byte null terminates the string (for atoi()) (we count on ** this last byte to be initialized to null by default). */ char*P,O[99],T[8]="1",D[4]; /* ** A(c,y,n) ** Recursive function that calculates the next digit of T[]. ** Arguments: (Note int args are not declared since default is int) ** int c - digit in T[] we're trying to calculate. Note that for ** first call, c == 1 since T[0] is prefilled with a 1. ** char *y - first digit to try as candidate for T[c]. On the ** initial call to A(), y points to the first digit of the ** original odometer reading, and gets incremented to the next ** digit for subsequent calls. As soon as we are forced to ** change a digit, we point y at the string "00000" since the ** first digit we want to try in the next position is 0. ** This guarantees that we'll find the lowest new odometer ** reading that works. ** int n - flag indicating whether a "borrow" was necessary from ** T[c-1] to produce the preceding 2 digits. ** Given a digit t tried in T[c-1], if the corresponding digit ** in the trip meter is t-D[c-3]-1 a borrow is necessary ** and t-D[c-3] if not. When we fill T[c] and ** the corresponding digit in the trip meter, we know whether ** a borrow actually occurs and can check for consistency. ** Possible values for n: ** -1 -- borrow was necessary ** 0 -- borrow not necessary. ** Returns: ** 1 when T is complete; 0 if T[c] that works can't be found (indicating ** to the caller that it's back to the drawing board for T[c-1] -- which ** is really T[c] from the caller's point of view). */ A(c,y,n)char*y; { /* ** locals: ** t - current digit being tried in position c of T ** (initialized to *y, incremented till it reaches ** '9'+1). ** p - current digit being tried in the trip odometer ** j - loop index assuming values of -1 and 0. -1 ** is used to compute p assuming a borrow from t ** occurs on the next digit; 0 assumes no borrow. ** h - assigned value of -1 if borrow from previous digit ** was necessary to produce this value of p; 0 if not ** h is compared to the n parameter to determine if ** this combination of T[c-1]T[c] and P[c-3]P[c-2] ** (where P is imagined to hold the calculated trip ** odometer but is not actually used) is possible. */ int t= *y++,p,j,h; /* ** while (t < '9'+1) (Note that '0' === 48, '9' === 57) ** loop through all values of t, starting with the current one and ** continuing through '9'. */ W(t<58) { /* ** if we've already used digit t, it won't work for this ** position. Otherwise, set H[t] (via ++) and try t for T[c] */ if(!H[t]++) { /* ** record t in position c */ T[c]=t; /* ** only attempt to figure out a digit in the ** trip meter if we're at the 3rd or later position ** in the overall meter. */ if(c>2) { /* ** assume we can borrow in this position */ j= -1; /* ** if this is the last digit -- we can't borrow ** from it */ if(c>5) j=0; W(j<1) { /* ** calculate a trip digit */ p=t-D[c-3]+j; /* ** set h to assume no borrow occurred */ h=0; /* ** however, if if the calculated ** digit is < '0'(48), a borrow from ** the previous digit will be ** necessary (and we've got to ** add 10 to our calculation). */ if(p<48) h= -1,p+=10; /* ** only proceed if the actual borrow (n) ** from the previous digit matches the ** calculated borrow (h) or we're ** at the first trip digit so we don't ** care if the borrow matched; and ** if we haven't yet used digit p. ** ** note that we probably should ** have written this test as ** if ((c<4||n==h)&&!H[p]++) ** since n is undefined for c<4, but ** I already submitted it to Fred this ** way so we'll let it go! */ if((n==h||c<4)&&!H[p]++) { /* ** if we're already at position ** 6, we've got an answer, ** otherwise, if we succeed ** in adding the next digit ** we can return success. */ if(c>5||A(c+1,y,j)) R 1; /* ** can't get answer with ** this value of p -- "un-use" ** it. */ H[p]=0; } /* ** increment borrow flag and try again */ j++; } } /* ** if (c<=2), we can proceed immediately to ** the next digit. Note that we save 2 bytes by ** not passing the borrow flag since it's a don't care */ else if(A(c+1,y)) /* ** pass the success back to the caller */ R 1; /* ** can't get an answer with this value of t, "un-use" it */ H[t]=0; } /* ** we've got to change digit at position c, so we want next ** digit as low as possible (so set y to point at string of 0) */ y="00000"; /* ** if we're at the first digit (c==1), we allow t to roll back ** to 0 after 9. Otherwise we just increment. ** ** note () not needed around condition in this statement since ** precedence of ?: is low. */ t+=c<2&&t>56?-9:1; } /* ** we couldn't find a digit for position T[c] -- return failure ** indication */ R 0; } /* ** G() ** Figure out miles traveled (maybe + 1000000) */ G() { /* ** - save integer value of original odometer reading in o. ** (o=atoi(O)) ** - save difference mod (Z=10000) in n, making sure 0<=n<10000. ** (n=(o+10000-atoi(P=O+7))%10000) ** - since differences that produce no solution are symmetric ** around 5000, if n>5000 set d to 10000-n */ d=(n=((o=atoi(O))+Z-atoi(P))%Z)>5000?Z-n:n; /* ** if the difference mod 10 is 0, the last digit of overall and ** trip meters will always be the same so solution is impossible. ** other no solution cases were found empirically: ** n<=24 (or n>=9976) ** 98<=n<=102 (or 9898<=n<=9902) ** 199<=n<=201 (or 9799<=n<=9801) ** x998<=n<=x002+1000 */ if(d%10<1|d<25|d>97&d<103|d>198&d<202||(d%=1000)<3||d>997)R-1; /* ** calculate digit by digit difference */ P=D+4;W(P>D) *--P=n%10,n/=10; /* ** initialize to not having used any digits yet ** 48 == '0', 58 == '9'+1 */ d=48;W(d<58) H[d++]=0; /* ** fill T[] -- note that since all non-solution cases were ** taken care of above, we're guaranteed success by A() */ A(1,O); /* ** return the difference between T[] and O[] ** since we added 1000000 to T[], the caller must take this ** result mod 1000000. Doing this in the caller saves a couple ** bytes since we don't need parens here. R atoi(T)-o; } /* ** main(c,v) ** Do the job ** Arguments ** the usual */ main(c,v)char**v; { /* ** open file id'd by first arg */ F=open(*++v,0); /* ** read a line from F, calculate the answer with G() and print it */ W(read(F,O,12)) P=O+7,printf("%d\n",G()%1000000); }