BEWARE - HTML INTERPRETATION DOES WEIRD THINGS TO THE
COMPRESSED VERSIONS OF THE CODE .... DO NOT ASSUME THAT
WHAT APPEARS ON YOUR SCREEN IS PRECISELY THE RIGHT THING!
/* 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);
}