Un mur de briques est un rectangle constitué de briques horizontales 1-sur-n empilées en rangées. Voici un mur de hauteur 4 et de largeur 8, avec les tailles de briques indiquées à droite.

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

Ce mur est instable car il y a une faille , un endroit où deux fissures verticales entre des briques sont alignées, illustrées ci-dessous avec des parens dans les briques environnantes.

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

Cependant, les fissures bordant les briques de taille 1 à droite ne constituent pas une faute, car elles sont séparées par une rangée.

Écrivez un code qui trouve et affiche un mur stable construit à partir de briques de tailles spécifiées. Le moins d'octets gagne.

Contribution

Une liste non vide de tailles de briques (nombres positifs) et une hauteur d'au moins 2. Cette liste peut être triée si vous le souhaitez. Vous pouvez également prendre en compte un nombre de briques de chaque taille.

Sortie

Une image d'un mur rectangulaire stable de la hauteur requise qui utilise toutes les briques données. Imprimez-le ou renvoyez-le sous forme de chaîne avec des nouvelles lignes.

Tracez une brique de taille n sous la forme de 2n caractères, soulignés par des crochets.

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

L'entrée est garantie d'avoir au moins une solution. S'il y en a plusieurs, vous ne devez toujours dessiner qu'un seul mur.

Il n'y a pas de limite de temps; utilisez autant de force brute que vous le souhaitez. Votre algorithme devrait en théorie fonctionner sur des entrées de toute taille.

Cas de test:

Il existe plusieurs solutions, vos sorties peuvent donc être différentes.

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

Une tâche parfaite pour une langue créée par 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

Force brute, mais assez rapide sur les cas de test (<1). Usage:

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

Testez - moi .

CJam, 94 92 82 octets

Ceci est la version de 92 octets. La version de 82 octets suit.

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

Cela sépare les briques de toutes les manières possibles et n'utilise que celui qui est valide. Force assez brute pour le moment mais exécute toujours le dernier scénario de test en environ 10 secondes sur l' interpréteur Java sur ma machine.

Explication :

Le code est divisé en 5 parties:

1) Étant donné un tableau de longueur L, comment pouvons-nous tous le partitionner en plusieurs Hparties?

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

Après cela, nous avons tous les moyens possibles de diviser notre tableau d’entrée en couches H de briques.

2) Obtenez toutes les permutations du tableau d'entrée, puis toutes les partitions pour toutes les permutations

\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

Après cela, nous avons toutes les dispositions possibles des briques d’entrée dans un Hmur de briques en couches.

3) Filtrez uniquement les dispositions dont les longueurs de briques sont identiques

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

Après la fin de ce filtre, toutes les dispositions restantes seraient des rectangles parfaits.

4) Sortez la première disposition de briques qui correspond aux critères de stabilité

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

Après cette étape, nous devons simplement imprimer la mise en page

5) Imprimer la mise en page

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

Essayez-le en ligne ici

82 octets

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

Ceci est presque similaire à la version à 92 octets, sauf qu’elle a une touche d’aléatoire. Si vous avez lu l'explication de la version à 92 octets, dans la version à 82 octets, les parties 3, 4 et 5 sont exactement identiques, alors qu'au lieu d'itérer toutes les permutations des parties 1 et 2, cette version génère simplement de manière aléatoire l'une des permutation à la fois, la teste en utilisant les parties 3 et 4, puis relance le processus si les tests des parties 3 et 4 échouent.

Ceci imprime les résultats très rapidement pour les 3 premiers cas de test. La hauteur = 5 cas de test est encore à donner une sortie sur mon ordinateur.

Explication de la différence

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

L'idée de cette version a été donnée par randomra (Get it?)

Essayez celui-ci en ligne

Python 2, 680 670 660 octets

Je ne sais pas pourquoi j'insiste pour avoir ces super longs "golfs" ... mais bon, voilà.

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

Cela nécessite la sortie dans un ordre croissant trié et est appelé via b(brick_sizes, height).

Cas de test:

>>> 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 façon dont cela fonctionne est:

1. Attribuez les briques (les plus longues -> les plus courtes) à des calques, en essayant de remplir chaque calque avant de passer au suivant.
2. Lorsque les calques adjacents sont instables, essayez d’échanger les calques et de déplacer les briques jusqu’à ce que vous trouviez quelque chose qui fonctionne.
3. Si rien ne fonctionne, placez la brique la plus longue à l'avant de la liste des tailles et recurse.

Haskell, 262 octets

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

Exemple d'utilisation:

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

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

Comment ça marche: la fonction principale #prend une liste l(liste de briques) et un nombre h(hauteur) et divise toutes les permutations de len hsous-listes à toutes les positions possibles (via la fonction %, par exemple 2%[1,2,3,4]-> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]). Il conserve ceux où deux éléments consécutifs ont la même somme (c'est-à-dire la même longueur dans les briques) et les listes de sous-totaux n'ont pas d'éléments communs (les fissures ne s'alignent pas, ne fonctionnent pas v). Prenez la première liste qui convient et construisez une chaîne de briques.

Python 2, 528 , 417 , 393 , 381

Très longue solution bruteforce. Cela fonctionne mais c’est à peu près tout, l’univers peut se terminer avant d’obtenir le résultat du dernier cas de test.

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 est la fonction principale:

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

JavaScript (ES6) 222 232 265 279 319

Reste à jouer au golf Celui-ci trouve toutes les solutions, ne sort que la dernière trouvée, et c'est assez rapide.

Exécuter un extrait de code dans Firefox pour tester

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 Et expliqué

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éthode grid (290 caractères)

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

La méthode ici est que vous transposez la grille et cherchez un [[ ou ]]n'importe où dans les colonnes. Vous vérifiez également que toutes les briques des côtés gauche et droit du mur sont alignées: il est intéressant de vérifier que tous les éléments d'une chaîne sont identiques:'[[[[[['.strip('[')==''

mini version de ci-dessus:

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

Cela pourrait probablement être fait plus facilement dans un langage de manipulation matricielle.

... ou d'abus de expressions rationnelles, ce qui nous permet de combiner la condition "blocs alignés sur les extrémités" avec la condition "aucune fissure":

Disons que la largeur du mur était w = 6. Les emplacements de la sous-chaîne "[..... [" et "] .....]" doivent correspondre exactement à l'ensemble {0, w-1, w, 2w-1,2w, 3w-1 ,. ..}. La non-existence à ces points signifie que le banderolage des briques ressemble à ceci:

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

L'existence PAS à ces endroits signifie qu'il y a une "fissure" instable dans le mur:

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

Par conséquent, nous réduisons le problème pour définir l’équivalence, où les ensembles en question sont les indices d’une correspondance d’expression régulière.

# 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éthode regexp (304 caractères):

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

Contribution

un vecteur d'entiers, exemple: p ([1 1 2 2 3])

Sortie

le schéma du mur exemple:

[____]

[__][]

[][__]