Il y a deux morceaux de bois. Les deux se composent d'un corps droit et de quelques blocs supplémentaires sous le corps. Un exemple de pièce avec des blocs supplémentaires aux positions (indexées 0) 0,4,7,9,10:

XXXXXXXXXXX
X   X  X XX

Le morceau peut être représenté comme une 01séquence binaire avec le ith caractère montrant s'il y a un bloc à la ith position. L'exemple supérieur peut être représenté par 10001001011.

Nous pouvons assembler deux morceaux en retournant verticalement le second (et peut-être en le retournant aussi horizontalement). Après le (s) flip (s), nous pouvons trouver un alignement où les deux pièces peuvent être assemblées pour avoir une hauteur de 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

L'exemple a donné une largeur totale de 12 blocs.

Vous devez écrire un programme ou une fonction qui reçoit deux chaînes en entrée représentant les deux pièces et génère un entier de la largeur minimale réalisable avec une hauteur de 3.

Contribution

• Deux chaînes composées des caractères 0et 1.
• Les deux chaînes contiennent au moins un caractère.
• Vous pouvez choisir de recevoir les deux chaînes comme une jointe par un seul espace.

Production

• Un seul entier positif, la largeur totale minimale réalisable.

Exemples

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

C'est le golf de code, donc l'entrée la plus courte gagne.

Pyth, 37 35 34 32 31 octets

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

Prend la nouvelle ligne d'entrée séparée.

Démonstration , test de harnais .

Explication:

Au niveau supérieur, pour chaque combinaison de chaînes normales et inversées, nous décalons la deuxième chaîne vers la gauche d'un nombre donné de positions et vérifions les chevauchements avec la première chaîne. Cette opération est répétée jusqu'à ce qu'un montant de décalage sans chevauchement soit trouvé. Cette quantité de décalage est ajoutée à la première longueur de chaîne et le résultat est comparé à la deuxième longueur de chaîne. La valeur la plus élevée est imprimée.

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 octets

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

Prend les deux chaînes comme arguments de ligne de commande. Formaté, avec commentaires:

                     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)

Nous calculons uniquement les chevauchements là où la pièce du bas dépasse vers la gauche, nous devons donc l'essayer avec les pièces du haut et du bas inversées. Chaque fois à travers la boucle intérieure, s'il n'y a pas de 2 dans la somme, c'est un ajustement; nous plaçons ensuite un autre zéro à la fin de la pièce inférieure et réessayons.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

Pour trouver la largeur totale, nous avons divisé les éléments de pen listes de caractères et somme. Les opérations par élément sur des listes de longueur inégale préservent la longueur de la plus longue, de sorte que la longueur de cette somme est exactement ce dont nous avons besoin. (Le fractionnement est nécessaire car la simple addition sous forme de nombres éliminera les zéros non significatifs:, $+[0101 10] = 111mais $+^[0101 10] = [0 1 1 1].)

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

Rubis 127 130

Cela s'est avéré si 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

Rubis lisible:

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

Impossible de raccourcir ...

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>