# Build a 4-vertex Connectedness Tester using NAND gates

A connected graph is a graph that contains a path between any two vertices.

### Challenge

Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
(A gate's 2 inputs can be the same input bit or other gate.)
Output True if the graph is connected, and False otherwise.

### Input

The six possible edges of a simple graph with 4 vertices:

[ 0e1 , 0e2 , 1e2 , 0e3 , 1e3 , 2e3 ​]

where aeb represents whether there is an edge between vertices a and b

Connectedness is equivalent to the following conditions:

• If less than 3 inputs are True then output False.

• If more than 3 inputs are True then output True.

• If exactly 3 inputs are True and they form a triangle then output False.

• Otherwise, output True.

The answer that uses the fewest gates wins. ​ Ties will be broken by
the lowest circuit depth (length of longest path(s) from input to output).

• Could you specify the input format further? – LegionMammal978 Jan 23 '16 at 2:23
• iej is True or False according to whether there is or isn't an edge from vertex i to vertex j. ​ ​ – user30594 Jan 23 '16 at 2:26
• Can input be taken as 0 and 1? How about output? – TheCoffeeCup Jan 23 '16 at 2:37
• @TheCoffeeCup This is a logic circuit design problem, not code-golf. – lirtosiast Jan 23 '16 at 2:39
• @ThomasKwa Whoops, did not notice. – TheCoffeeCup Jan 23 '16 at 2:41

# 30 NANDS

Instead of asking when do we get a 1, I asked the question when do we get a 0. It's better to ask it this way round because there are less 0's than 1's.

Here's the distribution according to number of edges (6th row of pascal's triangle)

Edges     0  1  2  3  4  5  6
Frequency 1  6 15 20 15  6  1 (total 64)
Output    0  0  0  *  1  1  1
* = 0 if triangle (4 possibilities) 1 if claw (4 possibilities)
1 if two opposite edges and one other (12 possibilities)


Asking the question this way round, we get the following diagram and expression

 ___D___
|\     /|
| E   F |
|  \ /  |
A   X   C
|  / \  |
| /   \ |
|/__B__\|

(A|C|D|B)&(A|D|E)&(D|B|E|F)&(C|B|E)&(A|C|E|F)&(D|F|C)&(A|F|B)


We assume the output will default to 1, but will change to 0 under any of the following conditions

1.A 0 for three adjacent edges (test 3 inputs)

2.A 0 for two opposing pairs of edges (test 4 inputs)

The terms above are already ordered in the manner that will enable them to be grouped as below. (Incidentally, this version of the expression is rotationally symmetrical abouth the AFB vertex.)

((A|D)|((C|B)&E))&((B|E)|((D|F)&C))&((C|F)|((A|E)&D))&(A|F|B)    =6 inverters
1      1  1       1      1  1       1      1  1      1        =10 (7 OR with both inputs inverted, 3 NAND)
2                 2                 2               2      =8  (4 OR with one input inverted)
2                 2                 2           =6  (3 AND)
Total    =30


The score for each & or | is placed below the symbol and justified as follows:

Level 0: We invest in an inverter for each input: 6 NANDS

Level 1: We can build an OR from a NAND gate by putting an inverter at the input (total 3 NANDS) but as we already invested in 6 NANDS in the previous step we can make 7 OR gates from 7 NAND gates. We also need 3 AND gates. For these, we will just use NANDs and leave the output inverted. 10 NANDS

Level 2: Again we build 4 OR gates from NAND gates. In each case we have 1 input from an OR gate, so we have to invert that. But the other input is already inverted (coming from one of the NANDs in the previous step that corresponds to a & symbol in three cases, and from an inverter in the last one) so we only need 2 gates for each OR functionality. 4 * 2 =8

Level 3: We now need to AND the four outputs together. This requires 3 AND gates, each built from 2 NANDs, 3 * 2 = 6

That's a total of 30 NAND gates, with a max depth of 2+2+4=8 NANDs for branches with an | at level 1 or 3+1+4=8 NANDs for branches with an & at level 1.

The following Ruby script confirms visually that the above expression is valid.

64.times{|i|
a=i%2
b=i/2%2
c=i/4%2
d=i/8%2
e=i/16%2
f=i/32%2

puts i, ((a|d)|((c|b)&e))&((b|e)|((d|f)&c))&((c|f)|((a|e)&d))&(a|f|b)

puts " ___#{d}___
|\\     /|
| #{e}   #{f} |
|  \\ /  |
#{a}   X   #{c}
|  / \\  |
| /   \\ |
|/__#{b}__\\|

"
}


# 19 NANDs

There is no simpler circuit than this.

There is code for testing it below the picture. As for understanding it, that's difficult. There are a couple of IF gates there, and the inputs are kinda grouped into a triangle with the free corner lines added for analysis one by one, but not in a simple way. If anyone manages to understand it, I will be impressed.

Verilog code with testing:

// 4-vertex Connectedness Tester
// Minimal at 19 NANDs
//
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange:
// https://codegolf.stackexchange.com/questions/69912/build-a-4-vertex-connectedness-tester-using-nand-gates/
//
// I am sure there are no simpler solutions to this problem.
// It has a logical depth of 11, which is deeper than
// circuits using a few more NANDs.

module counting6 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, out000 );
input  in_000, in_001, in_002, in_003, in_004, in_005, in_006;
output out000;
wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017;

nand gate000 ( wir000, in_000, in_000 );
nand gate001 ( wir001, in_001, in_003 );
nand gate002 ( wir002, wir001, wir000 );
nand gate003 ( wir003, in_002, wir002 );
nand gate004 ( wir004, wir002, wir002 );
nand gate005 ( wir005, wir004, in_002 );
nand gate006 ( wir006, wir005, wir004 );
nand gate007 ( wir007, in_005, wir006 );
nand gate008 ( wir008, in_003, wir006 );
nand gate009 ( wir009, in_004, wir003 );
nand gate010 ( wir010, wir003, wir009 );
nand gate011 ( wir011, wir009, wir000 );
nand gate012 ( wir012, wir011, in_001 );
nand gate013 ( wir013, wir008, wir012 );
nand gate014 ( wir014, wir013, in_005 );
nand gate015 ( wir015, wir006, wir013 );
nand gate016 ( wir016, wir015, wir007 );
nand gate017 ( wir017, wir016, wir010 );
nand gate018 ( out000, wir014, wir017 );
endmodule

module connecting6_test;
reg [5:0] X;
wire a;

counting6 U1 (
.in_000 (X[0]),
.in_001 (X[1]),
.in_002 (X[2]),
.in_003 (X[3]),
.in_004 (X[4]),
.in_005 (X[5]),
.in_006 (X[6]),
.out000 (a )
);

initial begin
X = 0;
end

always
#10  X = X+1;

initial  begin
$display("\t\t \t_");$display("\t\ttime,\t \\db/_,\tconnected");
$monitor("%d,\t%b,\t%d",$time, X, a );
end

initial
#630  \$finish;

endmodule

// iverilog -o hello hello.v
// vvp hello


Kim Øyhus

• Did you prove this minimal, and if so how? – lirtosiast Nov 26 '18 at 8:25
• I used statistical testing to get evidence that it is minimal. For relatively simple circuits, like this one, the tests are fairly certain. – KimOyhus Nov 27 '18 at 9:41

# Mathematica, 17 gates

We simply enumerate all of the rules, construct the boolean function, and minimize it in NAND form.

#->If[Total@#<3||
MemberQ[{{1,1,1,0,0,0},{1,0,0,1,1,0},{0,1,0,1,0,1},{0,0,1,0,1,1}},#]
,0,1] /.{1->True,0->False}& /@
Tuples[{0,1},6];
BooleanMinimize[BooleanFunction[rule], "NAND"]


Result:

(#1⊼#2⊼#4)⊼(#1⊼#2⊼#5)⊼(#1⊼#2⊼#6)⊼(#1⊼#3⊼#4)⊼ \
(#1⊼#3⊼#5)⊼(#1⊼#3⊼#6)⊼(#1⊼#4⊼#6)⊼(#1⊼#5⊼#6)⊼ \
(#2⊼#3⊼#4)⊼(#2⊼#3⊼#5)⊼(#2⊼#3⊼#6)⊼(#2⊼#4⊼#5)⊼ \
(#2⊼#5⊼#6)⊼(#3⊼#4⊼#5)⊼(#3⊼#4⊼#6)⊼(#4⊼#5⊼#6)&


, where #1...#6 are 6 slots for arguments.

Test cases:

f=%; (* assign the function to symbol f *)

f[True, True, True, True, False, False]
(* True *)

f[True, True, False, True, False, False]
(* True *) (*, three Trues do not form a triangle *)

f[True, True, True, False, False, False]
(* False *) (*, three Trues form a triangle *)

• Does p⊼q⊼r mean not (p&q&r)? ​ What does your result's final & mean? ​ ​ ​ ​ – user30594 Jan 23 '16 at 4:19
• @RickyDemer Yes, p⊼q⊼r means (p⊼q)⊼r, which is equivalent to !(p&&q&&r). – njpipeorgan Jan 23 '16 at 4:24
• Plugging in False,False,True appears to show that (p⊼q)⊼r is not equivalent to !(p&&q&&r). ​ ​ – user30594 Jan 23 '16 at 4:30
• @RickyDemer That's a problem... I took it for granted. – njpipeorgan Jan 23 '16 at 4:35
• Also, at least the wolframalpha version of BooleanMinimize[expr,"NAND"] does not necessarily minimize the number of NANDS. ​ (Try BooleanMinimize[(((a NAND b) NAND (c NAND d)) NAND ((e NAND f) NAND (g NAND h))),"NAND"].) ​ Does running that on Mathematica give an output with at most 7 NANDS? ​ ​ ​ ​ – user30594 Jan 23 '16 at 4:43

# 64 NANDs

The six edges can be split up into three pairs of opposite edges. For a graph to be connected, there must either be two opposite edges as well as a third edge, or three edges connected to the same vertex.

       •
U

Z   •   Y
V     W
•     X     •


The opposite pairs are UX, VY, WZ, so:

A = U+V   ;3 gates
B = W+X
C = Y+Z

D = UV(B+C)  ;2+2+3=7 gates
E = WX(A+C)
F = YZ(C+A)

Result = D+E+F+UVW+UYZ+XVZ+XWY ; 18 + 16 = 34 gates


Building AND and OR gates in the usual way, the total number of gates used is 3*3+7*3+34 = 64.

• [True,True,False,True,False,False] gives a connected graph without any opposite edges. ​ ​ – user30594 Jan 23 '16 at 5:04
• @RickyDemer I think this works now... – lirtosiast Jan 23 '16 at 5:10