It’s relatively easy to see that we cannot compute an arbitrary Boolean function using only AND and OR gates. For example, even the NOT function cannot be computed using only those gates (why?).
Can we build a circuit to compute an arbitrary Boolean function using a constant number of NOT gates?
Solution to the “42 code golf” problem
This was my best result:
n=1e6,m,c,d;main(){while(c+=d==42,d=0,m=--n)while(d+=m%10,m/=10);printf("%d\n",c);}
It would have been nice to find a solution under 80 bytes but, after one hour of trying, that was the best I could manage…
Spin Foam 
82:
n=1e6,m,c,d;main(){while(d+=m%10,(m/=10)||(c+=d==42,d=0,m=–n));printf(“%d\n”,c);}
Arguably \n is not part of the problem so it’s 80 without it 😉
Great solution!
79 without \n (81 with):
n=1e6,m,c,d;main(){for(;(m/=10)||(c+=d==42,d=0,m=–n);d+=m%10);printf(“%d”,c);}
Nice. I was thinking about “clever” ways to brute force the problem but it seems out of reach even when making assumptions (some assumptions will be needed anyway to avoid
printf("6061")being an answer 😀 ).[…] a previous post we have asked how many NOTs are needed to compute an arbitrary Boolean function. In this post we […]