Empilage de caisses lourdes

27

Vous avez un tas de boîtes lourdes et vous voulez les empiler dans le moins de piles possible. Le problème est que vous ne pouvez pas empiler plus de boîtes sur une boîte qu'il ne peut en supporter, donc les boîtes plus lourdes doivent aller au bas d'une pile.

Le défi

Entrée : une liste des poids des boîtes, en kg entiers.

Sortie : une liste de listes décrivant les piles de boîtes. Cela doit utiliser le moins de piles possible pour l'entrée. Pour être une pile valide, le poids de chaque boîte de la pile doit être supérieur ou égal à la somme du poids de toutes les boîtes au-dessus.

Exemples de piles valides

(De bas en haut)

  • [3]
  • [1, 1]
  • [3, 2, 1]
  • [4, 2, 1, 1]
  • [27, 17, 6, 3, 1]
  • [33, 32, 1]
  • [999, 888, 99, 11, 1]

Exemples de piles non valides

(Dans l'ordre de bas en haut)

  • [1, 2]
  • [3, 3, 3]
  • [5, 5, 1]
  • [999, 888, 777]
  • [4, 3, 2]
  • [4321, 3000, 1234, 321]

Exemples de cas de test

1

IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

2

IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

3

IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

4

IN: [8, 5, 8, 8, 1, 2]
OUT: [[8, 8], [8, 5, 2, 1]]

Règles et hypothèses

  • Les règles d'E / S standard et les failles interdites s'appliquent
  • Utilisez n'importe quel format pratique pour les E / S
    • Les piles peuvent être décrites de haut en bas ou de bas en haut, tant que vous êtes cohérent.
    • L'ordre des piles (plutôt que des cases dans ces piles) n'a pas d'importance.
    • Vous pouvez également prendre les zones de saisie comme une liste pré-triée. L'ordre n'est pas particulièrement important pour l'entrée, tant que le problème général n'est pas résolu par le tri lui-même.
  • S'il y a plus d'une configuration optimale de piles, vous pouvez sortir n'importe laquelle d'entre elles
  • Vous pouvez supposer qu'il y a au moins une boîte et que toutes les boîtes pèsent au moins 1 kg
  • Vous devez supporter des poids jusqu'à 9 999 kg, au minimum.
  • Vous devez prendre en charge jusqu'à 9 999 boîtes au total, au minimum.
  • Les boîtes de même poids sont indiscernables, il n'est donc pas nécessaire d'annoter quelle boîte a été utilisée à quel endroit.

Bon golf! Bonne chance!

Beefster
la source
2
Pouvons-nous prendre les poids dans l'ordre trié? (ascendant ou descendant)
Arnauld
4
"Vous devez prendre en charge jusqu'à 9 999 boîtes au total." Comment le «support» est-il interprété ici? Cela signifie-t-il simplement que le programme devrait être en mesure d'accepter une telle taille d'entrée, ou cela signifie-t-il que le programme devrait réellement fournir la réponse dans un délai raisonnable? S'il s'agit de ce dernier, des cas de test beaucoup plus importants devraient être fournis.
Joel
1
Cas de test suggéré: [8, 8, 8, 5, 1]->[[8, 8], [8, 5, 1]]
Hiatsu
3
Ou encore mieux: [8, 5, 8, 8, 1, 2]->[[8, 8], [8, 5, 2, 1]]
Hiatsu
2
@Arnauld, car sinon cela ajouterait un code de tri sans intérêt à une réponse, je vais dire oui , vous pouvez prendre les entrées dans l'ordre trié.
Beefster

Réponses:

5

Gelée , 19 octets

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ

Essayez-le en ligne!

Évident -3 grâce à Nick Kennedy ...

De haut en bas.

Explication:

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ  Arguments: S (e.g. [1, 2, 3, 4, 5])
Œ!                   Permutations (e.g. [..., [4, 1, 5, 2, 3], ...])
    €                Map link over left argument (e.g. [..., [..., [[4, 1], [5], [2, 3]], ...], ...])
  ŒṖ                  Partitions (e.g. [..., [[4, 1], [5], [2, 3]], ...])
     Ẏ               Concatenate elements (e.g. [..., ..., [[4, 1], [5], [2, 3]], ..., ...])
               Ƈ     Filter by link (e.g. [..., [[1, 3], [2], [4], [5]], ...])
              Ɗ       Create >=3-link monadic chain (e.g. [[1], [], [0]])
           €           Map link over left argument (e.g. [[1], [], [0]])
          Ʋ             Create >=4-link monadic chain (e.g. [1])
      Ṗ                  Remove last element (e.g. [4])
       Ä                 Cumulative sum (e.g. [4])
         Ḋ               [Get original argument] Remove first element (e.g. [1])
        >                Greater than (vectorizes) (e.g. [1])
            ¬          Logical NOT (vectorizes) (e.g. [[0], [], [1]])
             Ȧ         Check if non-empty and not containing zeroes after flattening (e.g. 0)
                 Þ   Sort by link (e.g. [[[1, 2, 3], [4, 5]], ..., [[5], [4], [3], [2], [1]]])
                L     Length (e.g. 4)
                  Ḣ  Pop first element (e.g. [[1, 2, 3], [4, 5]])
Erik le Outgolfer
la source
Une chance à une version moins compacte avec explication? J'apprends une tonne de ces choses.
John Keates
1
@JohnKeates Ajouté un.
Erik the Outgolfer
5

JavaScript (Node.js),  139 122  116 octets

Attend l'entrée triée par ordre croissant.

f=(A,s=[],[n,...a]=A,r)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:f(A,c,a,c[i]=[n,...b]))?S:r?0:f(A,[...s,[]]):S=s

Essayez-le en ligne!

Commenté

f = (                        // f is a recursive function taking:
  A,                         //   A[] = input array
  s = [],                    //   s[] = list of stacks, initially empty
  [n,                        //   n   = next weight to process
      ...a] = A,             //   a[] = array of remaining weights
  r                          //   r   = recursion flag
) =>                         //
  n ?                        // if n is defined:
    s.some((b, i,            //   for each stack b[] at position i in s[],
                  [...c]) => //   using c[] as a copy of s[]:
      n < eval(b.join`+`) ?  //     if n is not heavy enough to support all values in b[]:
        0                    //       abort
      :                      //     else:
        f(                   //       do a recursive call:
          A, c, a,           //         using A[], c[] and a[]
          c[i] = [n, ...b]   //         with n prepended to c[i]
        )                    //       end of recursive call
    ) ?                      //   end of some(); if successful:
      S                      //     return S[]
    :                        //   else:
      r ?                    //     if this is a recursive call:
        0                    //       do nothing
      :                      //     else:
        f(A, [...s, []])     //       try again with an additional stack
  :                          // else:
    S = s                    //   success: save the solution in S[]
Arnauld
la source
2

Python 3.8 (pré-version) , 178 octets

f=lambda b,s=[[]]:(a for i in range(len(s))if b[0]>=sum(s[i])for a in f(b[1:],s[:i]+[[b[0]]+s[i]]+s[i+1:]+[[]]))if b else[s]
g=lambda a:(c:=sorted(f(a),key=len)[0])[:c.index([])]

Essayez-le en ligne!

Fonctionne maintenant sur toutes les entrées possibles. (Il expire sur TIO avec plus d'une dizaine de cases, mais il calcule une réponse correcte)

Hiatsu
la source
2
list(reversed(sorted(a)))peut être écrit comme sorted(a)[::-1]à des fins de golf.
Joel
On pourrait penser que je le saurais maintenant, d'autant plus que je fais beaucoup d'autres indexations. Merci.
Hiatsu
Juste une remarque secondaire, sinon pour le golf, il vaut mieux écrire à la sorted(a, reverse=True)place.
Joel