Un graphique connecté est un graphique qui contient un chemin entre deux sommets.

Défi

Créez un circuit [porte NAND à 2 entrées] qui détermine si un graphe à 4 sommets est connecté.
(Les 2 entrées d'une porte peuvent être le même bit d'entrée ou une autre porte.)
Sortie True si le graphique est connecté, et False sinon.

Contribution

Les six arêtes possibles d'un graphe simple à 4 sommets:

[ ₀ e ₁ , ₀ e ₂ , ₁ e ₂ , ₀ e ₃ , ₁ e ₃ , ₂ e ₃ ]

où _a e _b représente s'il y a une arête entre les sommets a et b

La connectivité équivaut aux conditions suivantes:

• Si moins de 3 entrées sont True, la sortie est False.

• Si plus de 3 entrées sont True, la sortie True.

• Si exactement 3 entrées sont vraies et qu'elles forment un triangle, sortez False.

• Sinon, affichez True.

La réponse qui utilise le moins de portes gagne. Les liens seront rompus par
la profondeur de circuit la plus faible (longueur du ou des chemins les plus longs de l'entrée à la sortie).

30 NANDS

Au lieu de demander quand obtenons-nous un 1, j'ai posé la question quand obtenons-nous un 0. Il vaut mieux le poser de cette façon car il y a moins de 0 que de 1.

Voici la distribution en fonction du nombre d'arêtes (6ème ligne du triangle pascal)

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)

En posant la question de cette façon, nous obtenons le diagramme et l'expression suivants

 ___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) 

Nous supposons que la sortie sera par défaut à 1, mais passera à 0 dans l'une des conditions suivantes

1.A 0 pour trois bords adjacents (test de 3 entrées)

2.A 0 pour deux paires de bords opposés (test de 4 entrées)

Les conditions ci-dessus sont déjà commandées de la manière qui leur permettra d'être regroupées comme ci-dessous. (Soit dit en passant, cette version de l'expression est symétrique en rotation par rapport au sommet AFB.)

((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

Le score pour chacun &ou |est placé sous le symbole et justifié comme suit:

Niveau 0: Nous investissons dans un onduleur pour chaque entrée: 6 NANDS

Niveau 1: Nous pouvons construire un OU à partir d'une porte NAND en mettant un onduleur à l'entrée (total 3 NANDS) mais comme nous avons déjà investi dans 6 NANDS à l'étape précédente, nous pouvons faire 7 portes OU à partir de 7 portes NAND. Nous avons également besoin de 3 portes ET. Pour ceux-ci, nous allons simplement utiliser des NAND et laisser la sortie inversée. 10 NANDS

Niveau 2: Encore une fois, nous construisons 4 portes OU à partir de portes NAND. Dans chaque cas, nous avons 1 entrée d'une porte OU, nous devons donc inverser cela. Mais l'autre entrée est déjà inversée (provenant de l'une des NAND à l'étape précédente qui correspond à un &symbole dans trois cas, et d'un inverseur dans le dernier), nous n'avons donc besoin que de 2 portes pour chaque fonctionnalité OR. 4 * 2 = 8

Niveau 3: Nous devons maintenant ET les quatre sorties ensemble. Cela nécessite 3 portes ET, chacune construite à partir de 2 NAND, 3 * 2 = 6

Cela représente un total de 30 portes NAND, avec une profondeur maximale de 2 + 2 + 4 = 8 NAND pour les branches avec un |niveau 1 ou 3 + 1 + 4 = 8 NAND pour les branches avec un &niveau 1.

Le script Ruby suivant confirme visuellement que l'expression ci-dessus est valide.

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 NAND

Il n'y a pas de circuit plus simple que cela.

Il y a du code pour le tester sous l'image. Quant à le comprendre, c'est difficile. Il y a quelques portes IF là-bas, et les entrées sont un peu regroupées dans un triangle avec les lignes de coin libres ajoutées pour l'analyse une par une, mais pas de manière simple. Si quelqu'un parvient à le comprendre, je serai impressionné.

Code Verilog avec test:

// 4-vertex Connectedness Tester                                                                  
// Minimal at 19 NANDs                                                                            
//                                                                                                
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)                                                      
// This work is licensed under the Creative Commons Attribution 3.0                               
// Unported License. To view a copy of this license, visit                                        
// https://creativecommons.org/licenses/by-sa/3.0/                                                
//                                                                                                
// This is my entry to win this Programming Puzzle & Code Golf                                    
// at Stack Exchange:                                                                             
// /codegolf/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

Mathematica, 17 portes

Nous énumérons simplement toutes les règles, construisons la fonction booléenne et la minimisons sous NANDforme.

#->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"]

Résultat :

(#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)&

, où #1...#6sont 6 emplacements pour les arguments.

Cas de test :

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 *)

64 NAND

Les six bords peuvent être divisés en trois paires de bords opposés. Pour qu'un graphe soit connecté, il doit y avoir soit deux arêtes opposées ainsi qu'une troisième arête, soit trois arêtes connectées au même sommet.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Les paires opposées sont UX, VY, WZ, donc:

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

Construire des portes ET et OU de la manière habituelle, le nombre total de portes utilisées est 3*3+7*3+34= 64.