Ceglana ściana to prostokąt wykonany z poziomych cegieł 1 na n, ułożonych w rzędy. Oto ściana o wysokości 4 i szerokości 8, z rozmiarami cegieł pokazanymi po prawej stronie.

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

Ta ściana jest niestabilna, ponieważ ma wadę , miejsce, w którym dwa pionowe pęknięcia między cegłami ustawiają się w linii, pokazane poniżej z parenami w otaczających cegłach.

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

Ale pęknięcia graniczące z cegłami rozmiaru 1 po prawej stronie nie stanowią usterki, ponieważ są one oddzielone rzędem.

Napisz kod, który znajdzie i wyświetli stabilną ścianę zbudowaną z cegieł o określonych rozmiarach. Wygrywa najmniej bajtów.

Wejście

Niepusta lista rozmiarów cegieł (liczby dodatnie) i wysokości co najmniej 2. Ta lista może być sortowana, jeśli chcesz. Alternatywnie możesz wziąć liczbę cegieł każdego rozmiaru.

Wydajność

Zdjęcie stałej prostokątnej ściany o wymaganej wysokości, w której wykorzystano wszystkie podane cegły. Wydrukuj lub zwróć jako ciąg z nowymi liniami.

Narysuj cegłę o rozmiarze n jako 2n znaków, podkreślenia otoczone nawiasami.

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

Gwarantujemy, że dane wejściowe mają co najmniej jedno rozwiązanie. Jeśli jest ich wiele, nadal powinieneś narysować tylko jedną ścianę.

Nie ma ograniczeń czasowych; używaj tyle brutalnej siły, ile chcesz. Twój algorytm powinien teoretycznie działać na wejściach dowolnej wielkości.

Przypadki testowe:

Istnieje wiele rozwiązań, więc wyniki mogą być inne.

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

Idealne zadanie dla języka stworzonego przez Larry'ego Walla.

#!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

Brutalna siła, ale dość szybko na testach (<1s). Stosowanie:

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

Przetestuj mnie .

CJam, 94 92 82 bajtów

To jest wersja 92 bajtów. Następuje wersja 82-bajtowa.

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

To dzieli cegły na wszystkie możliwe sposoby i bierze tylko ten, który jest ważny. Jak na razie dość brutalna siła, ale nadal wykonuje ostatni test w około 10 sekundach na Java Interpreter na moim komputerze.

Objaśnienie :

Kod jest podzielony na 5 części:

1) Biorąc pod uwagę tablicę długości L, w jaki sposób możemy podzielić ją na Hczęści.

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

Następnie mamy wszystkie możliwe sposoby podziału naszej tablicy wejściowej na warstwy cegieł H.

2) Uzyskaj wszystkie permutacje tablicy wejściowej, a następnie uzyskaj wszystkie partycje dla wszystkich permutacji

\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

Następnie mamy wszystkie możliwe układy cegieł wejściowych w Hceglany mur warstwowy.

3) Filtruj tylko te układy, których długości cegieł są takie same

{::+)-!},
{      },              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.

Po zakończeniu tego filtra wszystkie pozostałe układy byłyby idealnymi prostokątami.

4) Wyjmij pierwszy układ klocków, który spełnia kryteria stabilności

{{_,,\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

Po tym kroku musimy po prostu wydrukować układ

5) Wydrukuj układ

{{(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

Wypróbuj online tutaj

82 bajty

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

Jest to prawie podobne do wersji 92-bajtowej, z tym wyjątkiem, że ma odrobinę losowości. Jeśli przeczytałeś wyjaśnienie dla wersji 92-bajtowej, to w wersji 82-bajtowej części 3, 4 i 5 są dokładnie takie same, a zamiast iteracji po wszystkich permutacjach z części 1 i 2, ta wersja po prostu losowo generuje jeden z permutacja na raz, testuje ją za pomocą części 3 i 4, a następnie ponownie uruchamia proces, jeśli testy części 3 i 4 nie powiodą się.

To bardzo szybko drukuje wyniki dla pierwszych 3 przypadków testowych. Przypadek testowy wysokość = 5 nie ma jeszcze danych wyjściowych na moim komputerze.

Wyjaśnienie różnicy

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

Pomysł na tę wersję został podany przez randomra (rozumiesz?)

Wypróbuj ten online

Python 2, 680 670 660 bajtów

Nie wiem, dlaczego nalegam na te długie golfa ... ale tak czy inaczej, proszę bardzo.

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

Wymaga to wyjścia w posortowanej kolejności rosnącej i jest wywoływane przez b(brick_sizes, height).

Przypadki testowe:

>>> 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
... 
[__][]
[][__]

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

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

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

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

Działa to w następujący sposób:

1. Przypisz cegły (najdłuższe-> najkrótsze) do warstw, próbując wypełnić każdą warstwę przed przejściem do następnej.
2. Ilekroć sąsiednie warstwy są niestabilne, spróbuj zamieniać warstwy i przesuwać cegły, aż znajdziesz coś, co działa.
3. Jeśli nic nie działa, przenieś najdłuższą cegłę na początek listy rozmiarów i powtórz.

Haskell, 262 bajty

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

Przykładowe użycie:

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

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

Jak to działa: główna funkcja #pobiera listę l(listę cegieł) i liczbę h(wysokość) i dzieli wszystkie permutacje lna hlisty podrzędne we wszystkich możliwych pozycjach (za pomocą funkcji %, np. 2%[1,2,3,4]-> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]). Utrzymuje te, w których dwa kolejne elementy mają tę samą sumę (tj. Taką samą długość w cegłach), a listy sum częściowych nie mają wspólnych elementów (tj. Pęknięcia nie ustawiają się w linii, funkcja v). Weź pierwszą pasującą listę i zbuduj ciąg cegieł.

Python 2, 528 , 417 , 393 , 381

Bardzo długie, brutalne rozwiązanie. Działa, ale o to chodzi, wszechświat może się skończyć, zanim otrzyma wynik dla ostatniego przypadku testowego.

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 jest główną funkcją:

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

JavaScript (ES6) 222 232 265 279 319

Nadal do gry w golfa. Ten znajduje wszystkie rozwiązania, wyświetla tylko ostatnie znalezione i jest dość szybki.

Uruchom snippet w przeglądarce Firefox, aby przetestować

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>

Niegolfowany i wyjaśniony

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, metoda grid (290 znaków)

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()

Metoda jest tu Państwo transpozycji siatkę i szukać [[albo ]]gdziekolwiek w kolumnach. Testujesz również, czy wszystkie cegły po lewej i prawej stronie ściany są ustawione w linii: urocze jest sprawdzenie, czy wszystkie elementy sznurka są takie same:'[[[[[['.strip('[')==''

mini wersja powyższego:

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

Prawdopodobnie można to zrobić łatwiej w języku manipulacji matrycą.

... lub nadużywanie wyrażeń regularnych, co pozwala nam łączyć warunek „blokuj wyrównanie na końcach” z warunkiem „brak pęknięć”:

Powiedzmy, że szerokość ściany wynosiła w = 6. Lokalizacje podłańcucha „[..... [” i „] .....]” muszą być dokładnie ustawione {0, w-1, w, 2w-1,2w, 3w-1 ,. ..}. Nieistnienie w tych punktach oznacza „okładzinę” cegieł w taki sposób:

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

Istnienie NIE w tych punktach oznacza niestabilną „szczelinę” w ścianie:

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

Dlatego ograniczamy problem do ustawiania równoważności, gdzie zestawy w pytaniach są wskaźnikami dopasowania wyrażenia regularnego.

# 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, metoda regexp (304 znaki):

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

Wejście

wektor liczb całkowitych, przykład: p ([1 1 2 2 3])

Wydajność

schemat przykładu ściany:

[____]

[__][]

[][__]