PROBLEM STATEMENT
One important process in designing computer chips is simulation. In this stage
of development, a circuit is created virtually and it is run for some amount of
time, and with various inputs. Your task is to write a method that performs
this given simulation over a given number of time steps.
Before you can simulate the circuit, you must first understand the components
in the circuit. For the sake of simplicity, we will only be considering four
types of components: NOT gates, AND gates, OR gates, and D flip-flops.
Remember, in a circuit all signals are binary: 1 or 0.
A NOT gate has one input and one output. If the input is 1, then the output is
0. If the input is 0, then the output is 1.
An AND gate has two or more inputs. If all of them are 1, then the output is
1, otherwise the output is 0.
An OR gate also has two or more inputs. If all of them are 0, then the output
is 0, otherwise the output is 1.
A D flip-flop has one input and one output. This component maintains the same
output, called its state, throughout the duration of each time step, regardless
of its input. At the transition from one time step to the next, all flip-flops
in the circuit simultaneously change their state to the value of their inputs.
For example, if after the transition to time step 2, the flip-flop has an input
of 1, then at time step 3, it will have a state, and thus an output, of 1.
Each String in components will start with "NOT", "OR", "AND", or "DFF" and this
will be followed by 1 or more numbers, indicating the indices of the
component(s) whose outputs are this components input.
For example, if components were {"NOT 1","DFF 0"}, that would mean that the
input of component 0 came from component 1, and the input of component 1 came
from component 0:
|-<---------<--
| |
->-NOT->-DFF->-
If the flip-flop in the above circuit was outputting a 1 at some time step,
then at the next time step it would change from outputting a 1 to outputting
its previous input, a 0. If the flip-flop was outputting a 0 at some time
step, then its input at that time step would be a 1, and thus at the next time
step, its output would be a 1. Thus, at every time step, the state of the
above flip-flop would switch its state.
After running the simulation for t time steps, you are to concatenate the
current state of all flip-flops into a String of '1's and '0's. The String
should contain one character for every flip-flop and they should be ordered the
same as they are in the input String[] (see examples to see how this works).
DEFINITION
Class: Simulate
Method name: go
Parameters: String[], int
Return type: String
Method signature (be sure your method is public): String go(String[]
components, int t);
NOTES
- assume that all flip-flops have an output of 0 at the beginning of the
simulation.
- do not include the state of non-flip-flop components in the output.
- the eight second execution time limit may become an issue for people who
submit solutions whose worst case run time is O(24^49) or 0(999999999)
TopCoder will ensure that:
- NOT and DFF gates have exactly 1 input and there will be exactly one space
between terms.
- AND and OR gates have at least 2 inputs and there will be exactly one space
between terms.
- All elements of components are between 5 and 50 characters in length,
inclusive.
- components contains between 1 and 50 elements inclusive.
- The only loops in the circuit contain at least one flip-flop (i.e. {"NOT 0"}
is not a valid input).
- No elements of components have extra spaces or leading '0's
- t will be in the range 0 to 999,999,999, inclusive.
- There will be between 1 and 15 flip-flops, inclusive
- All inputs indices will refer to valid components.
EXAMPLES
1. components = {"DFF 0"} t = 2
This is the simplest circuit we can make. Because flip-flops are initialized
to state 0, this flip-flop's input will be 0 and hence its state will always be
0. returns "0"
2. components = {"NOT 3","DFF 0","NOT 1","DFF 2"}
This corresponds to the following circuit, where the output a flip-flop is
always at its right-hand side:
Component: 0 1 2 3
/---NOT---DFF---NOT---DFF---\
| |
\---------------------------/
a) t = 0
The initial state of all flip-flops at time 0 is 0. Since there are two
flip-flops, return "00".
b) t = 1
The initial state of all flip-flops at time 0 is 0. The input of the flip-flop
at component 1 comes from component 0. At time 0, the output of component 0 is
1 (because it is the opposite of the flip-flop at component 3, whose output at
t = 0 is 0). Similarly, the input of the flip-flop at component 3 comes from
the output of component 2, which is 1 at time 0. Thus, at time 0, the inputs
of both flip-flops are 1. Thus, at time 1, both flip-flops change their states
to their inputs from the previous time step, and at time 1, the states of both
flip-flops are 1. Thus we return "11".
c) t = 2
At time 1, the states of both flip-flops are 1. Thus, both inputs to the
flip-flops are 0, and as a result, at time 2, both states go to 0.
returns "00"
d) t = 21
returns "11"
3. components = {"DFF 2","DFF 6","AND 3 4","NOT 5","OR 0 1","AND 0 1","NOT 1"}
This corresponds to the following circuit, where the number above each
component is its position in the input String[], a '+' indicates that two wires
overlap, but DO NOT connect, and a '*' indicated that two wires overlap and DO
connect:
--------------\
/ 6 |
| --NOT--/
| /
\ 1 |
--DFF-*----------\ 5 3
| AND---NOT--\ 2
| 0 / AND--\
| /-DFF--*----\ 4 / |
| | OR----/ |
\-+-----------/ |
| /
\-------------------------
a) t = 1
At time 0 the input to the flip-flop at component 0 is 0 (because the output of
the OR at component 4 is 0). However, the input to the flip-flop at component
1 is 1 (because the output of the NOT at component 6 is 1). Thus at time 1,
the state of the flip-flop at component 0 is 0, and the state of the flip-flop
at component 1 is 1.
returns "01"
b) t = 2, returns "10"
c) t = 3, returns "11"
d) t = 20
This circuit is a two bit binary counter. Thus at time 20, its output is 00.
returns "00"
4. components = {"OR 5 2 3 4 5","DFF 6","DFF 1","DFF 2","DFF 3","DFF 4","NOT 0"}
a) t = 3, returns "01100"
b) t = 99, returns "10000"
5. components = {"AND 9 10","DFF 13","DFF 0","DFF 6","DFF 5","NOT 4","OR 15
16","OR 3 4","AND 7 2","NOT 8","OR 7 2","AND 1 8","NOT 11","AND 12 14","OR 1
8","AND 3 4","NOT 17","OR 3 4"}
This circuit is a four bit counter that counts by threes.
a) t = 1, returns "0011"
b) t = 2, returns "0110"
c) t = 3, returns "1001"
d) t = 5, returns "1111"
e) t = 11, returns "0001"
f) t = 99999, returns "1101"
6. components = {"OR 9 8 7 6 5 4 3 2 1","OR 9 8 7 6 5 4 3 2","OR 9 8 7 6 5 4
3","OR 9 8 7 6 5 4","OR 9 8 7 6 5","OR 9 8 7 6","OR 9 8 7","OR 9 8","OR 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9","OR 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10","OR 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11","DFF 0"}
t = 10
returns "0"