FourGate.java

/*Connor Roos
 * 4Gate NAND->XOR Proof
 * 10/25/17
 * Discrete Math
 */
import java.util.TreeMap;
import java.util.LinkedHashSet;
import java.util.Set;
public class FourGate {
	TreeMap<String, Circuit> allCircuits = new TreeMap<>();//Can hold either Wire or nandCircuit Objects
	Wire a = new Wire ("a"); Wire b = new Wire ("b"); Wire zero = new Wire ("0"); Wire one = new Wire ("1"); //Initializes the wires

	public interface Circuit{ //Defines the methods that both wires and nandCircuits need, this also allows the program to run methods that could pass either as parameters
		public String getCircuitName();
		public Circuit getInput1();
		public Circuit getInput2();
	}

	private class Wire implements Circuit {//Wire is just the a,b,0,1 inputs-wire simply returns itself if asked for either Input, which is used as the exit case for the recursive methods
		String wireName;
		public Wire(String wireName) {
			this.wireName = wireName;
		}
		public Circuit getInput1() {
			return this;
		}
		public Circuit getInput2() {
			return this;
		}
		public String getCircuitName() {
			return this.wireName;
		}
	}

	private class NandCircuit implements Circuit{ //A NandCircuit is composed of two Circuits as inputs to a nand gate and the set of nand gates needed to construct it 
		String circuitName; Circuit input1; Circuit input2; 
		public NandCircuit(Circuit input1, Circuit input2) {
			this.circuitName = "Nand:("+input1.getCircuitName() + ", "+ input2.getCircuitName()+")"; this.input1 = input1; this.input2 = input2;
		}
		public Circuit getInput1() {
			return this.input1;
		}
		public Circuit getInput2() {
			return this.input2;
		}
		public String getCircuitName() {
			return this.circuitName;
		}
	}
	private Set<NandCircuit> numGates(Circuit c) { //Recursively finds the number of gates in this circuit by counting the number of nandCircuits needed to construct it.  
		Set<NandCircuit> subCircuits = new LinkedHashSet<>(); //All the circuit objects needed to construct another circuit
		if(c instanceof NandCircuit) {
			subCircuits.add(((NandCircuit)c));//The circuit itself is added to the Set subCircuits as all NandCircuits end in a nand gate.
		}
		if(c.getInput1() instanceof NandCircuit) {//Note the as the method looks for instance of NandCircuit, it can never be called on a Wire.
			subCircuits.addAll(numGates(c.getInput1()));
		}
		if(c.getInput2() instanceof NandCircuit) {
			subCircuits.addAll(numGates(c.getInput2()));
		}
		return subCircuits;

	}
	public boolean XORCheck(Circuit x) { //The a and b variables from verifyCircuit come from here-compares if the circuit operates like a XOR gate
		if(verifyCircuit(x,1,1) == 0 
				&& verifyCircuit(x,1,0) == 1
				&& verifyCircuit(x,0,1) == 1
				&& verifyCircuit(x,0,0) == 0)
			return true;
		return false;
	}

	public int verifyCircuit(Circuit x,int a,int b) { //Outputs the exact boolean value of the circuit under the given conditions of a and b 
		if(x.getCircuitName().equals("0") ||x.getCircuitName().equals("1") )
			return Integer.parseInt(x.getCircuitName());
		if(x.getCircuitName().equals("a"))
			return a;
		if(x.getCircuitName().equals("b")) //Four exit cases are needed to represent the 0,1,a,b wires
			return b;
		else
			if(verifyCircuit(allCircuits.get(x.getInput1().getCircuitName()), a ,b) == 1 && verifyCircuit(allCircuits.get(x.getInput2().getCircuitName()), a, b) == 1)
				return 0;
			else
				return 1;
	}

	public void findCircuits(int size) { //Input the maximum size of the XOR equivalent you are looking for
		NandCircuit c;
		Object[] currentCircuits;
		this.allCircuits.put(a.getCircuitName(), a);this.allCircuits.put(b.getCircuitName(), b);this.allCircuits.put(zero.getCircuitName(), zero);this.allCircuits.put(one.getCircuitName(), one); //Wires are added to circuits first
		int oldCircuitsSize = 0;
		while(allCircuits.size() != oldCircuitsSize) { //Checks to see if the size of the map allCircuits has increased since the last iteration, if not no more circuits can be constructed and the execution ends
			oldCircuitsSize = allCircuits.size();
			currentCircuits =  allCircuits.values().toArray();
			for(int i = 0; i<oldCircuitsSize; i++) { //Nested for loop used, note that j starts at the current value of i so that every object in currentCircuits is compared to every other object only once
				for(int j = 0; j<oldCircuitsSize; j++) {
					c = new NandCircuit((Circuit)currentCircuits[i],(Circuit)currentCircuits[j]); //Constructs a new circuit object
					int newGateLength = numGates(c).size();
					if(newGateLength<=size && !allCircuits.containsKey(c.getCircuitName())){ //If the gate is both less than or equal to the needed size and not already in the mapping it is added to the mapping
						allCircuits.put(c.getCircuitName(), c);
						if(this.XORCheck(c)) {
							System.out.println(c.getCircuitName() + "is equivalent to XOR!!! "+ "And it's "+newGateLength+" Gates long!");	
						} 
					}
				}
			}
		}
	}

	public static void main(String[] args) { //Main method, change the value in find circuits to check for a different number of maximum gates
		long startTime = System.currentTimeMillis(); //Main method also calculates how long it takes for the code to run-around 3 seconds for checking 4 Gates and 9 minutes for checking 5
		FourGate g = new FourGate();
		g.findCircuits(4);
		long endTime   = System.currentTimeMillis();
		long totalTime = endTime - startTime;
		System.out.println(totalTime +" milliseconds"); 
	}
}