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);
}












Make your own free website on Tripod.com