27
3
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.
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!
2May we take the weights in sorted order? (either ascending or descending) – Arnauld – 2019-08-30T21:55:46.003
4"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. – Joel – 2019-08-30T23:49:45.243
1Suggested test case:
[8, 8, 8, 5, 1]
->[[8, 8], [8, 5, 1]]
– Hiatsu – 2019-08-31T01:05:58.9303Or even better:
[8, 5, 8, 8, 1, 2]
->[[8, 8], [8, 5, 2, 1]]
– Hiatsu – 2019-08-31T01:16:13.850"You must support weights up to 9,999 kg, at minimum" So is this intended to be not just code golf, but code golf using an efficient algorithm? – Jonah – 2019-09-01T02:40:53.743
2@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. – Beefster – 2019-09-02T17:13:34.920
@Jonah the purpose of that is actually to require a minimum integer precision. – Beefster – 2019-09-02T17:17:28.327
@Joel, It means you need to be able to handle inputs of up to 9,999 boxes, at minimum. Your solution can blow up once you add the 10,000th box; it only has to work for inputs of that size and smaller. (maybe someone wants to make a regex to solve the problem or something equally insane) – Beefster – 2019-09-02T17:19:50.580
@Hiatsu added, though I'm curious as to what makes this a good test case – Beefster – 2019-09-02T17:22:10.890
@Beefster So it means that the solution should be able to provide a correct answer for the input range given an infinite amount of time and memory. Is that right? – Joel – 2019-09-02T17:24:43.387
@Joel yes, correct. (Though to be pedantic, I would say 'sufficient' rather than 'infinite' there, since a correct solution solves the general problem in finite time and space since the problem is decidable.) – Beefster – 2019-09-02T17:26:49.477
@Beefster, woops, I quote the wrong thing. I meant to say: "You must support up to 9,999 total boxes, at minimum." -- So is this intended to be not just code golf, but code golf using an efficient algorithm? Eg, the submitted solutions do not meet this requirement afaict. – Jonah – 2019-09-02T19:03:35.097
@Beefster That test case has strongly unbalanced stacks, unlike all the other test cases. – Hiatsu – 2019-09-03T01:28:24.537
1@Jonah efficiency doesn't matter as long as the program terminates eventually. All that matters is that the solution produces an optimal number of stacks. This problem is $O(n!)$ at worst. The purpose of the 9,999 box requirement is to specify a soft minimum on space requirements. – Beefster – 2019-09-03T15:07:35.957