Packing Wood Pieces

Question

There are two pieces of wood. Both consist of a straight body and some extra blocks below the body. An example piece with extra blocks at (0-indexed) positions 0,4,7,9,10:

XXXXXXXXXXX
X   X  X XX

The piece can be represented as a 01 binary sequence with the ith character showing if there is a block at the ith position. The upper example can be represented as 10001001011.

We can put together two pieces by vertically flipping the second one (and maybe flipping it horizontally too). After the flip(s) we can find an alignment where the two pieces can be put together to have a height of 3.

Two example pieces:

XXXXXXXXXXX   XXXXXXXX
X   X  X XX     XXX

Second piece flipped vertically and horizontally:

 XXXXXXXXXXX   
 X   X  X XX
  XXX
XXXXXXXX

Pieces put together:

 XXXXXXXXXXX   
 XXXXX  X XX
XXXXXXXX

The example resulted in a total width of 12 blocks.

You should write a program or function which receives two string as input representing the two pieces and outputs an integer the minimal achievable width with a height of 3.

Input

• Two strings consisting of the characters 0 and 1.
• Both strings contain at least one character.
• You may choose to receive the two strings as one joined by a single space.

Output

• A single positive integer, the minimal total width achievable.

Examples

0 0  =>  1

1 0  =>  1

1 1  =>  2

11 111  =>  5

010 0110  =>  5

0010 111  =>  5

00010 11011  =>  6

01010 10101  =>  5

1001 100001  =>  6

1110001100001 1100100101  =>  14

001101010000101 100010110000  =>  16

0010110111100 001011010101001000000  =>  21

0010110111100 001011010101001001100  =>  28

100010100100111101 11100101100010100100000001  =>  27

0010 10111  =>  5

0100 10111  =>  5

0010 11101  =>  5

0100 11101  =>  5

10111 0010  =>  5

10111 0100  =>  5

11101 0010  =>  5

11101 0100  =>  5

This is code golf so the shortest entry wins.

Answer 1

Pyth, 37 35 34 32 31 bytes

eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

Takes input newline separated.

Demonstration, Test Harness.

Explanation:

At the high level, for each combination of normal and reversed strings, we shift the second string to the left by a given number of positions, and check for overlaps with the first string. This is repeated until a shift amount with no overlaps is found. That shift amount is added to the first string length, and the result is compared with the second string length. The higher value is printed.

eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

                            .z     The list of the two input strings.
                       m           Map to 
                        ,d_d       The pair of each string and its reverse.
                     *F            Take the cartesisan product of those lists.
         f                         Filter those pairs of a first string and a 
                                   second string, possibly reversed,
          -\1                      On the absence of the string "1" in
             @V                    The vectorized intersection (intersection
                                   of 0th position, 1st position, etc.) of
               hY                  the first string and
                 >eYT              the second string without the first T elements.
        f                    0     Starting at 0 and counting upwards, find the
                                   lowest T where the result is truthy. 
                                   (where anything passes the inner filter)
    lM.z                           Map the input strings to their lengths.
  X0                               Add the above result to the first entry.
eS                                 Take the maximum of the two values and print.

Answer 2

Pip, 72 70 48 bytes

Fp[aRVa]CP[bRVb]L#a+1{I2NI$+plAE:#$+^pp@1.:0}MNl

Takes the two strings as command-line arguments. Formatted, with comments:

                     a, b initialized from cmdline args; l is [] (implicit)
F p [aRVa]CP[bRVb]   For each possible pair p of a/reverse(a) with b/reverse(b):
 L #a+1 {            Loop for each potential offset of bottom piece:
  I 2 NI $+p         If no 2's in the sum of p:
   l AE: # $+ ^p     Append the max width of elements of p to l (see below for explanation)
  p@1 .: 0           Append a 0 to bottom piece
 }
MNl                  The answer is min(l); print it (implicit)

We're only calculating the overlaps where the bottom piece sticks out to the left, so we need to try it with both top and bottom pieces reversed. Each time through the inner loop, if there are no 2's in the sum, it is a fit; we then tack another zero onto the the end of the bottom piece and try again.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

To find the total width, we split the elements of p into lists of characters and sum. Item-wise operations on uneven-length lists preserve the length of the longer one, so the length of this sum is exactly what we need. (Splitting is necessary because simply summing as numbers will eliminate leading zeros: $+[0101 10] = 111, but $+^[0101 10] = [0 1 1 1].)

C:\> pip.py woodPacking.pip 0010 111
5

Answer 3

Ruby 127 130

This turned out to be so long... :(

->m,n{[[m,n],[m,n.reverse],[n,m],[n,m.reverse]].map{|u,d|[(0..l=u.size).find{|i|(d.to_i(2)<<i)&u.to_i(2)<1}+d.size,l].max}.min}

Tests: http://ideone.com/te8XWk

Readable Ruby:

def pack_length piece1, piece2
  min_possible_packed_length = [
    min_packed_length(piece1, piece2),
    min_packed_length(piece1, piece2.reverse),
    min_packed_length(piece2, piece1),
    min_packed_length(piece2, piece1.reverse)
  ].min

  min_possible_packed_length
end

def min_packed_length up_piece, down_piece
  x = up_piece.to_i 2
  y = down_piece.to_i 2

  # find the smallest shift for the piece placed down 
  # so that they fit together
  min_packed_shift = (0..up_piece.size).find{|i| (y<<i)&x<1 }

  # min pack length cannot be smaller than any of the 
  # two pieces
  [min_packed_shift + down_piece.size, up_piece.size].max
end

Answer 4

JavaScript (ES6) 160

Couldn't make shorter ...

F=(a,b,c=[...b].reverse(),
K=(a,b,t=a.length)=>{
for(e=i=-1;e&&i++<t;)for(e=j=0;u=b[j];j++)e|=u&a[j+i];
return t<i+j?i+j:t
})=>Math.min(K(a,b),K(a,c),K(b,a),K(c,a))

// test

out=x=>O.innerHTML += x+'\n'

test=[
 ['0', '0', 1],['1', '0', 1],['1', '1', 2],['11', '111', 5]
,['010', '0110', 5],['0010', '111', 5],['0010', '10111', 5]
,['00010', '11011', 6],['01010', '10101', 5],['1001', '100001', 6]
,['1110001100001', '1100100101', 14]
,['001101010000101', '100010110000', 16]
,['0010110111100', '001011010101001000000', 21]
,['0010110111100', '001011010101001001100', 28]
,['100010100100111101', '11100101100010100100000001', 27]
,['0010','10111', 5],['0100','10111', 5]
,['0010','11101', 5],['0100','11101', 5]
,['10111','0010', 5],['10111','0100', 5]
,['11101','0010', 5],['11101','0100', 5]
]

test.forEach(t=>{
  r = F(t[0],t[1]),
  out(
    (r==t[2]?'Ok':'Fail') 
    + ' A: '+t[0]+', B: '+t[1]
    + ', Result: '+r + ', Check:  '+t[2])
})

pre { font-size: 10px }

<pre id=O></pre>