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

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 | |||||||||||||

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

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