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!
/*---------------------------------------------------------------------------
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
ose(0));scanf("%d%d",&n,&x)>0;printf("%d\n",x)){x=H+n-x;for(g=4;g--;x/=T)Y[g]=x%
T;G(3,0);for(x=g++;B==H;x+=B-L)L=x+n,i=L/H/T%T,j=L/H%T,L%=H,i-j&&G(u+3,0),u;}}G(
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 */
sml_o,
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;
else
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);
}
exit(0);
}
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)
break;
}
}