Potongan kayu kemasan

14

Ada dua potong kayu. Keduanya terdiri dari tubuh lurus dan beberapa blok tambahan di bawah tubuh. Contoh karya dengan blok tambahan di posisi (diindeks 0) 0,4,7,9,10:

XXXXXXXXXXX
X   X  X XX

Potongan dapat direpresentasikan sebagai 01urutan biner dengan ikarakter th menunjukkan jika ada blok di iposisi th. Contoh atas dapat direpresentasikan sebagai 10001001011.

Kita dapat mengumpulkan dua potong dengan membalik secara vertikal potongan kedua (dan mungkin membaliknya juga secara horizontal). Setelah flip, kita dapat menemukan keselarasan di mana kedua potongan dapat disatukan untuk memiliki ketinggian 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

Contoh menghasilkan total lebar 12 blok.

Anda harus menulis sebuah program atau fungsi yang menerima dua string sebagai input yang mewakili dua bagian dan menghasilkan bilangan bulat dengan lebar minimal yang dapat dicapai dengan ketinggian 3.

Memasukkan

  • Dua string terdiri dari karakter 0dan 1.
  • Kedua string mengandung setidaknya satu karakter.
  • Anda dapat memilih untuk menerima dua string sebagai satu bergabung dengan satu ruang.

Keluaran

  • Integer positif tunggal, total lebar minimal dapat dicapai.

Contohnya

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

Ini adalah kode golf sehingga entri terpendek menang.

randomra
sumber
Apakah bagian dalam contoh pertama seharusnya menjadi bagian 1 di bagian kedua dari contoh? Jika demikian, maka salah satunya salah.
mdc32
@ mdc32 Mereka bukan bagian yang sama tetapi mengubah yang pertama untuk menghindari kebingungan.
randomra

Jawaban:

7

Pyth, 37 35 34 32 31 byte

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

Membagi input baris baru.

Demonstrasi , Test Harness .

Penjelasan:

Pada level tinggi, untuk setiap kombinasi string normal dan terbalik, kami menggeser string kedua ke kiri dengan sejumlah posisi tertentu, dan memeriksa tumpang tindih dengan string pertama. Ini diulangi sampai jumlah shift tanpa tumpang tindih ditemukan. Jumlah shift itu ditambahkan ke panjang string pertama, dan hasilnya dibandingkan dengan panjang string kedua. Nilai yang lebih tinggi dicetak.

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.
isaacg
sumber
4

Pip , 72 70 48 byte

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

Mengambil dua string sebagai argumen baris perintah. Diformat, dengan komentar:

                     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)

Kami hanya menghitung tumpang tindih di mana bagian bawah menonjol ke kiri, jadi kami harus mencobanya dengan bagian atas dan bawah terbalik. Setiap kali melalui loop dalam, jika tidak ada 2 dalam jumlah, itu cocok; kami kemudian menempelkan nol lagi di ujung potongan bawah dan coba lagi.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

Untuk menemukan lebar total, kami membagi elemen pmenjadi daftar karakter dan jumlah. Operasi item-bijaksana pada daftar panjang tidak merata mempertahankan panjang yang lebih panjang, jadi panjang jumlah ini adalah persis apa yang kita butuhkan. (Membagi diperlukan karena menjumlahkan sebagai angka akan menghilangkan nol terkemuka:, $+[0101 10] = 111tapi $+^[0101 10] = [0 1 1 1].)

C:\> pip.py woodPacking.pip 0010 111
5
DLosc
sumber
3

Ruby 127 130

Ini ternyata sangat lama ... :(

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

Tes: http://ideone.com/te8XWk

Ruby yang Dapat Dibaca:

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
Cristian Lupascu
sumber
Bisakah Anda menguji contoh baru yang ditambahkan? Bagian itu [[m,n],[m,n.reverse],[n,m],[n,m.reverse]]mungkin salah. (Saya tidak yakin tetapi saya membuat kesalahan serupa.)
randomra
@randomra Tentu! Silakan lihat tautan tes; Saya menambahkan tes baru di sana.
Cristian Lupascu
Terima kasih, maaf atas kerumitan ekstra. Intuisi saya adalah bahwa Anda akan membutuhkan [n.reverse,m]alih-alih [n,m.reverse]tetapi saya tidak tahu Ruby.
randomra
@randomra sebenarnya yang gagal tes '0010110111100', '001011010101001001100'mengatakan Diharapkan: 28, Aktual: 30 . Semua tes lainnya lulus. Jadi Anda telah melakukan pekerjaan yang baik untuk menguji kasus sudut. :)
Cristian Lupascu
1

JavaScript ( ES6 ) 160

Tidak bisa membuat lebih pendek ...

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>

edc65
sumber