Subject: Re: Programming challenge
From: (Rob Warnock)
Date: Mon, 15 May 2006 22:46:34 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Glenn M. Lewis <> wrote:
| I came across a very cool hardware design challenge in a magazine
| and the author summarized the whole thing at this website:
| I was thinking that there must be an excellent way to write a
| program that solves this problem using Common Lisp...

Solving that *particular* problem is completely uninteresting (IMHO),
since the author gives away the entire trick... twice! However, a
slight generalization of George Harper's and Hadar Agam's "counting
the ones" solutions looks somewhat interesting:

    CLAIM [not proven, but "obvious" from the above paper]:
    Given a black box with N input signals (x0, x1, ... xN-1), it is
    possible to produce N output signals (not-x0, not-x1, ... not-xN-1)
    which are the logical inverses of the corresponding inputs
    [as bitmasks, (ASSERT (EQL not-X (LOGNOT X)))] if the black
    box contains *only* AND gates, OR gates, and not more than
    (CEILING (LOG N 2)) NOT gates [inverters].

    PROBLEM: Given N > 1, print a set of logic equations for a black
    box satisfying the above claim. Intermediate equations [that is,
    internal variables not visible outside the black box] are permitted.

    [Hint: You probably need at least (* 2 (CEILING (LOG N 2))) of them.]

Though... I would expect most of the time would be spent thinking
about the problem and very little coding, so I'm not sure even this
is very much of a "programming challenge" -- it's more of a math/logic
"brain teaser".


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607