3
\$\begingroup\$

Take a classic Boolean function with 4 variables, and perform a Karnaugh simplification (you can use any other method of Boolean algebra to arrive to the simplest form). The catch is: the result has to be displayed as a circuit diagram using ASCII graphics! (in a text-mode grid display, not just characters painted in arbitrary orientations in arbitrary positions)

You can choose how to evaluate input; it can be a form of 0000001011111110 as copied directly from the truth table, its 16 bit integer representation, etc.

This example function

simplifies to this form

For which you have to draw the circuit diagram out of ASCII characters.

Standard code-golf rules apply. The ASCII graphics can be as beautiful or as ugly as you like, but the diagram has to be unambiguously identifiable at first glance.

\$\endgroup\$
  • 1
    \$\begingroup\$ does "the simplest form" have to be in the form of a sum of products? The simplest SOP representation of XOR is AB`+A`B while the simplest representation is A^B \$\endgroup\$ – John Dvorak Aug 13 '13 at 19:30
  • 1
    \$\begingroup\$ "Unambiguously identifiable" is not a spec. People with different educational backgrounds might disagree on whether something is ambiguous, or on whether it is identifiable. \$\endgroup\$ – Peter Taylor Aug 13 '13 at 20:40
  • \$\begingroup\$ @PeterTaylor : "Unambiguously identifiable" should be quite normal for ASCII art, if for nothing more than to discourage "clever" solutions like . and "Well I've done it, but with a very small resolutiuon". If a reasonable person can identify the AND, OR and NOT gates in the drawing, it is enough. Take a look at other questions with ASCII art and their solutions. If I gave the exact drawing for the gates, it would just be yet another Kolmogorov Complexity question. \$\endgroup\$ – vsz Aug 14 '13 at 4:41
14
\$\begingroup\$

Python, 609 chars

N=input()
M=[[(255,['A']),(3855,['B']),(13107,['C']),(21845,['D'])]]
U=[1]*65536
for f,a in M[0]:U[f]=0
s=lambda x:x if x else''
L=1
B=65535
while all(f-N for f,a in sum(M,[])):
 K={}
 for f,a in M[L-1]:
  if U[f^B]:K[f^B]=[u'ᐂ',u'│']+a;U[f^B]=0
 for i in range((L+1)/2):
  for f,a in M[L-1-i]:
   A=max(len(x)for x in a)
   for g,b in M[i]:
    if U[f&g]|U[f|g]:
     d=[u'├'+u'─'*(A-1)+u'┐']+map(lambda x,y:s(x)+' '*(A-len(s(x)))+s(y),a,b)
     if U[f&g]:K[f&g]=[u'ᗝ']+d;U[f&g]=0
     if U[f|g]:K[f|g]=[u'ᗣ']+d;U[f|g]=0
 M+=[K.items()]
 L+=1
print '\n'.join([a for f,a in sum(M,[])if f==N][0])

Functions are specified by listing their truth table values as a binary input. The first bit is the output for ABCD=0000, the second bit is the output for ABCD=0001, and the last bit is the output for ABCD=1111. Does a brute-forceish search for the minimal circuit that computes the function. It never shares subcomputations, so it will always be a tree. M[L] contains a list of functions computable with L gates, represented as a pair (function,array of strings) where the function is computable with the circuit drawn by the strings when printed one per line. To make sure we get the minimum circuit, we run in increasing L order and U keeps track of which functions we've already found a circuit for.

$ echo 0b1110000000000111 | ./gates.py  
ᗣ
├───┐
ᐂ   ᗝ
│   ├──┐
ᗣ   ᗝ  A
├──┐├─┐
ᗣ  Aᗣ B
├─┐ ├┐ 
ᗝ B CD 
├┐  
CD  

I used some awesome Unified Canadian Aboriginal syllabics unicode glyphs for the gates, and box drawing glyphs for the connections. Yes, you heard right: *Unified Canadian Aboriginal*! If they don't display correctly in your browser, upgrade your unicode-fu. (They look awesome in my terminal; they are a bit misaligned on stackexchange.)

Depending on the input, could be fast or could take up to ~1/2 hour.

You might need to add something like # -*- coding: utf-8 -*- to the start of the program if running as a script.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.