ENTRY: odomatic    FROM: Vincent Goffin   AT: mozart!vjg

	First, here's the original entry, with lines cut at position 80.
	If you want to compile it you must rejoin the last five lines.
	There are 2 lines altogether. It may not run correctly on some systems,
	because of v declared as int* ('cause it's shorter than char** !)

#define u U[i]=U[j]=0
int B,L,H=1e4,g,i,j,n,T=10;char U[10],Y[4],K[5];main(x,v)int*v;{for(open(v[1],cl
n,c){int i=(c+=Y[n])&&c=L?B=j:0,g)););}

	A much expanded version follows, and it's not that much slower.
	Things I like about this algorithm:
	1. Odom() routine screens out all impossible cases AND
	   generates all solutions when asked to.
	2. Good use made of the problem's Y[] invariants (see code).
	3. An all arithmetic approach best proceeds left to right,
	   and an all symbolic (no /, % or + of large numbers) approach
	   best proceeds right to left (because it still needs the single
	   digit carry). These "pure" methods by themselves can be solve the
	   problem, and lead to more compact code (25%), but they tend to be
	   too slow (x10).
	   This algorithm is a hybrid, using arithmetic for the first two
	   digits of big odom and symbolic for the last 4 digits, where a
	   "generate and match" method makes use of the Y[] invariants.
	Things I would have liked to improve but couldn't:
	1. Proving the existence of a solution apparently generates no useful
	   information that could make it easier to find the smallest solution
	   (even when both problems use the same routine).
	2. Apparently the fastest way to find the smallest solution involves
	   exhausting ALL solutions for 2 given leading digits.

int	T=10, H=10000, Existence, Exists, Best, Least;
char	U[10],	/* 0/1 flag: is digit i already used? */
	Y[4],	/* last 4 digit of (big_odom - small_odom), an invariant */
	K[5];	/* temp buffer for all solutions with same 2 leading digits */

main(argc, argv)
int argc;
char *argv[];
	int	i, j,	/* leading big odom digits */
		big_o,	/* big odom initial reading */
		miles,	/* miles traveled in search for solution */
		nbig_o;	/* big_o + miles */

	/* read from stdin to avoid explicit file structures */
	close(0);		/* close stdin */
	open(argv[1],0);	/* make v[1] stdin */

	/* read input file of initial large & small odometer readings */
	while (scanf("%d%d", &big_o, &sml_o) == 2)
		/* the 4 Y invariants, used by Odom() algorithm */
		sprintf(Y, "%04d", (H + big_o - sml_o)%H);

		/* verify existence of a solution */
		Exists = 0;
		Existence = 1;
		Odom(3, 0);
		Existence = 0;

		/* if a solution exists, set up search for smallest */
		if (Exists)
			miles = 0, Best = H;
			miles = -1, Best = 0;

		/* if solution exists, search for the smallest one */
		while (Best == H)
			/* Increment 2 leading digits of big odometer,
			   cautiously, until examination of the last 4 digits
			   of the big odom and the 4 digits of the small odom
			   shows a solution.
			   We already know there is a solution, and this
			   approach will eventually find the smallest one. */

			/* i,j are the 2 leading digits of big odometer */
			nbig_o = big_o + miles;
			i = nbig_o/H/T%T;
			j = nbig_o/H%T;
			Least = nbig_o%H;
			if (i != j)
				U[i]=U[j]=1;	/* mark i,j digits as used */
				/* find all solutions, if any, and keep
				   smallest. When Odom() finds a solution it
				   sets Best < H, so we break out of the loop,
				   cleanly */
				Odom(3, 0);
				U[i]=U[j]=0;	/* free the i,j digits */
			miles += Best - Least;
		printf("%d\n", miles);

Odom(n, carry)
	Odom() is used first to determine if a solution exists,
	and then to find the best solution if a solution exists.
	n starts at 3 and goes down to 0, as the algorithm
	examines the odometer digits from right to left, recursively.
	All big odom digits (i) are generated and tested in turn,
	from 9 to 0. For each i that passes the test, i.e. has not yet
	been used, the only possible corresponding small odom digit
	is calculated (from Y[n] and the carry) and tested.
	Y[n] is between '0' and '9', carry is 0 or 1.
	If both tests pass, we can proceed to the next digit to the left
	or record the solution (when n = 0).
	For the existence proof, Existence is set to 1 and we can exit
	as soon as the first solution is registered.
	Otherwise the algorithm exhausts all solutions and keeps the best one.
int n, carry;
	int i, j, delta = carry + Y[n] - '0';

	/* if delta = 0 or 10, i will = j and there can be no solution.
	   So for these cases set i = 0 and avoid the while() loop */
	i = (delta && delta < T)? T: 0;
	carry = 0;	/* this is the next carry;
			   the current carry was absorbed in delta */

	while (i--)
		if (U[i] == 0)		/* big odom digit must still be free */
			if (i < delta)		/* carry needed */
				carry = 1;
				delta -= T;	/* simulate effect of carry */
			j = i - delta;	/* small odom digit... */
			if (U[j] == 0)	/* ...must also be free */
				K[n] = '0' + i;	/* record digit as a char */
				if (n > 0)
					U[i]=U[j]=1;	/* used */
					Odom(n-1, carry);
					U[i]=U[j]=0;	/* free */
				else if (Existence)
					Exists = 1;
				else	/* record all, keep smallest */
					int new = atoi(K);
					if (new < Best && new >= Least)
						Best = new;
		if (Existence && Exists)

Make your own free website on