11
\$\begingroup\$

I have a bunch of boards I need to stack in as small a space as possible. Unfortunately, the boards fall over if I stack them more than 10 high. I need a program to tell me how to stack the boards to take as little horizontal space as possible, without stacking boards more than ten high, or having boards hanging out over empty space.

Your Task:

Write a program or function, that when given an array containing the lengths of boards, outputs as ASCII art the way to stack the boards to conserve as much horizontal space as possible, without stacking the boards more than 10 high or having any part of any board hanging out over empty space. Your ASCII art should show the configuration of the boards, with each one shown using a different character. There will be a maximum of 20 boards. For example, if the input was [2,2,4,2,2,4,4,4], a possible output is:

dhh
dgg
dff
dee
abc
abc
abc
abc

which is a stable configuration (although this would fall over in ~0.1 seconds in real life).

Input:

An array containing up to 20 integers, showing the lengths of the boards.

Output:

ASCII art showing the configurations of the boards, as outlined above.

Test Cases:

Note that there may be other solutions for the test cases, and the characters shown for each board may be different.

[12,2,2,2,3,4,4,8,8]        -> ffgghhiii
                               ddddeeeeeeee
                               bbbbbbbbcccc
                               aaaaaaaaaaaa

[4,4,4,4,4,4,4,4,4,4,4,4]   -> llll
                               aaaa
                               cfghk
                               cfghk
                               cfghk
                               cfghk
                               debij
                               debij
                               debij
                               debij

[4,4,4,4,4,4,3,3,3,2,2,2,1] -> jjml
                               iiil
                               hhhk
                               gggk
                               ffff
                               eeee
                               dddd
                               cccc
                               bbbb
                               aaaa

Scoring:

This is , lowest score in bytes wins

\$\endgroup\$
3
\$\begingroup\$

Python 3, 513 512 511 509 499 497 485 465 459 458 444 bytes

Incredibly bad runtime, will finish at some point

e,j,c=enumerate,len,range
def f(n,p=[],o=97):
    r,l,m=lambda x:min(b,f(n[:i]+n[i+1:],x,o+1),key=j),chr(o),j(p)
    b=[p,l*(sum(n)*2+m)][n>[]]
    for i,a in e(n):
        for h,d in e(p):
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
            if(j(d)<10)*all(j(x)==j(d)for x in p[h:h+a])*(a<=m-h):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
        if a<11:b=r(p+[l*a])
        b=r(p+[l]*a)
    return["\n".join("".join(9-u<j(x)and x[9-u]or" "for x in b)for u in c(10)),b][o>97]

Try it online!

Edit: -2 -8 bytes thanks to @Mr. Xcoder Edit: -8 bytes thanks to @notjagan

Explanation

e,j,c=enumerate,len,range      
         # These built-ins are used a lot
def f(n,p=[],o=97):
         # n is the remaining blocks
         # p is the current stack
         # o is the ASCI code for the next letter to use
    r,l,m=lambda x:min(b,f(n[:i]+n[i+1:],x,o+1),key=j),chr(o),j(p)
         # r is the recursive call, that also selects the smallest stack found
         # l is the letter to use next
         # m is the length of the current stack
    b=[p,l*(sum(n)*2+m)][n>[]]
         # Sets the current best, if there are no remaining blocks, select the found stack, else we set it to be worse than the possible worst case
    for i,a in e(n):
         # Loop through all the remaining blocks
        for h,d in e(p):
         # Loop through all the columns in the current stack
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
         # If we can place the current block vertically in the current column, try it
            if(j(d)<10)*all(j(x)==j(d)for x in p[h:h+a])*(a<=m-h):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
         # If we can place the current block horizontally starting in the current column, try it
        if a<11:b=r(p+[l*a])
         # If the current block is lower than 10, try place it vertically to the right of the current stack
        b=r(p+[l]*a)
         # Try to place the current horizontally to the right of the current stack
    return["\n".join("".join(9-u<j(x)and x[9-u]or" "for x in b)for u in c(10)),b][o>97]
         # Return the best choice if we aren't in the first call to the function, that is the next letter is a. Else return the found best option formatted as a string

Python 3, 587 bytes

Actually runnable on TIO for some of the test cases

e,j,c=enumerate,len,range
def f(n,p=[],o=97,b=[]):
    if(not n):return p
    if not b:b="a"*sum(n)*2
    r,q,s,l,m=lambda x:q(f(n[:i]+n[i+1:],x,o+1,b)),lambda x:[b,x][j(b)>j(x)],b,chr(o),j(p)
    if j(b)<=m:return b
    for i,a in e(n):
        for h,d in e(p):
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
            if j(d)<10 and a<=m-h and all(map(lambda x:j(x)==j(d),p[h:h+a])):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
        if s==b:
            if a<11and m+1<j(b):b=r(p[:]+[l*a])
            if m+a<j(b):b=r(p[:]+[l for r in c(a)])
    return["\n".join("".join(map(lambda x:" "if u>=j(x)else x[u],b))for u in c(9,-1,-1)),b][o>97]

Try it online!

Both solutions could probably be golfed quite a bit.

\$\endgroup\$
  • \$\begingroup\$ 483 bytes \$\endgroup\$ – Mr. Xcoder Aug 5 '17 at 9:17
  • \$\begingroup\$ 583 bytes for the second one \$\endgroup\$ – Mr. Xcoder Aug 5 '17 at 9:21
  • \$\begingroup\$ Mr. Xcoder, the second one can be reduced by near 50 bytes, I just havn't applied the changes for the first one to the second one \$\endgroup\$ – Halvard Hummel Aug 5 '17 at 9:26
  • \$\begingroup\$ I know the second one can be golfed a lot, but the changes to the first one should be helpful. \$\endgroup\$ – Mr. Xcoder Aug 5 '17 at 9:27
  • 1
    \$\begingroup\$ You earned my upvote, for some great code with a wonderful explanation, that shows lots of effort and thought. Congrats and welcome to PPCG! \$\endgroup\$ – Mr. Xcoder Aug 5 '17 at 9:32

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.