32
\$\begingroup\$

You have a bunch of heavy boxes and you want to stack them in the fewest number of stacks possible. The issue is that you can't stack more boxes on a box than it can support, so heavier boxes must go on the bottom of a stack.

A box can support a total weight of boxes up to its own weight on top of it.

The Challenge

Input: A list of weights of boxes, in whole kg.

Output: A list of lists describing the stacks of boxes. This must use the fewest number of stacks possible for the input. To be a valid stack, the weight of each box in the stack must be greater than or equal to the sum of the weight of all boxes above it.

Examples of Valid stacks

(In bottom to top order)

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

Examples of Invalid stacks

(In order from bottom to top)

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

Example Test Cases

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

Rules and Assumptions

  • Standard I/O rules and banned loopholes apply
  • Use any convenient format for I/O
    • Stacks may be described top to bottom or bottom to top, as long as you are consistent.
    • The order of stacks (rather than boxes within those stacks) does not matter.
    • You may also take input boxes as a presorted list. Order is not particularly important for the input, so long as the general problem isn't being solved by the sorting itself.
  • If there is more than one optimal configuration of stacks, you may output any one of them
  • You may assume that there is at least one box and that all boxes weigh at least 1 kg
  • You must support weights up to 9,999 kg, at minimum.
  • You must support up to 9,999 total boxes, at minimum.
  • Boxes with the same weight are indistinguishable, so there is no need to annotate which box was used where.

Happy golfing! Good luck!

\$\endgroup\$
14
  • 2
    \$\begingroup\$ May we take the weights in sorted order? (either ascending or descending) \$\endgroup\$
    – Arnauld
    Commented Aug 30, 2019 at 21:55
  • 4
    \$\begingroup\$ "You must support up to 9,999 total boxes, at minimum." How is "support" interpreted here? Does it merely mean the program should be able to take such size of input, or does it mean that the program should actually provide the answer in a reasonable amount of time? If it is the latter, there should be much larger test cases provided. \$\endgroup\$
    – Joel
    Commented Aug 30, 2019 at 23:49
  • 1
    \$\begingroup\$ Suggested test case: [8, 8, 8, 5, 1] -> [[8, 8], [8, 5, 1]] \$\endgroup\$
    – Hiatsu
    Commented Aug 31, 2019 at 1:05
  • 3
    \$\begingroup\$ Or even better: [8, 5, 8, 8, 1, 2] -> [[8, 8], [8, 5, 2, 1]] \$\endgroup\$
    – Hiatsu
    Commented Aug 31, 2019 at 1:16
  • 2
    \$\begingroup\$ @Arnauld, since otherwise that would add uninteresting sorting code to an answer, I'm going to say yes, you can take in the inputs in sorted order. \$\endgroup\$
    – Beefster
    Commented Sep 2, 2019 at 17:13

6 Answers 6

6
\$\begingroup\$

JavaScript (Node.js),  139 122  116 bytes

Expects the input sorted in ascending order.

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

Try it online!

Commented

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[]
\$\endgroup\$
5
\$\begingroup\$

Jelly, 19 bytes

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

Try it online!

Obvious -3 thanks to Nick Kennedy...

Top to bottom.

Explanation:

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇ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]])
\$\endgroup\$
2
  • \$\begingroup\$ Any chance at a less compact version with explanation? I learn a ton from those. \$\endgroup\$ Commented Sep 2, 2019 at 8:00
  • 1
    \$\begingroup\$ @JohnKeates Added one. \$\endgroup\$ Commented Sep 2, 2019 at 13:03
3
\$\begingroup\$

Python 3.8 (pre-release), 178 bytes

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

Try it online!

Now works on all possible inputs. (It times out on TIO with more than ten or so boxes, but it calculates a correct answer)

\$\endgroup\$
3
  • 2
    \$\begingroup\$ list(reversed(sorted(a))) can be written as sorted(a)[::-1] for golfing purpose. \$\endgroup\$
    – Joel
    Commented Aug 30, 2019 at 23:51
  • \$\begingroup\$ You would think I would know that by now, especially since I do so much other indexing. Thanks. \$\endgroup\$
    – Hiatsu
    Commented Aug 30, 2019 at 23:53
  • \$\begingroup\$ Just as a side remark, if not for golfing it would be better write sorted(a, reverse=True) instead. \$\endgroup\$
    – Joel
    Commented Aug 30, 2019 at 23:58
0
\$\begingroup\$

Python3, 377 bytes

Takes input sorted in descending order. A little long, but fast.

E=enumerate
def f(b):
 q=[(b,[])]
 for b,c in q:
  if[]==b:return c
  Q,S=[(b[1:],[],1,0)],{}
  for B,o,I,k in Q:
   if o:S[len(o)]=S.get(len(o),[])+[o]
   if B:O=o+[I];Q+=[(B[1:],O,I+1,k+B[0])]*(k+B[0]<=b[0]and all(b[K]>=sum(b[j]for j in O[J+1:])for J,K in E(O)));Q+=[(B[1:],o,I+1,k)]
  for I in S[max(S)]:q+=[([a for i,a in E(b)if i not in[0]+I],c+[[b[0]]+[b[i]for i in I]])]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Scala 3, 270 bytes

A port of @Hiatsu's Python answer in Scala.

270 bytes, it can be golfed more.


Golfed version. Attempt This Online!

a=>f(a.sorted).map(_.filter(_.nonEmpty)).minBy(_.map(_.sum).sum)
def f(n:List[Int],s:List[List[Int]]=List(List())):List[List[List[Int]]]=n match{
case h::t=>s.indices.flatMap{i=>if(h>=s(i).sum)f(t,s.updated(i,h+:s(i)))else Nil}.toList++f(t,s:+List(h))
case Nil=>List(s)}

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    val test1 = List(87, 432, 9999, 1234, 3030)
    val test2 = List(1, 2, 3, 4, 5, 6, 9, 12)
    val test3 = List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
    val test4 = List(8, 5, 8, 8, 1, 2)
    
    println(minimalPartition(test1))
    println(minimalPartition(test2))
    println(minimalPartition(test3))
    println(minimalPartition(test4))
  }

  def findPartitions(numbers: List[Int], subsets: List[List[Int]] = List(List())): List[List[List[Int]]] = numbers match {
    case head :: tail =>
      subsets.indices.flatMap { i =>
        if (head >= subsets(i).sum) {
          val newSubset = head +: subsets(i)
          val newSubsets = subsets.updated(i, newSubset)
          findPartitions(tail, newSubsets)
        } else Nil
      }.toList ++ findPartitions(tail, subsets :+ List(head))
    case Nil => List(subsets)
  }

  def minimalPartition(numbers: List[Int]): List[List[Int]] = {
    val sortedNumbers = numbers.sorted
    val partitions = findPartitions(sortedNumbers)
    val nonEmptyPartitions = partitions.map(_.filter(_.nonEmpty))
    nonEmptyPartitions.minBy(_.map(_.sum).sum)
  }
}
\$\endgroup\$
0
\$\begingroup\$

Python 3, 114 bytes

f=lambda q,z=[]:q and min((f(q[1:],z[:i]+[q[:1]+y]+z[i+1:])for i,y in enumerate(z+[[]])if[sum(y)]<=q),key=len)or z

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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