/*   entry is followed by the expanded version

#define _ define
#_ T 10000
#_ J (T+z-*V)%T
#_ K a=u[s++]+r-d*T;if(a<0)a+=100*T;if(a0)x=~0,v(J,1,0,J-z),printf("%d\n",x);}


   This program corresponds roughly to the pre-obfuscated palith.c
   with added comments.  Main idea: for each value of odo and tripodo,
   generate the entire set of pairs of four digit numbers (abcd, efgh)
   such that: 1) all the digits a-h are distinct and 2) the differences
   abcd - efgh and odo - tripodo are congruent mod 10,000.  For each
   member of this set, use table lookup to find the two unused digits
   (say i and j) and consider the two six-digit numbers ijabcd and jiabcd.
   Keep track of the smallest of numbers these encountered greater than odo,
   (mod a million);  This will be the answer we seek.

   The recursion proceeds from the least significant digit to the
   most significant, and uses a bit-vector to keep track of the
   bits used so far.  This bit-vector also is used for the table
   lookup at the base of the recursion.

   -- Palith Balakrishnabati, 11267 and 11216


#define TT 10000

int tripo, odo;		/* trip and main odometers */
unsigned int bestgap;   /* main odometer reading found so far
			   that's nearest (mod 1,000,000) above odo */

int unusedpair[1024][2];/* table mapping vectors of 10 bits with
			   exactly 8 1-bits and 2 0-bits in the
			   low 10 bits to (10i + j) * 10000 and
			   (10 j + i) * 10000, where i and j
			   are the indices of the two 0-bits */

/* odocheck is the recursive routine:

   tenpow is 10^k where k is the recursion level (0 through 4)
   delta  is ((odo - tripodo) mod 10000) / tenpow, plus one if
             a carry occured at the previous level
   bits   is a 10-bit vector where the 1-bits indicate digits
             already used
   curodo is the last four digits of the main odometer.  This
             starts off, conceptually, with the trip odometer reading
	     0000 and the last four digits of the main odometer reading
	     (odo - tripodo) mod 10000.  This way the starting value of
	     each current odometer is always >= the starting value of the
	     corresponding trip odometer digit, and so the carries always
	     occur in the same way.

odocheck (delta, tenpow, bits, curodo)
register int delta;
register int tenpow;
register int bits;
register int curodo;
    register int gap;
    register int b;
    if (tenpow == TT) {
	/* base of the reucrsion;  curodo contains bottom four digits
	   of main odometer, and bits tells us the eight digits used so far */
	if (delta) curodo -= tenpow;   /* possibly adjust for carry */
	/* do table lookups to get the two possibilities for the
	   10,000s and 100,000s place digits, normalize to account for
	   main odometer wrap, and compare against the smallest gap
	   found so far, updating bestgap on new minima */	   
	gap = unusedpair[bits][0] + curodo - odo;
	if (gap < 0) gap += 1000000;
	if (gap < bestgap) bestgap = gap;
	gap = unusedpair[bits][1] + curodo - odo;
	if (gap < 0) gap += 1000000;
	if (gap < bestgap) bestgap = gap;
    } else {
	if (gap = delta % 10) {   /* if the digits in this position differ */
	    /* b is a bit vector holding the pair of bits that are going
	       to be used in this position.  First loop through the
	       feasible cases where there is no carry... */
	    for (b = 1 + (1< 0) {
	/* hack alert: make bestgap unsigned so that -1 looks like
	   a very big number when comparing against ints, but will
	   print out as "-1" when doing a printf("%d").  This saves
	   some special-casing */
	bestgap = -1;
	odocheck ((TT + odo - tripo) % TT, 1, 0, (TT + odo - tripo) % TT);
	printf ("%d\n",bestgap);

Make your own free website on