39
\$\begingroup\$

A brick wall is a rectangle made of horizontal 1-by-n bricks stacked into rows. Here's a wall of height 4 and width 8, with brick sizes shown on the right.

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

This wall is unsteady because it has a fault, a place where two vertical cracks between bricks line up, shown below with parens in the surrounding bricks.

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

But, the cracks bordering the size-1 bricks on the right don't form a fault because they are separated by a row.

Write code that finds and displays a steady wall constructed out of bricks of specified sizes. Fewest bytes wins.

Input

A non-empty list of brick sizes (positive numbers) and a height that's at least 2. This list may be sorted if you wish. You may alternatively take in a count of bricks of each size.

Output

A picture of a steady rectangular wall of the required height that uses all the bricks given. Print it or return it as a string with newlines.

Draw a brick of size n as 2n characters, underscores surrounded by brackets.

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

The input is guaranteed to have at least one solution. If there's multiple, you should still only draw one wall.

There's no time restriction; use as much brute force as you want. Your algorithm should in theory work on inputs of any size.

Test cases:

There are multiple solutions, so your outputs might be different.

>> [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
[][__][__]
[__][__][]
[][__][__]
[__][__][]
[][__][__]
\$\endgroup\$
  • \$\begingroup\$ why did you decide to make bricks 2n characters wide instead of n>1 characters wide? \$\endgroup\$ – Sparr May 2 '15 at 16:52
  • 2
    \$\begingroup\$ @Sparr 1 by 2 character blocks look roughly square. I had tried requiring n>1 and didn't like how it restricted test cases. Also, apparently there's precedent. \$\endgroup\$ – xnor May 2 '15 at 17:13
  • \$\begingroup\$ I don't mean 2n with n>1. I mean n with n>1. \$\endgroup\$ – Sparr May 3 '15 at 14:06
20
\$\begingroup\$

Perl, 166 170 194

A perfect task for a language created by 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, but quite fast on the test cases (<1s). Usage:

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

Test me.

\$\endgroup\$
  • 9
    \$\begingroup\$ Ha, I wonder if Larry Wall ever thought people would be using the language like that... :) \$\endgroup\$ – crazyhatfish May 2 '15 at 17:23
12
\$\begingroup\$

CJam, 94 92 82 bytes

This is the 92 bytes version. 82 byte version follows.

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

This partitions the bricks into every possible way and take only the one which is valid. Pretty brute force for now but still runs the last test case in about 10 seconds on the Java Interpreter on my machine.

Explanation:

The code is split into 5 parts:

1) Given an array of length L, how all can we partition it into H parts.

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

After this, we have all possible ways of splitting up our input array into H brick layers.

2) Get all permutations of the input array and then further get all partitions for all 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

After this, we have all possible layouts of the input bricks into an H layers brick wall.

3) Filter out only those layouts whose brick lengths are 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.

After the end of this filter, all remaining layouts would be perfect rectangles.

4) Take out the first brick layout which matches the stability criteria

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

After this step, we simply have to print the layout

5) Print the 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

Try it online here


82 bytes

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

This is almost similar to the 92 byte version, except that it has a touch of randomness. If you have read the explanation for the 92 byte version, then in the 82 byte version, parts 3, 4 and 5 are exactly same, while instead of iterating over all permutations from part 1 and 2, this version simply randomly generates one of the permutation at a time, tests it using part 3 and 4, and then restarts the process if the tests of part 3 and 4 fail.

This prints the results very quickly for the first 3 test cases. The height = 5 test case is yet to give an output on my computer.

Explanation of the difference

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

The idea for this version was given by randomra (Get it ?)

Try this one online

\$\endgroup\$
9
\$\begingroup\$

Python 2, 680 670 660 bytes

I don't know why I insist on having these super long "golfs"... but anyway, here you go.

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

This requires the output in sorted ascending order, and is called via b(brick_sizes, height).

Test cases:

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

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

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

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

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

The way this works is:

  1. Assign the bricks (longest->shortest) to layers, trying to fill each layer before moving to the next.
  2. Whenever adjacent layers are unstable, try swapping layers and shifting bricks until you find something that works.
  3. If nothing works, move the longest brick to the front of the sizes list and recurse.
\$\endgroup\$
  • 1
    \$\begingroup\$ You can probably drop the continue from near the end. Also return(N,N) won't need the parenthesis. \$\endgroup\$ – PurkkaKoodari May 2 '15 at 11:42
  • \$\begingroup\$ good call - that continue was a relic from an earlier version. \$\endgroup\$ – sirpercival May 2 '15 at 12:00
  • 1
    \$\begingroup\$ Can't get it to run, you have an extraneous bracket in W and T gets passed an extra argument. \$\endgroup\$ – crazyhatfish May 2 '15 at 14:25
  • \$\begingroup\$ whoops, thank you! fixed. \$\endgroup\$ – sirpercival May 2 '15 at 15:12
5
\$\begingroup\$

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

Example usage:

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

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

How it works: the main function # takes a list l (list of bricks) and a number h (height) and splits all permutations of l into h sublists at all possible positions (via function %, e.g. 2%[1,2,3,4] -> [ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]) . It keeps those where two consecutive elements have the same sum (i.e. same length in bricks) and the lists of subtotals don't have common elements (i.e. cracks don't line up, function v). Take the first list that fits and build a string of bricks.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 528, 417, 393, 381

Very long, bruteforce solution. It works but that's about it, the universe may end before getting the result for the last test case.

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 is the main function:

>> a([1, 1, 2, 2], 2)
'[][  ]\n[  ][]'
\$\endgroup\$
  • \$\begingroup\$ You can save 4 bytes by changing the import to from itertools import* and removing itertools. from the permutations call. Also, the ifs in the end can be changed to if all(x==w[0] for x in w)and~-f(o):return... to save 13 bytes. \$\endgroup\$ – PurkkaKoodari May 2 '15 at 11:32
  • \$\begingroup\$ Also, doesn't f always return on the first iteration? That looks weird. It's either a bug or a huge golf opportunity. \$\endgroup\$ – PurkkaKoodari May 2 '15 at 11:37
  • \$\begingroup\$ You have a ton of extraneous spaces that can be removed - before or after a quote/paren/bracket, surrounding an operator, etc. You also are assigning t=0 twice in r(); you can make that function into map(sum,[x[:i] for i in range(len(x))]) as a one-liner (suitable for lambda-ing if you want). Using isdisjoint and sets in f() would reduce it significantly (also f() currently returns after only one test, whether it's found an error or not). Personally I'd rewrite f() as return not all(map(isdisjoint,map(set,map(r,w[:-1])),map(set,map(r,w[1:])))) or something similar. \$\endgroup\$ – sirpercival May 2 '15 at 11:47
  • \$\begingroup\$ @Pietu1998 Oh yeah, missed a space. Thanks for the tips guys, I amazed you can spot these things. \$\endgroup\$ – crazyhatfish May 2 '15 at 14:15
  • \$\begingroup\$ laughing too bad i hate that kind of codes where "the universe may end before getting the result " but this is shortest bytes cotest what else to do xD \$\endgroup\$ – Abr001am May 2 '15 at 23:46
3
\$\begingroup\$

JavaScript (ES6) 222 232 265 279 319

Still to be golfed. This one find all the solutions, output just the last found, and it's quite fast.

Run snippet in Firefox to test

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 And explained

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
}
\$\endgroup\$
2
\$\begingroup\$

Python 2, grid method (290 chars)

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

The method here is you transpose the grid and look for a [[ or ]] anywhere in the columns. You also test that all the bricks on the left and right sides of the wall line up: the cute thing here is to test that all elements of a string are the same: '[[[[[['.strip('[')==''


mini version of above:

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

This could probably be done more easily in a matrix-manipulation language.

...or abuse of regexes, which lets us combine the "blocks align on ends" condition with the "no cracks" condition:

Say the width of the wall was w=6. The locations of the substring "[.....[", and "].....]" must be exactly the set {0,w-1,w,2w-1,2w,3w-1,...}. Not-existence at those points means the bricks 'linewrap' like so:

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

Existence NOT at those points means there is an unsteady 'crack' in the wall:

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

Therefore we reduce the problem to set equivalence, where the sets in questions are the indices of a regular expression match.

# 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 method (304 chars):

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)))
\$\endgroup\$
  • \$\begingroup\$ Interesting idea working with the wall picture directly to check for faults. You need a line to take the input, like x,h=input(). \$\endgroup\$ – xnor May 17 '15 at 3:17
0
\$\begingroup\$

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

Input

a vector of integers , example: p([1 1 2 2 3])

Output

the scheme of the wall example:

[____]

[__][]

[][__]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.