CGAC2022 Day 17: Present Heap

Question

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.)

Answer 1

05AB1E, 14 bytes

æʒO¹àQ}éæ.Δ˜ÃQ

Try it online!

Explanation:

æʒO¹àQ}éæ.Δ˜ÃQ
æ               # powerset
 ʒ    }         # filter:
  O             #   sum
   ¹à           #   maximum of input
     Q          #   are equal
       é        # sort by length
        æ       # powerset
         .Δ     # first where the following is true:
           ˜    #   flatten
            Ã   #   intersect with implicit input
             Q  #   is equal to implicit input

Answer 2

Vyxal, 16 bytes

ṖvøṖÞf'Ṡ?G=A;hÞṡ

Try it Online!

Extremely inefficient. Simply brute-forces it.

ṖvøṖÞf'Ṡ?G=A;hÞṡ
Ṗ                 # All permutations
 vøṖ              # For each, get a list of all ways to partition the list
    Þf            # Shallow flatten
      '           # Filter:
       Ṡ          #  Sum each
        ?G=A      #  All are equal to the max of the input?
            ;     # End filter
             h    # First item
              Þṡ  # Sort by length

Answer 3

Jelly, 16 bytes

ŒPS⁼¥ƇṀŒPFṢ⁼ɗƇṢṪ

A monadic Link that accepts a list of integers and yields a list of lists of integers representing the present rows, or the integer 0 if not possible.

Try it online!

How?

ŒPS⁼¥ƇṀŒPFṢ⁼ɗƇṢṪ - Link: list of integers, Widths
ŒP               - power-set (Widths) (results are ordered by length, ascending)
      Ṁ          - maximum (Widths)
     Ƈ           - filter (the sets) keeping those for which:
    ¥            -   last two links as a dyad - f(set, max_width):
  S              -     sum (set)
   ⁼             -     (that) equals (max_width)?
       ŒP        - power-set (those)
              Ṣ  - sort (Widths)
             Ƈ   - filter (the sets of valid-sum sets) keeping those for which:
            ɗ    -   last three links as a dyad - f(set_of_sets, sorted_widths):
         F       -     flatten (the set_of_sets)
          Ṣ      -     sort (that)
           ⁼     -     (that) equals (sorted_widths)?
               Ṫ - tail

Answer 4

JavaScript (ES2020), 140 bytes

Returns 0 if there's no solution.

f=(a,m=Math.max(...a),t,o=[],...p)=>a.some((v,i)=>f(a.filter(_=>i--),m,~~t+v,o,...p,v),t^m|p[o[0]?.length]||(o=[p,...o],p=t=[]))?O:a+p?0:O=o

Attempt This Online!

Commented

f = (                   // f is a recursive function taking:
  a,                    //   a[] = input array
  m = Math.max(...a),   //   m   = highest value in a[]
  t,                    //   t   = sum of the current sub-array
  o = [],               //   o[] = array of sub-arrays
  ...p                  //   p[] = current sub-array
) =>                    //
a.some((v, i) =>        // for each value v at index i in a[]:
  f(                    //   do a recursive call:
    a.filter(_ => i--), //     remove the i-th element from a[]
    m,                  //     pass m unchanged
    ~~t + v,            //     add v to t
    o,                  //     pass o[] unchanged
    ...p, v             //     append v to p[]
  ),                    //   end of recursive call
                        //   loop initialization:
  t ^ m |               //     do nothing if t is not equal to m
  p[o[0]?.length] ||    //     or p is longer than o[0] (which is either the
  (                     //     previous sub-array or still undefined)
    o = [p, ...o],      //     otherwise, insert p[] at the beginning of o[]
    p = t = []          //     and start with p[] empty and t zero'ish
  )                     //
) ?                     // end of some(); if truthy:
  O                     //   return the solution O[]
:                       // else:
  a + p ?               //   if either a[] or p[] is non-empty:
    0                   //     incomplete or invalid solution: do nothing
  :                     //   else:
    O = o               //     save the solution in O[]

Answer 5

Japt, 21 bytes

Returns undefined if there is no result.

n
à f@̶XxÃà æ@eXÔc n

Try it

n\nà f@̶XxÃà æ@eXÔc n     :Implicit input of array U
n                          :Sort
 \n                        :Reassign to U
   à                       :Combinations
     f                     :Filter by
      @                    :Passing each X through the following function
       Ì                   :  Last element of U
        ¶                  :  Is equal to
         Xx                :  X reduced by addition
           Ã               :End filter
            à              :Combinations (in descending order of length)
              æ            :First element to return true
               @           :When passed through the following function as X
                e          :  U is equal to
                 XÔ        :    Reverse X (mutates the original)
                   c       :    Flatten
                     n     :    Sort

Answer 6

Pyth, 18 bytes

MfqSsTSGyHlDhgQgeS

Try it online!

Returns an index error when there is no solution.

Somehow only used alphabetical characters as well, which is neat.

Explanation

Power set is the poor man's partition. This solution is brute force, but a rather elegant one, I think. First we take the power set of the input and filter for elements whose sum is equal to the desired width. This means we now have a list of all possible rows (often with duplicates). Then we take the power set of the rows, and filter for elements which use the exact same elements as the input. This will give us all sets of rows that are valid solutions. From here it's simple, just pick any set and sort the rows by number of elements. The beauty comes from the fact that both of these steps look the same if you squint, and so by being clever we can write a single "power set and filter" function and just apply it twice.

MfqSsTSGyHlDhgQgeSQQ    # implicitly add QQ to the end
                        # implicitly assign Q = eval(input())
M                       # define g(G, H):
 f      yH              #   filter powerset(H) on lambda T
  qSsTSG                #   when H is a list and G is a number, this will check if T sums to G
                        #   but when H is a list of lists and G is a list, this will check if T and G use the same elements
          lD            # sort using length as the key
            h           # the first element of
             gQ         # power set filter Q,
               geSQQ    # power set filter max(Q), Q

Answer 7

Charcoal, 58 bytes

Ｗ⁻Ｅ⊟ΦＥＸＬθＬθΦＥθΦθ⁼ν﹪÷κＸＬθπＬθμ⬤κ⁼Σμ⌈θ⁺⟦Ｌκ⟧κυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Try it online! Link is to verbose version of code. Explanation: Lots and lots of brute force (takes minutes on the examples) so link only has three presents.

61 bytes for a slightly less inefficient version that can just about complete the examples on TIO:

≔Ｅ⊟ΦＥＸＬθＬθΦＥθΦθ⁼μ﹪÷ιＸＬθξＬθλ⬤ι⁼Σλ⌈θ⁺⟦Ｌι⟧ιηＷ⁻ηυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Try it online! Link is to verbose version of code. Explanation: Calculates all nⁿ permutations of n presents in n rows, filters for valid answers, picks one, then sorts it. (But unlike the first version, it doesn't perform the calculation each pass of the sorting loop.)

65 bytes for a slightly less inefficient version:

≔÷Σθ⌈θη≔Ｅ⊟ΦＥＸηＬθΦＥθΦθ⁼μ﹪÷ιＸηξηλ⬤ι⁼Σλ⌈θ⁺⟦Ｌι⟧ιηＷ⁻ηυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Try it online! Link is to verbose version of code. Explanation: Still exponential time, but since we know the width of each row then we can calculate the number of rows, and take the nth power of that instead.

71 bytes for a version that's less inefficient for a large enough number of rows:

≔⟦⟦⟧⟧ηＦθ≔ΣＥηＥ⊞ＯκυΦＥκ⎇⁼νπ⁺ξ⟦ι⟧ξξη≔Ｅ⊟Φη⬤ι⁼Σλ⌈θ⁺⟦Ｌι⟧ιηＷ⁻ηυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Attempt This Online! Link is to verbose version of code. Explanation: Uses dynamic programming to generate integer partitions directly instead of filtering permutations, so O(A000110(n)) instead of O(kⁿ). This means that it can handle the example in @JonathanAllan's comment.

72 bytes for a version that's somewhat efficient for a small enough number of rows:

≔⟦Ｅ÷Σθ⌈θυ⟧ηＦθ≔ΣＥηΦＥκＥκ⎇⁼νπ⁺ξ⟦ι⟧ӧμν⌈θη≔Ｅ⊟η⁺⟦Ｌι⟧ιηＷ⁻ηυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Attempt This Online! Link is to verbose version of code. Explanation: Based on the third version but using dynamic programming to to generate only matching integer partitions, but still generates all permutations of all integers in all rows.

85 bytes for an efficient version:

≔⟦υ⟧ηＦθ≔ΣＥη⁺ΦＥκＥκ⎇⁼νπ⁺ξ⟦ι⟧ξ⬤쬛Σξ⌈θ…⟦⁺κ⟦⟦ι⟧⟧⟧‹Ｌκ÷Σθ⌈θη≔Ｅ⊟η⁺⟦Ｌι⟧ιηＷ⁻ηυＦ№ι⌊ι⊞υ⌊ι⭆¹Ｅυ✂λ¹

Attempt This Online! Link is to verbose version of code. Explanation: Combination of the previous two so it avoids considering multiple empty rows for the same integer.

Answer 8

JavaScript (Node.js), 167 bytes

f=(x,i=z=[],...y)=>z=x.map((v,j)=>f(j=x.filter(_=>j--),[...i,v],...y)|f(j,[v],i,...y),L=[i,...y])+x?z:L.some((e,j)=>e.length<(y[j-1]||i).length|eval(e.join`+`)!=i)?z:L

Try it online!

Answer 9

Pip, 43 bytes

@(DNa=DNFL_FI(Ma=$+_FIaCB_MF,#a)CB_MF,#a)|0

Try It Online!

Pip doesn't have a command for powersets (that I could find), so I had to construct them manually. Explanation:

Ma=$+_FIaCB_MF,#a

All combinations of the input list where the sum of the combination equals the input max i.e. all possible row combinations

DNa=DNFL_FI(   )CB_MF,#a

All valid combinations of all possible row combinations, determined by comparing the sorted flattened combination with the sorted input

@()|0

Outputs the first valid combination, or 0 if no combination is found. No reordering is required, as the combination operator aCBb in pip automatically orders lists by ascending length.

Answer 10

05AB1E, 11 bytes

àÅœéæʒ˜œ€Qà

Extremely slow. Will output all possible results (replace filter ʒ with find_first .Δ to only output one - although that will still timeout for the second test case).

Try it online.

Explanation:

à            # Get the maximum of the (implicit) input-list
 Ŝ          # Get lists of all positive integers that sum to this maximum
   é         # Sort those lists by length (shortest to longest)
    æ        # Get the powerset of this list of lists
     ʒ       # Filter this list of lists of rows by:
      ˜      #  Flatten the list of rows to a single list
       œ     #  Get all permutations of this flattened list
        €Q   #  Check for each permutation whether it's equal to the (implicit) input
          à  #  Check if any is truthy
             # (after which the filtered list is output implicitly)