How many NOTs are needed?

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…

Advertisements

5 thoughts on “How many NOTs are needed?

  1. zeuxcg says:

    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 😉

  2. mchouza says:

    Great solution!

  3. zeuxcg says:

    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);}

    • mchouza says:

      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 😀 ).

  4. […] a previous post we have asked how many NOTs are needed to compute an arbitrary Boolean function. In this post we […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s