Una pared de ladrillos es un rectángulo hecho de ladrillos horizontales de 1 por n apilados en filas. Aquí hay un muro de altura 4 y ancho 8, con tamaños de ladrillo a la derecha.

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

Este muro es inestable porque tiene una falla , un lugar donde se alinean dos grietas verticales entre los ladrillos, que se muestran a continuación con parens en los ladrillos circundantes.

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

Pero, las grietas que bordean los ladrillos de tamaño 1 a la derecha no forman una falla porque están separadas por una fila.

Escriba un código que encuentre y muestre un muro estable construido con ladrillos de tamaños específicos. Pocos bytes ganan.

Entrada

Una lista no vacía de tamaños de ladrillo (números positivos) y una altura de al menos 2. Esta lista se puede ordenar si lo desea. Alternativamente, puede tomar un recuento de ladrillos de cada tamaño.

Salida

Una imagen de una pared rectangular estable de la altura requerida que utiliza todos los ladrillos dados. Imprimirlo o devolverlo como una cadena con nuevas líneas.

Dibuje un ladrillo de tamaño n como 2n caracteres, guiones bajos entre paréntesis.

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

Se garantiza que la entrada tenga al menos una solución. Si hay varios, solo debes dibujar una pared.

No hay restricción de tiempo; usa tanta fuerza bruta como quieras. En teoría, su algoritmo debería funcionar en entradas de cualquier tamaño.

Casos de prueba:

Existen múltiples soluciones, por lo que sus resultados pueden ser diferentes.

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

Una tarea perfecta para un lenguaje creado por 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

Fuerza bruta, pero bastante rápida en los casos de prueba (<1s). Uso:

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

Ponme a prueba .

CJam, 94 92 82 bytes

Esta es la versión de 92 bytes. Sigue la versión de 82 bytes.

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

Esto divide los ladrillos en todas las formas posibles y toma solo el que es válido. Fuerza bruta bastante por ahora, pero aún ejecuta el último caso de prueba en unos 10 segundos en el intérprete de Java en mi máquina.

Explicacion :

El código se divide en 5 partes:

1) Dada una matriz de longitud L, ¿cómo podemos dividirla en Hpartes?

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

Después de esto, tenemos todas las formas posibles de dividir nuestra matriz de entrada en capas de ladrillo H.

2) Obtenga todas las permutaciones de la matriz de entrada y luego obtenga todas las particiones para todas las permutaciones

\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

Después de esto, tenemos todos los diseños posibles de los ladrillos de entrada en una Hpared de ladrillo de capas.

3) Filtre solo aquellos diseños cuyas longitudes de ladrillo sean iguales

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

Después del final de este filtro, todos los diseños restantes serían rectángulos perfectos.

4) Saque el primer diseño de ladrillo que coincida con los criterios de estabilidad

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

Después de este paso, simplemente tenemos que imprimir el diseño.

5) Imprimir el diseño

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

Pruébalo en línea aquí

82 bytes

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

Esto es casi similar a la versión de 92 bytes, excepto que tiene un toque de aleatoriedad. Si ha leído la explicación de la versión de 92 bytes, en la versión de 82 bytes, las partes 3, 4 y 5 son exactamente iguales, mientras que en lugar de repetir todas las permutaciones de las partes 1 y 2, esta versión simplemente genera aleatoriamente una de las permutación a la vez, lo prueba usando las partes 3 y 4, y luego reinicia el proceso si las pruebas de las partes 3 y 4 fallan.

Esto imprime los resultados muy rápidamente para los primeros 3 casos de prueba. El caso de prueba height = 5 todavía tiene que dar una salida en mi computadora.

Explicación de la diferencia.

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

La idea para esta versión fue dada por randomra (¿Entiendes?)

Prueba este en línea

Python 2, 680 670 660 bytes

No sé por qué insisto en tener estos "golfs" súper largos ... pero de todos modos, aquí tienes.

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

Esto requiere la salida en orden ascendente ordenado, y se llama vía b(brick_sizes, height).

Casos de prueba:

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

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

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

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

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

La forma en que esto funciona es:

1. Asigne los ladrillos (más largo-> más corto) a las capas, tratando de llenar cada capa antes de pasar a la siguiente.
2. Siempre que las capas adyacentes sean inestables, intente intercambiar capas y mover ladrillos hasta que encuentre algo que funcione.
3. Si nada funciona, mueva el ladrillo más largo al principio de la lista de tamaños y vuelva a aparecer.

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

Ejemplo de uso:

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

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

Cómo funciona: la función principal #toma una lista l(lista de ladrillos) y un número h(altura) y divide todas las permutaciones len hsublistas en todas las posiciones posibles (a través de la función %, por ejemplo, 2%[1,2,3,4]-> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]). Mantiene aquellos en los que dos elementos consecutivos tienen la misma suma (es decir, la misma longitud en ladrillos) y las listas de subtotales no tienen elementos comunes (es decir, las grietas no se alinean, funcionan v). Tome la primera lista que se ajuste y construya una cadena de ladrillos.

Python 2, 528 , 417 , 393 , 381

Muy larga, solución de fuerza bruta. Funciona pero eso es todo, el universo puede terminar antes de obtener el resultado para el último caso de prueba.

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 es la función principal:

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

JavaScript (ES6) 222 232 265 279 319

Aún por jugar al golf. Este encuentra todas las soluciones, genera solo el último encontrado y es bastante rápido.

Ejecute el fragmento en Firefox para probar

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>

Desengañado y explicado

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, método de cuadrícula (290 caracteres)

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

El método aquí es transponer la cuadrícula y buscar una [[o ]]cualquier parte de las columnas. También prueba que todos los ladrillos en los lados izquierdo y derecho de la pared se alinean: lo lindo aquí es probar que todos los elementos de una cadena son iguales:'[[[[[['.strip('[')==''

versión mini de arriba:

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

Esto probablemente podría hacerse más fácilmente en un lenguaje de manipulación matricial.

... o abuso de expresiones regulares, que nos permite combinar la condición de "bloques alineados en los extremos" con la condición de "sin grietas":

Digamos que el ancho de la pared era w = 6. Las ubicaciones de la subcadena "[..... [" y "] .....]" deben ser exactamente el conjunto {0, w-1, w, 2w-1,2w, 3w-1 ,. ..}. La inexistencia en esos puntos significa que los ladrillos 'linewrap' así:

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

La existencia NO en esos puntos significa que hay una 'grieta' inestable en la pared:

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

Por lo tanto, reducimos el problema para establecer la equivalencia, donde los conjuntos en las preguntas son los índices de una coincidencia de expresión regular.

# 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, método regexp (304 caracteres):

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

Entrada

un vector de enteros, ejemplo: p ([1 1 2 2 3])

Salida

El esquema del ejemplo del muro:

[____]

[__][]

[][__]