| | 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"}. |