Istnieją dwa kawałki drewna. Oba składają się z prostego korpusu i kilku dodatkowych bloków poniżej korpusu. Przykładowy kawałek z dodatkowymi blokami w pozycjach (0-indeksowanych) 0,4,7,9,10:

XXXXXXXXXXX
X   X  X XX

Kawałek może być reprezentowany jako 01sekwencja binarna ze iznakiem th pokazującym, czy w ipozycji th znajduje się blok . Górny przykład można przedstawić jako 10001001011.

Możemy złożyć dwa elementy, obracając drugi pionowo (i być może również poziomo). Po odwróceniu (ach) możemy znaleźć wyrównanie, w którym dwa elementy mogą być złożone, aby mieć wysokość 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

W wyniku uzyskano całkowitą szerokość 12 bloków.

Powinieneś napisać program lub funkcję, która odbiera dwa ciągi jako dane wejściowe reprezentujące dwa kawałki i wyprowadza liczbę całkowitą o minimalnej możliwej do osiągnięcia szerokości o wysokości 3.

Wejście

• Dwa ciągi znaków złożone z znaków 0i 1.
• Oba ciągi zawierają co najmniej jeden znak.
• Możesz wybrać otrzymanie dwóch ciągów jako jednego połączonego pojedynczym odstępem.

Wynik

• Pojedyncza dodatnia liczba całkowita, minimalna możliwa do osiągnięcia szerokość całkowita.

Przykłady

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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Pyth, 37 35 34 32 31 bajtów

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

Oddziela wprowadzany znak nowej linii.

Demonstracja , uprząż testowa .

Wyjaśnienie:

Na wysokim poziomie, dla każdej kombinacji normalnych i odwróconych łańcuchów, przesuwamy drugi łańcuch w lewo o określoną liczbę pozycji i sprawdzamy, czy pierwszy łańcuch się pokrywa. Jest to powtarzane do momentu znalezienia wielkości przesunięcia bez nakładania się. Ta wartość przesunięcia jest dodawana do długości pierwszego łańcucha, a wynik jest porównywany z długością drugiego łańcucha. Drukowana jest wyższa wartość.

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.

Pip , 72 70 48 bajtów

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

Traktuje dwa ciągi jako argumenty wiersza poleceń. Sformatowane, z komentarzami:

                     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)

Obliczamy tylko zakładki, w których dolna część wystaje w lewo, więc musimy spróbować z odwróconą górną i dolną częścią. Za każdym razem przez wewnętrzną pętlę, jeśli w sumie nie ma 2, jest to dopasowanie; następnie przyczepiamy kolejne zero na końcu dolnej części i próbujemy ponownie.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

Aby znaleźć całkowitą szerokość, podzieliliśmy elementy pna listy znaków i sumę. Operacje na listach o nierównych długościach zachowują długość dłuższej, więc długość tej sumy jest dokładnie tym, czego potrzebujemy. (Podział jest konieczny, ponieważ zwykłe sumowanie jako liczby wyeliminuje wiodące zera:, $+[0101 10] = 111ale $+^[0101 10] = [0 1 1 1].)

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

Ruby 127 130

To okazało się tak długie ... :(

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

Testy: http://ideone.com/te8XWk

Czytelny Rubin:

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

Nie można skrócić ...

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>