Dinding bata adalah persegi panjang yang terbuat dari bata 1-by-n horisontal yang ditumpuk menjadi baris. Inilah dinding dengan tinggi 4 dan lebar 8, dengan ukuran batu bata ditampilkan di sebelah kanan.

[______][______]    4 4
[__][____][__][]    2 3 2 1
[][______][____]    1 4 3
[____][______][]    3 4 1

Dinding ini tidak stabil karena memiliki kesalahan , tempat di mana dua celah vertikal di antara batu bata berbaris, ditunjukkan di bawah ini dengan parens di batu bata sekitarnya.

[______][______]    
[__][____)(__][]
[][______)(____]
[____][______][]

Tapi, retakan yang berbatasan dengan batu bata ukuran-1 di sebelah kanan tidak membentuk kesalahan karena dipisahkan oleh satu baris.

Tulis kode yang menemukan dan menampilkan dinding kokoh yang dibangun dari batu bata dengan ukuran yang ditentukan. Bytes paling sedikit menang.

Memasukkan

Daftar ukuran bata yang tidak kosong (angka positif) dan tinggi minimal 2. Daftar ini dapat diurutkan jika diinginkan. Anda dapat juga menghitung jumlah batu bata dari setiap ukuran.

Keluaran

Gambar dinding persegi panjang yang mantap dari ketinggian yang diperlukan yang menggunakan semua batu bata yang diberikan. Cetak atau kembalikan sebagai string dengan baris baru.

Gambarlah bata berukuran n sebagai karakter 2n, garis bawah dikelilingi oleh tanda kurung.

1: []
2: [__]
3: [____]
4: [______]
...

Input dijamin memiliki setidaknya satu solusi. Jika ada banyak, Anda harus tetap hanya menggambar satu dinding.

Tidak ada batasan waktu; gunakan sebanyak mungkin kekerasan yang Anda inginkan. Algoritme Anda secara teori seharusnya bekerja pada input dengan ukuran berapa pun.

Kasus uji:

Ada beberapa solusi, jadi output Anda mungkin berbeda.

>> [1, 1, 2, 2], 2
[][__]
[__][]

>> [1, 1, 1, 2, 2, 2, 2, 3], 2
[__][____][__]
[][__][][__][]

>> [1, 1, 2, 2, 3, 3, 3, 3], 3
[][__][____]
[__][____][]
[____][____]

>> [1, 2, 3, 4, 5, 6, 7, 8, 9], 5
[][______________]
[__][____________]
[________________]
[____][__________]
[______][________]

>> [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5
[][__][__]
[__][__][]
[][__][__]
[__][__][]
[][__][__]

Perl, 166 170 194

Tugas yang sempurna untuk bahasa yang dibuat oleh Larry Wall.

#!perl -pa
$_=(1x($x=2/($y=pop@F)*map{1..$_}@F)."
")x$y;sub
f{my$l=$_;$-|=!@_;for$=(@_){$Z=__
x~-$=;$f=0;s/(11){$=}/[$Z]/&!/\]..{$x}\[/s&&f(grep$=ne$_||$f++,@_);$-or$_=$l}}f@F

Brute force, tetapi cukup cepat pada test case (<1s). Pemakaian:

$ perl ~/wall.pl <<<"1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 5"
[][__][__]
[__][__][]
[][__][__]
[__][__][]
[][__][__]

Ujilah aku .

CJam, 94 92 82 byte

Ini adalah versi 92 byte. Versi 82 ​​byte berikut.

l~1$,:L,:)m*{1bL=},\e!\m*{~W<{/(\e_}%}%{::+)-!},{{_,,\f<1fb}%2ew{:&,(},!}={{(2*'_*'[\']}/N}/

Ini mem-partisi bata menjadi segala cara yang mungkin dan hanya mengambil satu yang valid. Kekuatan yang cukup kasar untuk saat ini tetapi masih menjalankan test case terakhir dalam waktu sekitar 10 detik pada Java Interpreter di komputer saya.

Penjelasan :

Kode ini dibagi menjadi 5 bagian:

1) Diberikan array panjang L, bagaimana kita semua dapat mempartisi menjadi Hbeberapa bagian.

l~1$,:L,:)m*{1bL=},
l~                     e# Read the input as string and evaluate it.
  `$,:L                e# Copy the array and take its length. Store that in L
       ,:)             e# Get an array of 1 to L
          m*           e# Cartesian power of array 1 to L of size H (height of wall)
            {1bL=},    e# Take only those parts whose sum is L

Setelah ini, kami memiliki semua cara yang mungkin untuk memecah array input kami menjadi lapisan H bata.

2) Dapatkan semua permutasi dari array input dan kemudian lanjutkan semua partisi untuk semua permutasi

\e!\m*{~W<{/(\e_}%}%
\e!                    e# Put the input array on top of stack and get all its permutations
   \m*                 e# Put the all possible partition array on top and to cartesian
                       e# product of the two permutations. At this point, every
                       e# permutation of the input array is linked up with every
                       e# permutation of splitting L sized array into H parts
      {           }%   e# Run each permutation pair through this
       ~W<             e# Unwrap and remove the last part from the partition permutation
          {     }%     e# For each part of parts permutation array
           /           e# Split the input array permutation into size of that part
            (\         e# Take out the first part and put the rest of the parts on top
              e_       e# Flatten the rest of the parts so that in next loop, they can be
                       e# split into next part length

Setelah ini, kita memiliki semua tata letak yang mungkin dari batu bata input ke Hdinding bata berlapis.

3) Saring hanya tata letak yang memiliki panjang bata yang sama

{::+)-!},
{      },              e# Filter all brick layouts on this condition
 ::+                   e# Add up brick sizes in each layer
    )-!                e# This checks if the array contains all same lengths.

Setelah akhir filter ini, semua tata letak yang tersisa akan menjadi persegi panjang sempurna.

4) Keluarkan tata letak bata pertama yang cocok dengan kriteria stabilitas

{{_,,\f<1fb}%2ew{:&,(},!}=
{                       }=   e# Choose the first array element that leaves truthy on stack
 {         }%                e# For each brick layer
  _,,                        e# Create an array of 0 to layer length - 1
     \f<                     e# Get all sublists starting at 0 and ending at 0
                             e# through length - 1
        1fb                  e# Get sum of each sub list. This gives us the cumulative
                             e# length of each brick crack except for the last one
           2ew               e# Pair up crack lengths for every adjacent layer
              {    },        e# Filter layer pairs
               :&            e# See if any cumulative crack length is same in any two
                             e# adjacent layers. This means that the layout is unstable
                 ,(          e# make sure that length of union'd crack lengths is greater
                             e# than 1. 1 because 0 will always be there.
                     !       e# If any layer is filtered through this filter,
                             e# it means that the layer is unstable. Thus negation

Setelah langkah ini, kita cukup mencetak tata letaknya

5) Cetak tata letaknya

{{(2*'_*'[\']}/N}/
{               }/           e# For each brick layer
 {           }/              e# For each brick
  (2*'_*                     e# Get the (brick size - 1) * 2 underscores
        '[\']                e# Surround with []
               N             e# Newline after each layer

Cobalah online di sini

82 byte

l~:H;{e_mrH({H-X$,+(mr)/(\e_}%_::+)-X${_,,\f<1fb}%2ew{:&,(},+,}g{{(2*'_*'[\']}/N}/

Ini hampir mirip dengan versi 92 byte, kecuali bahwa ia memiliki sentuhan keacakan. Jika Anda telah membaca penjelasan untuk versi 92 byte, maka dalam versi 82 ​​byte, bagian 3, 4 dan 5 persis sama, sedangkan alih-alih mengulangi semua permutasi dari bagian 1 dan 2, versi ini secara acak menghasilkan salah satu dari permutasi pada suatu waktu, mengujinya menggunakan bagian 3 dan 4, dan kemudian memulai kembali proses jika pengujian bagian 3 dan 4 gagal.

Ini mencetak hasilnya dengan sangat cepat untuk 3 kasus uji pertama. Ketinggian = 5 test case belum memberikan output di komputer saya.

Penjelasan perbedaannya

l~:H;{e_mrH({H-X$,+(mr)/(\e_}%_::+)-X${_,,\f<1fb}%2ew{:&,(},+,}g
l~:H;                           e# Eval the input and store the height in H
     {   ...   }g               e# A do-while loop to iterate until a solution is found
      e_mr                      e# Flatten the array and shuffle it.
          H({               }%  e# This is the random partition generation loop
                                e# Run the loop height - 1 times to get height parts
             H-X$,+(            e# While generating a random size of this partition, we
                                e# have to make sure that the remaining parts get at least
                                e# 1 brick. Thus, this calculation
                    mr)         e# Get a random size. Make sure its at least 1
                       /(\e_    e# Similar to 92's part 2. Split, pop, swap and flatten

_::+)-                          e# 92's part 3. Copy and see if all elements are same
      X${_,,\f<1fb}%2ew{:&,(},  e# 92's part 4. Copy and see if layers are stable
+,                              e# Both part 3 and 4 return empty array if
                                e# the layout is desirable. join the two arrays and
                                e# take length. If length is 0, stop the do-while

Ide untuk versi ini diberikan oleh randomra (Get it?)

Coba yang ini online

Python 2, 680 670 660 byte

Saya tidak tahu mengapa saya bersikeras untuk memiliki "golf" yang sangat panjang ini ... tapi bagaimanapun, ini dia.

M,L,R,N=map,len,range,None
exec"J=@:M(''.join,x);B=@:'['+'_'*2*~-x+']';K=@:M(B,x);W=@:J(M(K,x));C=@:set(M(sum,[x[:i]for i in R(L(x))]))-{0};T=@,w:w[x:]+w[:x]\ndef F(i):f=filter(@:i[x-1]&i[x],R(1,L(i)));return f and f[0]".replace('@','lambda x')
def P(e,x,i,w,h):
 for j in[-~_%h for _ in R(i-1,h+i-2)]:
    for s in R(w):
     if not e&C(T(s,x[j])):return j,s
 return N,N
def b(l,h):
 w,d=[[]for _ in R(h)],2*sum(l)/h
 for _ in l[::-1]:q=M(L,W(w));w[[q.index(i)for i in sorted(q)if i+L(B(_))<=d][-1]]+=_,
 g=M(C,w);i=F(g)
 while i:
    e=g[i-1];j,s=P(e,w,i,d,h)
    if j!=N:w[j]=T(s,w[j]);w[i],w[j]=w[j],w[i];g=M(C,w);i=F(g)
    else:b(T(-1,l),h);return
 print'\n'.join(W(w))

Ini membutuhkan output dalam urutan menaik, dan dipanggil via b(brick_sizes, height).

Kasus uji:

>>> tests = [([1, 1, 2, 2], 2),([1, 1, 1, 2, 2, 2, 2, 3], 2), ([1, 1, 2, 2, 3, 3, 3, 3], 3), ([1, 2, 3, 4, 5, 6, 7, 8, 9], 5), ([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5)]
>>> for t in tests:
...     b(*t); print
... 
[__][]
[][__]

[____][__][__]
[][][__][__][]

[____][____]
[__][__][][]
[____][____]

[________________]
[______________][]
[____________][__]
[__________][____]
[________][______]

[__][__][]
[][__][__]
[__][__][]
[][__][__]
[__][__][]

Cara kerjanya adalah:

1. Tetapkan bata (terpanjang-> terpendek) ke lapisan, mencoba untuk mengisi setiap lapisan sebelum pindah ke yang berikutnya.
2. Setiap kali lapisan yang berdekatan tidak stabil, cobalah menukar lapisan dan menggeser batu bata sampai Anda menemukan sesuatu yang berhasil.
3. Jika tidak ada yang berhasil, pindahkan bata terpanjang ke depan daftar ukuran dan ulangi.

Haskell, 262 byte

import Data.List
c=concat
n=init.scanl1(+)
1%l=[[[l]]]
n%l=[map(h:)(c$(n-1)%t)|(h,t)<-map(`splitAt`l)[1..length l]]
v[x]=1<2
v(x:y:z)=sum x==sum y&&n x==n x\\n y&&v(y:z)
l#n=unlines$map(>>=(\b->'[':replicate(2*b-2)'_'++"]"))$head$filter v$c.(n%)=<<permutations l

Contoh penggunaan:

*Main> putStr $  [1, 2, 3, 4, 5, 6, 7, 8, 9] # 5
[______][________]
[__________][____]
[____________][__]
[][______________]
[________________]

*Main> putStr $ [1, 1, 2, 2, 3, 3, 3, 3] # 3
[____][____]
[__][__][][]
[____][____]

Cara kerjanya: fungsi utama #mengambil daftar l(daftar batu bata) dan angka h(tinggi) dan membagi semua permutasi lmenjadi hsublists di semua posisi yang mungkin (via fungsi %, misalnya 2%[1,2,3,4]-> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]). Itu membuat mereka di mana dua elemen berturut-turut memiliki jumlah yang sama (yaitu panjang yang sama dalam batu bata) dan daftar subtotal tidak memiliki elemen umum (yaitu retak tidak berbaris, berfungsi v). Ambil daftar pertama yang cocok dan buatlah serangkaian batu bata.

Python 2, 528 , 417 , 393 , 381

Solusi bruteforce yang sangat panjang. Ini bekerja tetapi itu saja, alam semesta mungkin berakhir sebelum mendapatkan hasil untuk kasus uji terakhir.

exec u"from itertools import*;m=map;g=@w,n:([[w]],[[w[:i]]+s#i?range(1,len(w))#s?g(w[i:],n-1)])[n>1];r=@x:set(m(sum,[x[:i]#i?range(1,len(x))]));f=@w:1-all(m(@(x,y):not x&y,zip(m(r,w[:-1]),m(r,w[1:]))));a=@s,h:['\\n'.join([''.join(['[%s]'%(' '*(s-1)*2)#s?r])#r?o])#p?permutations(s)#o?g(p,h)if len(set([sum(r)#r?o]))<2 and~-f(o)][0]".translate({64:u"lambda ",35:u" for ",63:u" in "})

a adalah fungsi utama:

>> a([1, 1, 2, 2], 2)
'[][  ]\n[  ][]'

JavaScript (ES6) 222 232 265 279 319

Masih harus bermain golf. Yang ini menemukan semua solusi, output yang terakhir ditemukan, dan ini cukup cepat.

Jalankan cuplikan di Firefox untuk menguji

f=(n,h,b=[],s=0)=>
  (R=(z,l,p,k,t)=>
    z?b.map((v,a)=>
      v&&k.indexOf(v=t+a)<0&v<=s&&(
        --b[a],h=l+`[${'__'.repeat(a-1)}]`,
        v-s?R(z,h,[...p,v],k,v):R(z-1,h+'\n',[],p,0),
        ++b[a]
      ))
    :n=l
  )(h,'',[],[],0,n.map(n=>(b[n]=-~b[n],s+=n)),s/=h)&&n

// Test suite


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

;[ 
 [[1, 1, 2, 2], 2], [[1, 1, 1, 2, 2, 2, 2, 3], 2], [[1, 1, 2, 2, 3, 3, 3, 3], 3]
,[[1, 2, 3, 4, 5, 6, 7, 8, 9], 5], [[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5]]
.forEach(([a,b])=>out(a+' '+b+'\n'+f(a,b)))

<pre id=OUT></pre>

Tidak Diikat Dan dijelaskan

function f(n, h) {
  var b=[], s=0, result // in golfed version will re-use n for result variable
  n.forEach(function (n) {
    b[n] = -~b[n] // group equal input numbers in buckets
    s+=n          // calc sum of input numbers
  });
  // example of buckets: input 1,1,4,1,5,4 -> b[1]=3,b[4]=2,b[5]=1
  s /= h // total sum / height => sum expected for each brick layer

  // recursive scan function 
  function R(z, // layer count, from h downto 1
             l, // output so far
             p, // current layer partial sums array, mark intervals between bricks
             k, // prev layer parial sums, checked to avoid faulds
             t  // current partial sum 
             ) 
  {
    if (z > 0) 
    { // still building
      b.forEach( function (v,a) { // a:number from input list, v: repeat count 
        var w, m   // locals (in golfed version, reuse other variables avoid defining locals)
        w = t + a; // increased running total for current layer
        if (v != 0  // repeat count still > 0 
           && k.indexOf(w) < 0 // running total not found on list in prev layer (no fault)
           && w <= s) // current layer length not exceeded
        {
           --b[a]; // decrease repeat count, number used one more time
           m = l+"["+ '__'.repeat(a-1) + "]"; // new output with a brick added
           // l is not changed, it will be used again in this loop
           if (w == s) 
           {   // layer complete, go to next (if any)
               // recurse, new layer, add newline to output, p goes in k, and t start at 0 again
               R(z-1, m+'\n', [], p, 0); 
           }
           else
           {   // layer still to complete
               // recurse, same layer, m goes in l, add current sum to array p
               R(z, m, [...p,w], k, w);
           }
           ++b[a]; // restore value of repeat count for current loop
        }
      })
    }   
    else
    { // z == 0, all layers Ok, solution found, save in result and go on to next
      result = l;
    }
  }

  R(h,'',[],[],0);
  return result; // this is the last solution found
}

Python 2, metode grid (290 karakter)

x,h=input()
from itertools import *
w = sum(x)*2/h
for p in permutations(x):
 bricks = ''.join('[' + '_'*(2*n-2) + ']' for n in p)
 cols = map(''.join,zip(*zip(*[iter(bricks)]*w)))
 if all(c=='[' for c in cols[0]) and all(c==']' for c in cols[-1]) and not any(']]' in col or '[[' in col for col in cols[1:-1]):
  print('\n'.join(map(''.join,zip(*cols))))
  print()

Metode di sini adalah Anda mentransposisikan grid dan mencari [[atau ]]di mana saja di kolom. Anda juga menguji bahwa semua batu bata di sisi kiri dan kanan berbaris: yang lucu di sini adalah untuk menguji bahwa semua elemen string adalah sama:'[[[[[['.strip('[')==''

versi mini di atas:

x,h=input()
from itertools import*
w=sum(x)*2/h
z=zip
j=''.join
for p in permutations(x):
 C=map(j,z(*z(*[iter(j('['+'_'*(2*n-2)+']'for n in p))]*w)))
 if C[0].strip('[')==''and C[-1].strip(']')==''and not any(']]'in c or '[['in c for c in C[1:-1]):
  print('\n'.join(map(j,z(*C))))
  break

Ini mungkin bisa dilakukan dengan lebih mudah dalam bahasa manipulasi-matriks.

... atau penyalahgunaan regex, yang memungkinkan kami menggabungkan kondisi "blok sejajar" dengan kondisi "tidak ada celah":

Katakanlah lebar dinding itu w = 6. Lokasi substring "[..... [", dan "] .....]" harus persis set {0, w-1, w, 2w-1,2w, 3w-1 ,. ..}. Tidak adanya pada titik-titik itu berarti batu bata 'linewrap' seperti:

       v
[][__][_
___][__]
       ^

Keberadaan BUKAN pada titik-titik itu berarti ada 'celah' yang tidak stabil di dinding:

     vv
[][__][]
[    ][]
     ^^

Oleh karena itu kami mengurangi masalah untuk menetapkan kesetaraan, di mana set dalam pertanyaan adalah indeks dari kecocokan ekspresi reguler.

# assume input is x and height is h

from itertools import *
import re
w=sum(x)*2/h

STACKED_BRACKET_RE = r'(?=\[.{%i}\[|\].{%i}\])'%(w-1,w-1)  # ]....] or [....[
STRING_CHUNK_RE = '.{%i}'%w  # chunk a string with a regex!
bracketGoal = set().union(*[(x*w,x*w+w-1) for x in range(h-1)])  # expected match locations

for p in permutations(x):
 string = ''.join('['+'_'*(2*n-2)+']'for n in p)
 bracketPositions = {m.start() for m in re.finditer(STACKED_BRACKET_RE,string)}
 print(string, bracketPositions, bracketGoal, STACKED_BRACKET_RE) #debug
 if bracketPositions==bracketGoal:
  break

print('\n'.join(re.findall(STRING_CHUNK_RE,string)))

Python, metode regexp (304 karakter):

from itertools import*
import re
x,h=input()
w=sum(x)*2/h
for p in permutations(x):
 s=''.join('['+'_'*(2*n-2)+']'for n in p)
 if {m.start()for m in re.finditer(r'(?=\[.{%i}\[|\].{%i}\])'%(w-1,w-1),s)}==set().union(*[(x*w,x*w+w-1) for x in range(h-1)]):
  break

print('\n'.join(re.findall('.{%i}'%w,s)))

Matlab (359)

function p(V),L=perms(V);x=sum(V);D=find(rem(x./(1:x),1)==0);for z= 2:numel(D-1)for y=1:numel(L),x=L(y,:);i=D(z);b=x;l=numel(x);for j=1:l,for k=j-1:-1:2,m=sum(x(1:k));if mod(m,i),if mod(m,i)<mod(sum(x(1:k-1)),i)||sum(x(1:j))-m==i,b=0;,end,end,end,end,if b,for j=1:l,fprintf('[%.*s]%c',(b(j)-2)+b(j),ones(9)*'_',(mod(sum(x(1:j)),i)<1)*10);end,return,end;end,end

Memasukkan

vektor bilangan bulat, contoh: p ([1 1 2 2 3])

Keluaran

contoh skema dinding:

[____]

[__][]

[][__]