| | PROBLEM STATEMENT
Using blocks of binary logic defined by their truth tables, build a block with
a desired truth table. Each block of binary logic has two inputs and two
outputs. Block inputs are referred to as i0 and i1; block outputs are referred
to as o0 and o1. Logic inside a block implements its truth tables for each of
its two outputs. To build a block with the target truth table, connect blocks
in a chain, wiring both outputs of a block to both inputs of another block.
Your method should return the number of blocks in the shortest chain
implementing the target truth table, or -1 when it is impossible to build a
chain with the target truth table.
DEFINITION
Class name: BinBlocks
Method name: targetChain
Parameters: String[], String
Return type: int
Method signature: int targetChain(String[] blocks, String target) (make sure
your method is public)
Both the target and the elements of blocks are String representations of truth
tables formatted as follows (quotation marks are used for clarity - they are
not part of the strings):
"abcd,efgh"
Each character represents a digit '0' or '1'. Group abcd represents the truth
table of the output o0, while efgh represents the truth table of the output o1.
The characters of "abcd,efgh" correspond to the following states of inputs:
i0 i1 | o0 o1
-------+-------
0 0 | a e
1 0 | b f
0 1 | c g
1 1 | d h
For example, truth table "0001" corresponds to the truth table of the operation
AND: (i0 AND i1).
TopCoder will check that
- blocks will contain 0 to 50 elements, inclusive, and
- all truth tables are properly formatted
NOTES
* Blocks are ordered. Your method may not alter the order of the blocks while
building the target chain. It may, however, skip any number of blocks.
* For certain values of target, the optimal chain would consist of zero logical
blocks. See examples 1 and 2.
* When connecting logical blocks A and B in a chain, you may wire outputs to
inputs in either of the two ways: A o0 to B i1 and A o1 to B i1, or A o0 to B
i1 and A o1 to B i0. This rule applies even in cases when the optimal chain is
empty.
EXAMPLES
1. blocks= {}, target="0101,0011". targetChain should return 0 because wiring
i0 to o0 and i1 to o1 implements the target truth table.
2. blocks= {"0000,1111","0000,0101"}, target="0011,0101". targetChain should
return 0 because wiring i0 to o1 and i1 to o0 implements the target truth
table, without using any of the blocks.
3. blocks= {"0001,0111","1010,1100"}, target="1110,1000". targetChain should
return 2 because you need to wire both blocks in a sequence to get the target
truth table.
4. blocks= {"0001,0111","0101,0011"}, target="0111,0001". targetChain should
return 1 because the target truth table is the "flipped" truth table of the
block 0.
5. blocks= {}, target="1111,0000". targetChain should return -1 because it is
impossible to implement the target truth table.
6. blocks= {"0101,1010","0110,1001","1110,0001","1010,1100","1000,0001"},
target= "1111,0000". targetChain should return 2. For a graphical
representation of this please refer to
http://www.topcoder.com/contest/blocks.html
7 a. blocks={"0001,1101","1010,1011"}, target="0010,0011". targetChain returns 2
b. blocks={"0001,1101","1010,1011"}, target="0011,0010". targetChain returns 2
c. blocks={"0001,1101","1010,1011"}, target="1110,1111". targetChain returns 2
d. blocks={"0001,1101","1010,1011"}, target="1111,1110". targetChain returns 2
e. blocks={"0001,1101","1010,1011"}, target="0100,0101". targetChain returns 2
f. blocks={"0001,1101","1010,1011"}, target="0101,0100". targetChain returns 2
|