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!
#if !defined A
/* this is the actual entry qcd.c */
#define F for(j=10;--j>=0;)(n>>=1)&b
#define H j,p,b,s,m,c)int*p;{int n=1049600,f=j+p[4],y
unsigned
B;Z(H;F||(y=c,f+=c=j);s-=((n=y*9+f)>0?(f+=c*9)>0?n-100:f:n)*m;B>s?B=s:B;}r(H;c+=*p++;n=n>>c^n>>f;if(n&1022)F||(m&7?r:Z)(f>j,p,n|b,s,10*m,c>j),s+=m;}main(H=fopen(p[1],"r"),P[10];for(;B=-1;printf("%d\n",B)){F,fscanf(y,"%1d",P+j)<1&&exit();P[8]+=10*P[9]-99;r(0,P,0,0,1,0);}}
#elif defined B1
/* rearranging white-space slightly, for increased visibility ... */
#define F for(j=10;--j>=0;)(n>>=1)&b
#define H j,p,b,s,m,c)int*p;{int n=1049600,f=j+p[4],y
unsigned B;
Z(H;F||(y=c,f+=c=j);s-=((n=y*9+f)>0?(f+=c*9)>0?n-100:f:n)*m;B>s?B=s:B;}
r(H;c+=*p++;n=n>>c^n>>f;if(n&1022)F||(m&7?r:Z)(f>j,p,n|b,s,10*m,c>j),s+=m;}
main(H=fopen(p[1],"r"),P[10];for(;B=-1;printf("%d\n",B)){
F,fscanf(y,"%1d",P+j)<1&&exit();P[8]+=10*P[9]-99;r(0,P,0,0,1,0);}}
#elif defined B2
/* this is the result of the C preprocessor */
unsigned B;
Z(j,p,b,s,m,c)int*p;{int n=1049600,f=j+p[4],y;for(j=10;--j>=0;)(n>>=1)&b||(y=c,f+=c=j);s-=((n=y*9+f)>0?(f+=c*9)>0?n-100:f:n)*m;B>s?B=s:B;}
r(j,p,b,s,m,c)int*p;{int n=1049600,f=j+p[4],y;c+=*p++;n=n>>c^n>>f;if(n&1022)for(j=10;--j>=0;)(n>>=1)&b||(m&7?r:Z)(f>j,p,n|b,s,10*m,c>j),s+=m;}
main(j,p,b,s,m,c)int*p;{int n=1049600,f=j+p[4],y=fopen(p[1],"r"),P[10];for(;B=-1;printf("%d\n",B)){
for(j=10;--j>=0;)(n>>=1)&b,fscanf(y,"%1d",P+j)<1&&exit();P[8]+=10*P[9]-99;r(0,P,0,0,1,0);}}
#elif defined B3
/* rearranging white space liberally yields */
unsigned B;
Z(j,p,b,s,m,c)
int *p;
{
int n=1049600, f=j+p[4], y;
for(j=10; --j>=0; )
(n>>=1)&b || (y=c, f+=c=j);
s-=( (n=y*9+f)>0 ? (f+=c*9)>0 ? n-100 : f : n )*m;
B>s ? B=s : B;
}
r(j,p,b,s,m,c)
int *p;
{
int n=1049600, f=j+p[4], y;
c += *p++;
n = n>>c ^ n>>f;
if(n&1022)
for(j=10; --j>=0; )
(n>>=1)&b || (m&7?r:Z)(f>j, p, n|b, s, 10*m, c>j),
s += m;
}
main(j,p,b,s,m,c)
int *p;
{
int n=1049600, f=j+p[4], y=fopen(p[1],"r"), P[10];
for(;B=-1;printf("%d\n",B)){
for(j=10; --j>=0; )
(n>>=1)&b,
fscanf(y,"%1d",P+j)<1 && exit();
P[8]+=10*P[9]-99;
r(0,P,0,0,1,0);
}
}
#elif defined B4
/* making local adjustments,
producing more conventional representation of "logic" ... */
#include
unsigned B;
Z(j,p,b,s,m,c)
int *p;
{
int n=1<<20|1<<10, f=j+p[4], y, k;
for(k=10; --k>=0; )
if(((n>>=1)&b) == 0){
y = c;
f += c = k;
}
if( (k = y*9+f) > 0 )
if( (f += c*9) > 0 )
s -= (k-100) * m;
else s -= f * m;
else s -= k * m;
if(B > s) B = s;
}
r(j,p,b,s,m,c)
int *p;
{
int n=1<<20|1<<10, f=j+p[4], k, x;
x = c + *p++;
n = n>>x ^ n>>f;
if(n & ((1<<10)-2))
for(k=10; --k>=0; ){
if(((n>>=1)&b) == 0)
(m&7 ? r : Z)(f>k, p, n|b, s, 10*m, x>k);
s += m;
}
}
main(j,argv)
char **argv;
{
FILE *y = fopen(argv[1],"r");
int P[10];
for( ; ; ){
B = -1;
for(j=10; --j>=0; )
if(fscanf(y,"%1d",P+j)<1) exit();
P[8] += 10*P[9] - 99;
r(0,P,0,0,1,0);
printf("%d\n",B);
}
}
/* now we can try to see what the code is doing...
main:
the outer loop in main processes a line of input, each time through.
B (the answer) is initialized to -1, but will be changed
if any better answer is found.
the inner loop reads 10 digits from the input file, ignoring white space,
and storing them backwards in P[9 .. 0],
so P[0] contains the units digit of the 4-digit input,
P[3] contains its thousands digit,
P[4] contains the units digit of the 6-digit input,
and P[9] contains its high-order digit.
then P[8]+=10*P[9] would set P[8] to the 2-digit number
at the front of the 6-digit input,
and P[8]-=100 is done here for efficiency... explanation later.
the call to r() changes B if necessary; then we print B.
r:
r is hard to explain.
before getting to the actual function r,
it will be helpful to look at a similar function
for a simpler problem.
i want (not really, just pretend) to find
all 4 digit numbers which,
added to the 4-digit trip odometer,
produce 4 distinct digits.
assume that main(), as above, has stored the
odometer value backwards in an array of int(s).
for no specific reason, i choose to write
a recursive function
that finds valid 1-digit extensions (to the left)
of K-digit partial solutions (K = 0, 1, 2, or 3)
and then (often by calling itself) takes useful
action with these extended values.
i start out with
r1(ptr, num, power, carry)
int *ptr;
{
int sum, newdigit, sumdigit, sumcarry, newnum;
for (newdigit = 0; newdigit < 10; newdigit++){
sum = *ptr + newdigit + carry;
sumdigit = sum % 10;
sumcarry = sum / 10;
newnum = num + newdigit*power;
if ( )
continue;
if ( power < 1000 )
r1(ptr+1, newnum, 10*power, sumcarry);
else
printf("%d\n", newnum);
}
}
but i need to write code that checks for matching digits.
let me add an argument that bit-maps the digits previously
observed in the total.
i use the 1<<0 bit to show the presence of 9, ...,
1<<9 to show the presence of 0.
r1(ptr, bitmap, num, power, carry)
int *ptr;
{
int sum, newdigit, sumdigit, sumcarry, newnum, newbit;
for (newdigit = 0; newdigit < 10; newdigit++){
sum = *ptr + newdigit + carry;
sumdigit = sum % 10;
sumcarry = sum / 10;
newnum = num + newdigit*power;
newbit = 1 << (9-sumdigit);
if(bitmap & newbit)
continue;
if ( power < 1000 )
r1(ptr+1, bitmap | newbit, newnum, 10*power, sumcarry);
else
printf("%d\n", newnum);
}
}
because we're scored (in part) on fewest characters,
i now eliminate extra variables and letters:
r1(p, b, s, m, c)
int *p;
{
int t, d, n;
for (d = 0; d < 10; d++, s += m){
t = *p + d + c;
n = 1 << (9-(t%10));
if(b & n)
continue;
if ( m < 1000 )
r1(p+1, b|n, s, 10*m, t/10);
else
printf("%d\n", s);
}
}
because 0 <= t <= 19,
i can replace t/10 with t>9.
also, i can redefine b (the motivation becomes obvious, later)
as
if the digit i has not been found, then
b & (1<<(9-i)) is zero, and
b & (1<<(19-i)) is zero.
if the digit i has been found, then
b & (1<<(9-i)) is nonzero.
b & (1<<(19-i)) is unspecified.
in other words, the 1-bits in b are allowed to propagate into
"phantom" bits, 10 positions further left.
this lets me change
n = 1 << (9-(t%10));
to
n = ((1<<19)|(1<<9)) >> t;
setting x = c + *p,
now i can write
r1(p, b, s, m, c)
int *p;
{
int d, n, x;
x = c + *p++;
for (d = 0; d < 10; d++, s += m){
n = ((1<<19)|(1<<9)) >> x >> d;
if(b & n)
continue;
if ( m < 1000 )
r1(p, b|n, s, 10*m, x+d>9);
else
printf("%d\n", s);
}
}
by first noting that d is always increasing by 1,
and then replacing d with k = 9-d,
i get
r1(p, b, s, m, c)
int *p;
{
int k, n, x;
x = c + *p++;
n = ((1<<20)|(1<<10)) >> x;
for (k = 10; --k >= 0; s += m){
if((n>>=1) & b)
continue;
if ( m < 1000 )
r1(p, b|n, s, 10*m, x>k);
else
printf("%d\n", s);
}
}
observe that m is always a power of 10.
hence the test (for non-zero-ness) of
m < 1000
is equivalent to
m % 1000
which is equivalent to
m % 8
which is equivalent to
m & 7 .
now, back to the function r itself.
r is rather like r1, searching for 4-digit numbers
one digit at a time, starting with the least significant digit
and recursing for each more significant digit.
but now we have 2 odometers to add to,
and we need 8 distinct digits to result.
the for-loop and if
in r1 are still quite useful here.
we just need n to contain bits for the 2 new digits
that have to be distinct from the other digits,
instead of just 1 new digit as before.
so it is tempting to write something like
n1 = ((1<<20)|(1<<10)) >> x1;
n2 = ((1<<20)|(1<<10)) >> x2;
n = n1|n2;
but there are traps here.
the two new digits must be distinct from each other,
not just distinct from the digits previously obtained.
we could check that x1 != x2 ,
or that n1 != n2 ,
but that's not quite enough.
we can check !(n1&n2), and that's enough.
the trouble is when x1 and x2 are 0 and 10 (respectively or not).
(this can happen! they range between 0 and 10 inclusive.)
my code-saving solution is to put
n = n1^n2;.
this contains 4 1-bits (2 ordinary, and 2 "phantoms")
in good cases,
no 1-bits in normal bad cases,
and 2 1-bits ( (1<<20) + 1 ) in the special bad case.
now i can check (n & ((1<<20) - 2))
and if nonzero, then n is set for the for loop.
actually i check (n & ((1<<10) - 2)).
smaller constants take less source code, and
maybe smaller/faster object code (depending on the machine).
since r doesnt finish the job
(to get 10 distinct digits, and then to keep the
least solution that does so),
r should not call printf when it's done with its recursion.
instead it calls a function Z with the same arguments as r has,
and so the peculiar construct
(m&7 ? r : Z)(f>k, p, n|b, s, 10*m, x>k);
appears.
Z:
Z is invoked under exactly 4 stacked calls to r.
p is &P[4], and m is 10000.
s is a 4-digit number that, added to both odometers,
yields 8 distinct digits
in the last 4 digits of each.
those 8 digits are represented by the 1-bits in b.
the carry from the last 4 digits of the 6-digit odometer is in j,
and (although nobody cares) the carry from the 4 digit odometer is in c.
there are 2 digits left.
we can place them (in any order) at the front of the 6-digit odometer,
and obtain 10 digits all distinct.
so then if we determine the 2 digits to prepend to s,
producing those missing digits in the 6-digit sum,
WE HAVE A (not the LEAST) SOLUTION.
in fact, we get two solutions.
we need to choose the smaller of the two, and maintain somewhere
(well, yes, in B) the least solution that has been found.
the detailed logic of Z is as follows:
first f is initialized to j+p[4],
which is j+P[8],
which (based upon main's adjustments)
should be interpreted as (o12 +j) - 99.
here o12 represents the first 2 digits of the 6-digit odometer value,
viewed as a 2-digit number.
the for-loop uses code like r
to find the 2 missing digits left after 8 have already been registered in b.
twice we reach the line
f += c = k;
where k is 9-d for d a missing digit.
thus f is modified to (o12+j) -d1 -d2 -81 when the loop is over.
the loop leaves c = 9 - d2, and y = 9 - d1.
d1 and d2 are the missing digits, with d1 < d2.
the next 2 if's (assuming we execute both) contain assignments that put
-k = 10*d1 +d2 - (o12+j)
-f = 10*d2 +d1 - (o12+j)
which obviously look like the 2-digit values to prepend to s
so that d1 and d2 will appear in the sum, giving the 10 distinct digits.
but either can be negative, in which case that value +100 can be used.
we know -k < -f, so if -k >= 0 it is the better (smaller) answer.
if -k < 0 and -f >= 0, we want the smaller of 100-k and -f
which must be -f.
if -k < 0 and -f < 0, we want the smaller of 100-k and 100-f
which must be 100-k.
the code adjusts s for whichever case above is appropriate,
and obtains a solution.
then it compares against B, the least solution thus far,
and updates B if appropriate.
note that B is unsigned, so the initial -1
compares larger (worse) than any actual solution discovered later,
but printing with %d effectively casts the value to (int).
could i make this any faster??
yes, but not enough.
*/
#elif defined B5
/* could i make it any smaller?
by sacrificing (probably; it depends on the machine
and how smart the compiler is) run time for character reduction,
there are still a few tricks to play.
i've produced a 356-character version, not my official entry:*/
#define F for(j=10;j--;n/=2)n&b
#define H j,p,b,s,m,c)int*p;{int n=524800,f=j+p[4],y
int
B;Z(H;F||(y=9*c,f+=c=j-9);s-=m*=(y+=f+=10*p[5])>0?(f+=c*9)>0?y-100:f:y;B>s|B<0?B=s:B;}r(H;c+=*p++;n=n>>c^n>>f;if(n&511)F||(m&7?r:Z)(f>j,p,n|b,s,10*m,c>j),s+=m;}main(H=fopen(p[1],"r"),P[10];for(;B=-1;printf("%d\n",B)){F,fscanf(y,"%1d",P+j)<1&&exit();r(0,P,0,0,1,0);}}
#elif defined B6
/* rearranging white-space slightly, for increased visibility ... */
#define F for(j=10;j--;n/=2)n&b
#define H j,p,b,s,m,c)int*p;{int n=524800,f=j+p[4],y
int B;
Z(H;F||(y=9*c,f+=c=j-9);s-=m*=(y+=f+=10*p[5])>0?(f+=c*9)>0?y-100:f:y;
B>s|B<0?B=s:B;}
r(H;c+=*p++;n=n>>c^n>>f;if(n&511)F||(m&7?r:Z)(f>j,p,n|b,s,10*m,c>j),s+=m;}
main(H=fopen(p[1],"r"),P[10];for(;B=-1;printf("%d\n",B)){
F,fscanf(y,"%1d",P+j)<1&&exit();r(0,P,0,0,1,0);}}
#endif