Glenn M. Lewis <noSpam@noSpam.com> wrote:
+---------------
| I came across a very cool hardware design challenge in a magazine
| and the author summarized the whole thing at this website:
|    http://www.pldesignline.com/howto/showArticle.jhtml;?articleID=187202855
| 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

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607