Есть два куска дерева. Оба состоят из прямого тела и некоторых дополнительных блоков ниже тела. Пример фрагмента с дополнительными блоками в (0-индексированных) позициях 0,4,7,9,10:

XXXXXXXXXXX
X   X  X XX

Часть может быть представлена ​​в виде 01двоичной последовательности с iсимволом th, показывающим, есть ли блок в iпозиции th. Верхний пример может быть представлен как10001001011 .

Мы можем собрать две части, перевернув вторую по вертикали (и, возможно, перевернув ее по горизонтали). После переворачивания (ей) мы можем найти выравнивание, где две части могут быть соединены, чтобы иметь высоту 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

В результате мы получили общую ширину 12 блоков.

Вы должны написать программу или функцию, которая получает две строки в качестве входных данных, представляющих две части, и выводит целое число минимально достижимой ширины с высотой 3.

вход

• Две строки, состоящие из символов 0и1 .
• Обе строки содержат как минимум один символ.
• Вы можете получить две строки как одну, соединенную одним пробелом.

Выход

• Единственное положительное целое число, минимальная общая достижимая ширина.

Примеры

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

Это код гольф, поэтому выигрывает самый короткий вход.

Pyth, 37 35 34 32 31 байт

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

Вводит новую строку отдельно.

Демонстрация , Испытательный жгут .

Объяснение:

На высоком уровне для каждой комбинации обычных и обращенных строк мы сдвигаем вторую строку влево на заданное количество позиций и проверяем совпадения с первой строкой. Это повторяется до тех пор, пока не будет найдена величина смены без наложений. Эта величина сдвига добавляется к первой длине строки, а результат сравнивается со второй длиной строки. Более высокое значение печатается.

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.

Пип , 72 70 48 байт

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

Принимает две строки в качестве аргументов командной строки. Отформатировано, с комментариями:

                     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)

Мы рассчитываем только перекрытия, когда нижняя часть выступает влево, поэтому мы должны попробовать ее с перевернутыми верхней и нижней частями. Каждый раз, когда в сумме нет 2-х по внутренней петле, это подходит; затем мы добавляем еще один ноль в конец нижней части и пытаемся снова.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

Чтобы найти общую ширину, мы разбиваем элементы pна списки символов и суммы. Поэтапные операции над списками неравной длины сохраняют длину более длинных, поэтому длина этой суммы - именно то, что нам нужно. (Разделение необходимо, потому что простое суммирование в виде чисел исключит начальные нули:, $+[0101 10] = 111но $+^[0101 10] = [0 1 1 1].)

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

Ruby 127 130

Это оказалось так долго ... :(

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

Тесты: http://ideone.com/te8XWk

Читаемый Рубин:

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

JavaScript ( ES6 ) 160

Не могу сделать короче ...

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>