Planches empilables

11

J'ai un tas de planches que je dois empiler dans un espace aussi petit que possible. Malheureusement, les planches tombent si je les empile de plus de 10 de haut. J'ai besoin d'un programme pour me dire comment empiler les planches pour prendre le moins d'espace horizontal possible, sans empiler les planches de plus de dix de haut, ou avoir des planches suspendues sur un espace vide.

Ta tâche:

Écrivez un programme ou une fonction qui, lorsqu'il est fourni un tableau contenant les longueurs de cartes, génère en tant qu'art ASCII le moyen d'empiler les cartes pour conserver autant d'espace horizontal que possible, sans empiler les cartes de plus de 10 de haut ou avoir une partie quelconque Conseil traîner sur un espace vide. Votre art ASCII doit montrer la configuration des cartes, chacune étant représentée avec un caractère différent. Il y aura un maximum de 20 planches. Par exemple, si l'entrée était [2,2,4,2,2,4,4,4], une sortie possible est:

dhh
dgg
dff
dee
abc
abc
abc
abc

qui est une configuration stable (bien que cela tomberait en ~ 0,1 seconde dans la vraie vie).

Contribution:

Un tableau contenant jusqu'à 20 entiers, montrant les longueurs des cartes.

Production:

Art ASCII montrant les configurations des cartes, comme indiqué ci-dessus.

Cas de test:

Notez qu'il peut y avoir d'autres solutions pour les cas de test et que les caractères affichés pour chaque carte peuvent être différents.

[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

Notation:

C'est le , le score le plus bas en octets gagne

Gryphon
la source

Réponses:

3

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

Temps d'exécution incroyablement mauvais, se terminera à un moment donné

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]

Essayez-le en ligne!

Edit: - 2 à 8 octets grâce à @Mr. Xcoder Edit: -8 octets grâce à @notjagan

Explication

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 octets

Exécutable sur TIO pour certains des cas de test

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]

Essayez-le en ligne!

Les deux solutions pourraient probablement être assez utilisées.

Halvard Hummel
la source
483 octets
M. Xcoder
M. Xcoder, le second peut être réduit de près de 50 octets, je n'ai tout simplement pas appliqué les changements du premier au second
Halvard Hummel
Je sais que le second peut être joué beaucoup, mais les changements au premier devraient être utiles.
M. Xcoder
1
Vous avez gagné mon vote positif, pour un excellent code avec une merveilleuse explication, qui montre beaucoup d'efforts et de réflexion. Félicitations et bienvenue à PPCG!
M. Xcoder