Eine Ziegelmauer ist ein Rechteck aus horizontalen 1-mal-n-Ziegeln, die in Reihen gestapelt sind. Hier ist eine Wand mit einer Höhe von 4 und einer Breite von 8, auf der rechten Seite sind die Ziegelgrößen dargestellt.

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

Diese Wand ist instabil, weil sie einen Defekt aufweist , eine Stelle, an der zwei vertikale Risse zwischen den Steinen aneinandergereiht sind, wie unten gezeigt, mit Parens in den umgebenden Steinen.

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

Die Risse an den Ziegeln der Größe 1 rechts stellen jedoch keinen Fehler dar, da sie durch eine Reihe voneinander getrennt sind.

Schreiben Sie Code, der eine stabile Wand findet und anzeigt, die aus Ziegeln bestimmter Größen besteht. Wenigste Bytes gewinnt.

Eingang

Eine nicht leere Liste mit Ziegelgrößen (positive Zahlen) und einer Höhe von mindestens 2. Diese Liste kann auf Wunsch sortiert werden. Sie können alternativ eine Anzahl von Steinen jeder Größe aufnehmen.

Ausgabe

Ein Bild einer stabilen rechteckigen Wand mit der erforderlichen Höhe, in der alle angegebenen Steine ​​verwendet werden. Drucken Sie es aus oder geben Sie es als Zeichenfolge mit Zeilenumbrüchen zurück.

Zeichnen Sie einen Baustein der Größe n als 2n Zeichen, die von eckigen Klammern umgeben sind.

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

Die Eingabe hat garantiert mindestens eine Lösung. Wenn es mehrere gibt, sollten Sie immer noch nur eine Wand zeichnen.

Es gibt keine zeitliche Beschränkung. Wende so viel rohe Gewalt an, wie du willst. Ihr Algorithmus sollte theoretisch mit Eingaben jeder Größe arbeiten.

Testfälle:

Es gibt mehrere Lösungen, sodass Ihre Ausgaben möglicherweise unterschiedlich sind.

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

Eine perfekte Aufgabe für eine Sprache von 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

Brachiale Kraft, aber in den Testfällen recht schnell (<1s). Verwendungszweck:

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

Teste mich .

CJam, 94 92 82 Bytes

Dies ist die 92-Byte-Version. Es folgt die 82-Byte-Version.

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

Dadurch werden die Bausteine ​​in alle möglichen Arten unterteilt und es wird nur der gültige verwendet. Momentan ziemlich brachial, aber der letzte Testfall wird in ungefähr 10 Sekunden auf dem Java-Interpreter auf meinem Computer ausgeführt.

Erklärung :

Der Code ist in 5 Teile aufgeteilt:

1) LWie können wir ein Array mit einer gegebenen Länge in HTeile unterteilen?

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

Danach haben wir alle Möglichkeiten, unser Input-Array in H-Brick-Layer aufzuteilen.

2) Holen Sie sich alle Permutationen des Eingabearrays und holen Sie sich dann alle Partitionen für alle Permutationen

\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

Danach haben wir alle möglichen Layouts der Eingabebausteine ​​in einer HEbenenmauer.

3) Filtern Sie nur die Layouts heraus, deren Ziegelsteinlängen gleich sind

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

Nach dem Ende dieses Filters wären alle verbleibenden Layouts perfekte Rechtecke.

4) Nehmen Sie das erste Ziegellayout heraus, das den Stabilitätskriterien entspricht

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

Nach diesem Schritt müssen wir nur noch das Layout ausdrucken

5) Drucken Sie das Layout

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

Probieren Sie es hier online aus

82 Bytes

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

Dies ähnelt fast der 92-Byte-Version, nur dass sie etwas zufällig ist. Wenn Sie die Erklärung für die 92-Byte-Version gelesen haben, sind die Teile 3, 4 und 5 in der 82-Byte-Version genau gleich. Anstatt alle Permutationen aus Teil 1 und 2 zu durchlaufen, generiert diese Version einfach zufällig eine der folgenden Permutation zu einem Zeitpunkt, testet es mit Teil 3 und 4 und startet dann den Prozess neu, wenn die Tests von Teil 3 und 4 fehlschlagen.

Dies gibt die Ergebnisse für die ersten 3 Testfälle sehr schnell aus. Der Testfall height = 5 muss noch auf meinem Computer ausgegeben werden.

Erklärung des Unterschieds

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

Die Idee zu dieser Version stammt von randomra (Get it?)

Versuchen Sie dieses online

Python 2, 680 670 660 Bytes

Ich weiß nicht, warum ich darauf bestehe, diese superlangen "Golfer" zu haben ... aber auf jeden Fall, los geht's.

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

Dies erfordert die Ausgabe in aufsteigender Reihenfolge sortiert und wird über aufgerufen b(brick_sizes, height).

Testfälle:

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

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

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

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

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

Das funktioniert folgendermaßen:

1. Ordnen Sie die Steine ​​(am längsten-> am kürzesten) den Schichten zu und versuchen Sie, jede Schicht zu füllen, bevor Sie zur nächsten übergehen.
2. Wenn benachbarte Ebenen instabil sind, versuchen Sie, Ebenen auszutauschen und Steine ​​zu verschieben, bis Sie etwas finden, das funktioniert.
3. Wenn nichts funktioniert, platzieren Sie den längsten Ziegelstein an der Spitze der Größenliste und führen Sie den Vorgang erneut aus.

Haskell, 262 Bytes

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

Anwendungsbeispiel:

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

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

So funktioniert es: Die Hauptfunktion #nimmt eine Liste l(Ziegelsteinliste) und eine Nummer h(Höhe) und teilt alle Permutationen von an allen möglichen Stellen lin hUnterlisten auf (über Funktion %, zB 2%[1,2,3,4]-> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]). Es behält diejenigen bei, bei denen zwei aufeinanderfolgende Elemente die gleiche Summe haben (dh die gleiche Länge in Ziegelsteinen) und die Listen der Zwischensummen keine gemeinsamen Elemente haben (dh Risse reihen sich nicht aneinander, funktionieren nicht v). Nehmen Sie die erste Liste, die passt, und bauen Sie eine Reihe von Steinen.

Python 2, 528 , 417 , 393 , 381

Sehr lange Bruteforce-Lösung. Es funktioniert, aber das war's auch schon. Das Universum könnte enden, bevor das Ergebnis für den letzten Testfall vorliegt.

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 ist die Hauptfunktion:

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

JavaScript (ES6) 222 232 265 279 319

Noch zu golfen. Dieser findet alle Lösungen, gibt nur die zuletzt gefundenen aus und es ist ziemlich schnell.

Führen Sie zum Testen das Snippet in Firefox aus

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>

Ungolfed Und erklärte

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, Gittermethode (290 Zeichen)

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

Die Methode hier ist, dass Sie das Raster transponieren und nach einer [[oder einer ]]beliebigen Stelle in den Spalten suchen . Sie testen auch, ob alle Steine ​​auf der linken und rechten Seite der Wand ausgerichtet sind: Das Süße hier ist, zu testen, ob alle Elemente einer Zeichenfolge gleich sind:'[[[[[['.strip('[')==''

Mini-Version von oben:

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

Dies könnte wahrscheinlich einfacher in einer Matrix-Manipulationssprache erfolgen.

... oder Missbrauch von Regexen, wodurch wir die Bedingung "Blöcke an den Enden ausrichten" mit der Bedingung "keine Risse" kombinieren können:

Angenommen, die Breite der Wand war w = 6. Die Positionen der Teilzeichenfolge "[..... [" und "] .....]" müssen genau der Menge {0, w-1, w, 2w-1,2w, 3w-1,. ..}. Nichtexistenz an diesen Punkten bedeutet, dass der Zeilenumbruch wie folgt lautet:

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

Das Vorhandensein von NOT an diesen Stellen bedeutet, dass es einen unsteten "Riss" in der Wand gibt:

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

Daher reduzieren wir das Problem auf die Mengenäquivalenz, bei der die fraglichen Mengen die Indizes eines regulären Ausdrucks sind.

# 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, Regexp-Methode (304 Zeichen):

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

Eingang

ein Vektor von ganzen Zahlen, Beispiel: p ([1 1 2 2 3])

Ausgabe

Das Schema des Wandbeispiels:

[____]

[__][]

[][__]