``` Subject: Re: Programming challenge From: rpw3@rpw3.org (Rob Warnock) Date: Mon, 15 May 2006 22:46:34 -0500 Newsgroups: comp.lang.lisp Message-ID: <iKKdnYl269KH1vTZnZ2dnUVZ_sOdnZ2d@speakeasy.net> ```
```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

```