## Problem Statement | |||||||||||||

PROBLEM STATEMENT Compute a truth table of a digital circuit composed of logical elements AND, OR, and NOT. An AND element takes between 2 and 8 inputs and outputs 1 if all inputs are 1, and 0 otherwise. An OR element takes between 2 and 8 inputs and outputs 1 if any element is 1, and 0 otherwise. A NOT element takes 1 input, and ouputs 0 if the input is 1, and 1 if the input is 0. The circuit does not have feedbacks, meaning that no output of an element can influence any of that element's inputs, either directly or through other elements. DEFINITION Class name: TruthTable Method name: getTruthTable Parameters: String[] Return type: String[] Method signature: String[] getTruthTable(String[] nodes); Be sure your method is public. nodes may have 2 to 50 String objects, inclusive. Each String defines a "node" in the circuit. A "node" may be an input, an output, or a logical element of type "AND", "OR", or "NOT". Strings are formatted as follows: TYPE:Input1,Input2,... TYPE is a single lowercase character designating the type of the node, as follows: 'i' - the node is an input, 'x' - the node is an output, 'a' - the node is a logical AND element, 'o' - the node is a logical OR element, 'n' - the node is a logical NOT element. The input list following the colon ':' character (Input1, Input2,...) designates inputs of this node. The input list consists of numbers in the range 0 to 48, inclusive, representing zero-based indexes of nodes used as inputs to the current node. For example, string "a:1,2" represents a logical AND element with two inputs, connected to the outputs of nodes at index 1 and 2. Elements of type 'a' and 'o' have 2 to 8 inputs, inclusive. Elements of type 'n' and 'x' have exactly one input. Elements of type 'i' do not have inputs, therefore strings that start with 'i' do not contain the ':' character. TopCoder will ensure that: * nodes has at least two and no more than fifty elements * The first character of each String is 'i', 'x', 'a', 'o', or 'n' * nodes contains at least one but no more than five inputs * nodes contains at least one output * Number of inputs per element type is within the limits set above: two to eight, inclusive, for ANDs and ORs; exactly one for NOTs and Outputs, zero for Inputs * Indexes of elements used as inputs to an element are lower than the index of the current element (this ensures that the circuit has no feedbacks) Your method should compute truth tables for each of the outputs, and return the results in a String[], one per output, arranged in the order of the outputs in the circuit definition. Each truth table is a string composed of characters '1' (digit one) and '0' (digit zero). Truth tables consist of 2^numInputs (2 raised to the power of numInputs) characters, where numInputs is the number of inputs to the circuit. To build a truth table, your method should number all inputs 0 through numInputs-1, in the order they appear in the circuit definition. Then your method should go through all possible combinations of zeros and ones for the inputs, interpreting each combination of inputs as a binary representation of an index into the truth table. The first character in the string representation of truth tables corresponds to all inputs set to zero; The second character corresponds to the input with the lowest index set to one while the rest of the inputs are set to zero, and so on. The last character corresponds to all inputs set to one. For example, the truth table for an AND element with two inputs is "0001". NOTES * Some outputs may ignore some inputs. This should not influence the length of the truth table for that output. * Some outputs may produce a constant result regardless of the state of the inputs. Truth tables for such outputs should consist of 2^numInputs repetitions of the constant (see example number 4). * Circuits may use output nodes as inputs to other nodes. This is not different from re-using that output's input, in that it does not alter circuit's truth table. For example, {"i","n:0","x:1","n:2","x:4"} and {"i","n:0","x:1","n:1","x:4"} are equivalent. EXAMPLES 1. nodes = {"i","i","i","n:0","a:1,2,3","x:4"} This circuit contains a logical AND element with three inputs, two of which are connected directly to inputs, and one connected to an input through a logical NOT element. See diagram below (for a more detailed diagram check out http://www.topcoder.com/contest/circuits.html): +---+ +---+ i0 --|not|--| | +---+ | | i1 ---------|and|-- o0 | | i2 ---------| | +---+ The circuit computes the following: i0 i1 i2 | o0 ---------+--- 0 0 0 | 0 1 0 0 | 0 0 1 0 | 0 1 1 0 | 0 0 0 1 | 0 1 0 1 | 0 0 1 1 | 1 1 1 1 | 0 getTruthTable should return {"00000010"}. 2. nodes = {"i","x:0"} This trivial circuit connects its only input to its only output, with no logical elements in between. getTruthTable should return {"01"}. 3. nodes = {"i","n:0","x:1"} This circuit contains a logical NOT element in between of its input and its output. getTruthTable should return {"10"}. 4. nodes ={"i","n:0","a:0,1","x:2"} This circuit returns 0 regardless of the state of the input, because (X AND (NOT X)) is 0 for any value of X; therefore getTruthTable should return {"00"}. 5. nodes = {"i","i","i","n:0","a:1,2,3","x:4","x:0","x:3"} getTruthTable should return {"00000010","01010101","10101010"}. | |||||||||||||

## Definition | |||||||||||||

| |||||||||||||