PROBLEM STATEMENT:
Given a circuit consisting of logical AND and OR gates, INPUT and OUTPUT
components, connections (wires), and the values (TRUE / FALSE) of the inputs to
the circuit, you must determine the output of the circuit.
All values in the circuit are TRUE, FALSE, or UNDEFINED.
The AND and OR gates take two inputs and have one output. The outputs are
defined in terms of their inputs as follows:
For an AND gate:
* the output is TRUE if both inputs are TRUE
* the output is FALSE if at least 1 input is FALSE
* the output is UNDEFINED otherwise.
For an OR gate
* the output is TRUE if at least 1 input is TRUE.
* the output is FALSE if both inputs are FALSE.
* the output is UNDEFINED otherwise.
For this program, the circuit will be defined with two String[] and the inputs
will be defined in a third String[].
The first String[] defines the components in the circuit. Components are an
AND gate, an OR gate, an INPUT component, or an OUTPUT component. Each element
of the String[] will specify one component in the circuit. The elements of the
String[] will be of the form "<COMPONENT_NAME> <COMPONENT_TYPE>". The component
names will be unique. Component types will be "AND", "OR", "INPUT", or
"OUTPUT" where INPUT specifies places where values are inputted to the circuit
and OUTPUT specifies the place where the value of the circuit is outputted.
The circuit can have only one OUTPUT. For example, an element may be "ANDGATE
AND".
The second String[] defines the wires in the circuit. Each element of the
String[] will specify one connection or input line or output line. The
elements will be of the form "<POINT_1> <POINT_2>" which corresponds to a
connection connecting POINT_1 to POINT_2. POINT_1 and POINT_2 will be of the
form "<COMPONENT_NAME>-<PIN_NUMBER>" The COMPONENT_NAME specifies which
component the connection connects to and the PIN_NUMBER specifies where on the
component the connection connects to. For gates, a PIN_NUMBER of "1"
corresponds to the first input, a PIN_NUMBER of "2" corresponds to the second
input and a PIN_NUMBER of "3" corresponds to the output. INPUT and OUTPUT
components have only one place to connect to, PIN_NUMBER = 1. For example, an
element may be "IN-1 OUT-1".
The input to the circuit is specified in a third String[] with elements of the
form "<COMPONENT_NAME> <VALUE>" where COMPONENT_NAME is the name of the INPUT
component, and VALUE is "TRUE" or "FALSE". For example, an element may be "IN
TRUE".
The program should output a String which is the value connected to the OUTPUT
component. The output string should be TRUE, FALSE, or UNDEFINED.
DEFINITION:
Class Name: LogicAnalyzer
Method Name: getOutput
Parameters: String[], String[], String[]
Returns: String
Method Signature (be sure your method is public): String getOutput(String[]
components, String[] connections, String[] inputs);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
* components contains at most 20 elements.
* connections contains at most 50 elements.
* each element of components will contain between 4 and 20 characters, inclusive.
* components contains exactly one OUTPUT component and at least one INPUT
component.
* components elements are of the form "<COMPONENT_NAME> <COMPONENT_TYPE>"
(quotes and < and > for clarity only). There will be exactly one space in the
String, and the remaining characters will be capital letters. COMPONENT_NAME
will contain capital letters and COMPONENT_TYPE will be one of "AND", "OR",
"INPUT", and "OUTPUT".
* Component names are all unique.
* connections elements will be of the form "<COMPONENT_NAME_1>-<PIN_NUMBER_1>
<COMPONENT_NAME_2>-<PIN_NUMBER_2>" (quotes and < and > for clarity only).
There will be exactly 1 space and 2 dashes in the String. COMPONENT_NAME_1 and
COMPONENT_NAME_2 are names of components specified in the components String[]
and PIN_NUMBER_1 and PIN_NUMBER_2 are either "1", "2", or "3" for gates and are
"1" for INPUT and OUTPUT components.
* inputs elements are of the form "<COMPONENT_NAME> <VALUE>" (quotes and < and
> for clarity only). There is exactly one space in this String. COMPONENT_NAME
will be one of the names of one of the INPUT components specified in
components. VALUE will be either "TRUE" or "FALSE"
* There will be exactly one element in inputs corresponding to each input
component specified in components.
* There will be no loops in the circuit. That is a component will never be
dependent on its own output
NOTES:
* If multiple wires (connections) are connected to a pin, the values on all
connecting wires must always be identical.
* If a wire, or set of connected wires, are connected to the outputs of gates
(or the output of an INPUT component) which are outputting different values,
the wire(s) have the value UNDEFINED. That is, if there is ever a conflict of
value on a wire or set of connected wires, the value on the wire(s) is UNDEFINED.
* As an example, if a wire connects an INPUT called A with an INPUT called B
and another wire connects B to an OUTPUT called O and the input values of A and
B are TRUE and FALSE, respectively, the output is UNDEFINED.
* With both AND and OR gates, in some cases, one of the inputs can be
UNDEFINED, yet the output can still be determined.
* If the output of a gate cannot be determined for some reason, but the circuit
output does not depend on the output of that gate, the output of the circuit is
not necessarily UNDEFINED.
* For an AND gate, if one of the inputs is FALSE and the other input is
UNDEFINED (or has nothing connected to it) the output can still be determined
and is FALSE.
* For an OR gate, it one of the inputs is TRUE and the other input is
UNDEFINED, (or has nothing connected to it) the output can still be determined
and is TRUE.
EXAMPLES:
EXAMPLE 1:
If components = {"IA INPUT",
"IB INPUT",
"AA AND"
"O OUTPUT"}
and connections = {"IA-1 AA-1",
"IB-1 AA-2",
"O-1 AA-3"}
and inputs = {"IA TRUE",
"IB TRUE"}
This corresponds to a circuit with two inputs going into an AND gate (AA), and
the output of AA being the output of the circuit. Both inputs to AA are TRUE,
so its output is TRUE and the program should output TRUE.
To help visualize, here is a picture of the circuit in Example 1:
IA --> |---\
|AA |---> O
AB --> |---/
EXAMPLE 2:
If components = {"IA INPUT",
"IB INPUT",
"AA AND"
"O OUTPUT"}
and connections = {"IA-1 AA-1",
"IB-1 O-1",
"O-1 AA-3"}
and inputs = {"IA TRUE",
"IB TRUE"}
O (the OUTPUT) has two connections to it. The output of AA (the AND cannot) be
determined, so the value going to O from AA cannot be determined. Thus there
is a conflict and the program should output UNDEFINED.
To help visualize, here is a picture of the circuit in example 2:
IA --> |---\
|AA |--+> O
|---/ |
IB ------------+
EXAMPLE 3:
If components = {"IA INPUT",
"IB INPUT",
"AA AND"
"O OUTPUT"}
and connections = {"IA-1 AA-1",
"IB-1 O-1",
"O-1 AA-3"}
and inputs = {"IA FALSE",
"IB FALSE"}
O (the OUTPUT) has two connections to it. Even though there is only one
connection to AA (the AND gate), it is FALSE, so the output of AA can be
determined to be FALSE. Thus both connections to O are FALSE, so the program
outputs FALSE.
EXAMPLE 4:
components:
{IA INPUT,IB INPUT,IC INPUT,ID INPUT,AA AND,OA OR,AB AND,O OUTPUT}
connections:
{IA-1 AA-1,IB-1 AA-2,AA-3 OA-1,IC-1 OA-2,OA-3 AB-1,ID-1 AB-2,AB-3 O-1,AB-3
O-1,AB-3 O-1,AA-1 AA-2}
inputs:
{IA TRUE,IB FALSE,IC FALSE,ID TRUE}
returns:
UNDEFINED