Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
Inspired by https://xkcd.com/835
In the midst of his mid-life crisis, Santa has impulsively purchased a Sports Sleigh™ for present delivery this year. The only problem is that this sleigh has a specially designed Infinite Present Trunk with rigid sides instead of a present bag with flexible ones. This means Santa must pack the presents optimally so there is as little empty space as possible.
The Challenge
Write a program that takes as input a list of positive integers (representing the widths of the presents) and outputs a list of lists of positive integers (representing rows of presents) where each row follows these two rules:
- There are never fewer presents in each row than the one before it
- The total width of each row is the same as the width of the widest present
Your program must return any constant value if it is impossible to fulfill these rules. There may be multiple valid solutions; your program may output any of them.
Examples
Input: [5, 1, 2, 6, 4, 3, 3]
Possible output: [[6], [5, 1], [2, 4], [3, 3]]
Visualization:
vvvvvv
+++++=
xx----
___ooo
Input: [9, 4, 2, 4, 5, 3]
Possible output: [[9], [4, 5], [3, 4, 2]]
Visualization:
+++++++++
vvvv=====
xxxoooo--
I don't actually know if there exist any inputs with multiple possible outputs; it doesn't seem like it to me, but if you can prove there are or aren't please leave a comment! (I'm not counting trivial differences with different orderings of presents on a single row.)
[9, 9, 6, 5, 4, 4, 3, 2, 2, 1]
has three non-trivial solutions:[[9], [9], [4, 5], [3, 6], [1, 2, 2, 4]]
,[[9], [9], [4, 5], [1, 2, 6], [2, 3, 4]]
, and[[9], [9], [3, 6], [2, 2, 5], [1, 4, 4]]
. \$\endgroup\$