/* 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 */ #include #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); } }