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