AoCG2021 Day 5: Balancing sleigh with lots of trunks

Question

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2015 Day 24, Part 2.

Here's why I'm posting instead of Bubbler

---

To recap: Santa gives you the list of gift packages' weights. The packages must be split into multiple groups so that each group has the same weight, so that the sleigh is balanced and Santa can defy physics to deliver the presents.

Also, one of the groups goes to the passenger compartment, and Santa wants to have the maximal legroom, so the number of packages in there must be minimal. If there are ties, choose the one with the minimal "quantum entanglement" - the product of all weights in that group - to minimize the risk of physics doing its job, so to speak.

If you were to divide [1, 2, 3, 4, 5, 7, 8, 9, 10, 11] into three groups of equal weight, the possible choices are (QE stands for Quantum Entanglement):

Group 1;             Group 2; Group 3
11 9       (QE= 99); 10 8 2;  7 5 4 3 1
10 9 1     (QE= 90); 11 7 2;  8 5 4 3
10 8 2     (QE=160); 11 9;    7 5 4 3 1
10 7 3     (QE=210); 11 9;    8 5 4 2 1
10 5 4 1   (QE=200); 11 9;    8 7 3 2
10 5 3 2   (QE=300); 11 9;    8 7 4 1
10 4 3 2 1 (QE=240); 11 9;    8 7 5
9 8 3      (QE=216); 11 7 2;  10 5 4 1
9 7 4      (QE=252); 11 8 1;  10 5 3 2
9 5 4 2    (QE=360); 11 8 1;  10 7 3
8 7 5      (QE=280); 11 9;    10 4 3 2 1
8 5 4 3    (QE=480); 11 9;    10 7 2 1
7 5 4 3 1  (QE=420); 11 9;    10 8 2

Since [11, 9] has the smallest number of packages, you should choose that one.

It turns out that Santa's sleigh is a pretty advanced model and has a bunch of trunks instead of one. Under the same conditions, determine which presents should go into the passenger compartment.

Input: The total number of groups n, and the list of packages' weights. n is at least 3, and it is guaranteed that the list of weights can be split into n groups of equal weight.

Output: The optimal list of packages to be placed in the passenger compartment. The individual packages may be output in any order. If there are multiple optimal solutions (same number of packages and same quantum entanglement), output any one of them.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Weights, Groups -> Answer
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 3 -> [11, 9]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 4 -> [11, 4]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 5 -> [11, 1]
[1, 1, 2, 2, 6, 6, 6, 6, 9], 3 -> [1, 6, 6] or [2, 2, 9]
[1, 2, 2, 3, 3, 3, 4, 6, 6, 9], 3 -> [4, 9]
[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2], 3 -> [3, 2, 2, 2]

Answer 1

05AB1E, 20 bytes

Can at least run some of the cases fast enough for TIO, with 6 bytes more all of them.

OI÷ÅœΣP}éIã.Δ˜{¹{Q}н

Try it online!

Answer 2

Jelly, 20 bytes

Œ!ŒṖ€ẎL=¥Ƈ§E$ƇẎPÞLÞḢ

Try it online!

Very messy port of my Vyxal answer. Full program.

-1 thanks to ovs.

Œ!                   # Permutations
  ŒṖ€                # Partitions of each of these
     Ẏ               # Flattened by depth 1
      ---Ƈ           # Filter by...
        ¥            # Last two links as a dyad...
      L              # Length
       =             # Equal to other input value?
          ---Ƈ       # Filter by...
            $        # Last two links as a monad...
          §          # Vectorised sums...
           E         # All equal?
              Ẏ      # Flatten by one level
                 -Þ  # Sort by...
                 L   # Length
               -Þ    # Sort by (tiebreak) product
               P     # Product
                   Ḣ # Get the first item.

Answer 3

Python 3, 211 bytes

lambda l,n:min([z for x in c(chain(*[[*c(l,_)]for _ in range(len(l))]),n)if (sorted(chain(*x))==l)*(len({*map(sum,x)})<2)for z in x],key=lambda y:eval("*".join(map(str,y))))
from itertools import*
c=combinations

Try it online!

@tsh's method is too complex for me, so my own itertools based solution

Answer 4

Python 3, 143 bytes

f=lambda a,p,u=[],v=[]:p<2and a or a and min(f(a[1:],p,a[:1]+u,v),f(a[1:],p,u,a[:1]+v),key=len)or sum(u)==sum(v)/~-p==sum(f(v,p-1))and u or u+v

Try it online!

f=(lambda 
  a,                        # input array, weight of packages
  p,                        # how many groups
  u=[],                     # packages selected in this group
  v=[]:                     # packages not selected in this group
    p<2 and a or            # if we want only 1 group
                            # then we simply include everything to this group
    a and min(              # if there are any packages
      f(a[1:],p,a[:1]+u,v), # we try to include it in current group
      f(a[1:],p,u,a[:1]+v), # or try to exclude it in current group
      key=len) or           # find out the answer which is shorter
                            # otherwise, every package are processed
    sum(u)==sum(v)/~-p      # if sum of selected package is what we want
          ==sum(f(v,p-1))   # and remaining packages may be grouped correctly
      and u or              # We found a possible grouping
    u+v                     # We failed to find out a correct grouping
                            # We return `u+v` here as it would be long enough
                            # to avoid it been selected after the min function
)

Answer 5

05AB1E, 13 bytes

.ŒʒOË}€`ΣP}éн

First input is the amount of groups, second the list of weights.

Try it online (times out for the third test case with 5 groups, but works for the others).

Explanation:

.Π         # Get all possible ways to split the (implicit) second input-list
            # into the first (implicit) input-integer amount of group-lists
  ʒ         # Filter this list of lists of group-lists by:
   O        #  Get the sum of each inner group-list
    Ë       #  And check if all sums are equal
  }€`       # After the filter: flatten the list of lists of lists one level down
     ΣP}    # Sort this list of lists by their product
        é   # After that sort again by their length
         н  # Pop and leave the first list
            # (which is output implicitly as result)

Answer 6

Charcoal, 46 bytes

ＦＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξηＦ⁼Σθ×η⌈Ｅι↨¹κＦι⊞υ⟦ＬλΠλλ⟧Ｉ⊟⌊υ

Try it online! Link is to verbose version of code. Very slow so only the smallest test case completes on TIO. Explanation:

ＦＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξη

Loop through all possible allocations of presents to compartments (including redundant allocations such as switching the allocations of two compartments).

Ｆ⁼Σθ×η⌈Ｅι↨¹κ

If the largest compartment under this allocation has the correct share of the total weight, then...

Ｆι⊞υ⟦ＬλΠλλ⟧

... save the size and product of the compartment with the compartment.

Ｉ⊟⌊υ

Output the compartment with the smallest size and product.

For comparison I've written a relatively fast algorithm, however it's 89 bytes long. (8 bytes can be trivially removed, but this makes the code much slower.)

≔⟦Ｅηυ⟧ζ≔⟦⟧εＷ⌈⁻θεＦ№θι«⊞ει≔⟦⟧δＦζＦηＦ¬∨⊙…λμ№νι›×η⁺ι↨¹§λμΣθ⊞δＥλ⎇⁼πμ⁺ξ⟦ι⟧ξ≔δζ»ＦζＦι⊞υ⟦ＬκΠκκ⟧Ｉ⊟⌊υ

Try it online! Link is to verbose version of code. Explanation:

≔⟦Ｅηυ⟧ζ

Start with n empty compartments.

≔⟦⟧εＷ⌈⁻θεＦ№θι«⊞ει

Enumerate the presents in descending order. (This is the best I can do given a lack of a sort primitive in Charcoal.)

≔⟦⟧δ

Start building up a new list of allocations of presents to compartments.

ＦζＦηＦ¬∨⊙…λμ№νι›×η⁺ι↨¹§λμΣθ

Loop through all of the compartments in all of the allocations, but ignore compartments when the same size present was already placed in an earlier compartment by a previous iteration or if it would overfill the current compartment.

⊞δＥλ⎇⁼πμ⁺ξ⟦ι⟧ξ

Save the new allocation.

≔δζ

Save the new list of allocations.

»ＦζＦι⊞υ⟦ＬκΠκκ⟧

At this point all of the presents will have been distributed to all of the compartments without overfilling any compartment, so flatten the list of allocations and get the size and product of each compartment.

Ｉ⊟⌊υ

Output the compartment with the smallest size and product.

Answer 7

Rust, 348 bytes

|w:&mut[_],g|{fn p(w:&mut[u64],i:usize,g:u64)->Option<Vec<u64>>{Some(if w[i..].iter().sum::<u64>()==g{if i!=0{p(&mut w[..i],0,g)?;}w[i..].to_vec()}else{let mut r=vec![];for j in i+1..w.len(){w.swap(i,[i+1,j][j%2]);p(w,j,g).map(|x|r.push(x));}r.iter().map(|x|(x.len(),x.iter().product::<u64>(),x)).min()?.2.to_vec()})}p(w,0,w.iter().sum::<u64>()/g)}

Try it online!

I think somebody should talk to Santa about time complexity.

Ungolfed:

|weights: &mut [_], group_size| {
    fn permutate(weights: &mut [u64], i: usize, group_weight: u64) -> Option<Vec<u64>> {
        Some(if weights[i..].iter().sum::<u64>() == group_weight {
            if i != 0 {
                permutate(&mut weights[..i], 0, group_weight)?;
            }
            weights[i..].to_vec()
        } else {
            let mut results = vec![];
            for j in i + 1..weights.len() {
                weights.swap(i, [i + 1, j][j % 2]);
                permutate(weights, j, group_weight).map(|x| results.push(x));
            }
            results
                .iter()
                .map(|x| (x.len(), x.iter().product::<u64>(), x))
                .min()?
                .2
                .to_vec()
        })
    }
    permutate(weights, 0, weights.iter().sum::<u64>() / group_size)
}

Answer 8

Husk, 20 bytes

◄Π←kLΣfËΣföEeO¹OΣπ²Ṗ

Try it online!

Unfortunately too inefficient to run any of the provided test cases, but I think that it's correct based on testing with smaller ones:

[1,1,2,2,3] -> [3]
[3,1,2,2,4,0] -> [4]
[3,2,2,3,4,1] -> [4,1]

How?

föEeO¹OΣπ²Ṗ = Get all partitions, by filtering all combinations of n groups of all subsets of the input list (π²Ṗ), selecting (fö) only those that are equal (Ee) to the sorted input list (O¹) after flattening & sorting (OΣ). I thought that the Husk fork (§) combinator should have saved a byte here, but I couldn't get it to work...

fËΣ = Filter (f) only those partitions with equal sums (ËΣ)

←kLΣ = Flatten the list of lists (Σ), and get the group of those with the smallest lengths (←kL)

◄Π = Return the list with the smallest product.

Answer 9

Python 3, 229 bytes:

f=lambda l,i,s,c,j:[(j,c)] if sum(c)==s else(l and f(l[:-1],i-1,s,c+[l[-1]],j+[i])+f(l[:-1],i-1,s,c,j))
y=lambda p,g:[q for w,q in f(p,len(p)-1,sum(p)//g,[],[]) if f([m for n,m in enumerate(p)if n not in w],0,sum(p)//g,[],[])][0]

Try it online!

Answer 10

TypeScript Types, 957 bytes

//@ts-ignore
type a<N,I=0,M=[]>=N extends M["length"]?M:a<N,I,[...M,I]>;type b<T,N=[]>=T extends[infer A,...infer T]?b<T,[...N,...a<A>]>:N;type c<T,S,G=[],U=T>=S extends[]?G:U extends U?S extends[...U[1],...infer S]?c<Exclude<T,U>,S,[...G,U]>:never:0;type d<A,B,N=[]>=A extends[...B,...infer A]?d<A,B,[...N,0]>:N;type e<T>={[K in keyof T]:T[K][1]};type f<T,N,S,G=[]>=N extends[0,...infer M]?c<T,S>extends infer X?X extends X?f<Exclude<T,X[number]>,M,S,[...G,e<X>]>:0:0:G;type M<I,N,M=a<N>,S=d<b<I>,M>,A=f<{[K in keyof I]:[K,a<I[K]>]}[number],M,S>[number],R=i<k<j<A>>>>={[K in keyof R]:R[K]["length"]};type g<A,B,C=[]>=A extends[0,...infer A]?g<A,B,[...C,...B]>:C;type h<T,N=[0]>=T extends[infer A,...infer T]?b<T,g<N,A>>:N;type i<T>=(T extends T?(x:()=>T)=>0:0)extends(x:infer U)=>0?U extends()=>infer V?V:0:0;type j<U,V=keyof U>=U extends U?keyof U extends V?U:never:never;type k<T,V=keyof(T extends T?h<T>:0)>=T extends T?keyof h<T>extends V?T:never:never

This really pushes TypeScript's type system to the limit. Calling the generic will give "Type instantiation is excessively deep and possibly infinite", but it will eventually still result in a valid answer for most test cases.

Try It Online!

Less Golfed (but just as cryptic)

Answer 11

Pari/GP, 143 bytes

(w,g)->p=vecprod;s=vecsum(r=w)/g;forperm(vecsort(w),a,for(k=q=!c=0,#a,c+=a[k];c%s||q++>2||b=Vec(a[1..k]));#b==#r&&p(b)<p(r)||#b<#r&&q>g&&r=b);r

Try it online!

TIL: the forperm built-in only works for sorted lists. Thanks @tsh for providing a new testcase.

Answer 12

Vyxal, 26 bytes

ṖvøṖÞf'L⁰=;'Ṡ≈;vhƛ₍LΠwJ;↓Ṫ

Try it Online!

This was horrible to make. Vyxal is horridly cursed sometimes...

Note: Almost all sort-related functions are broken.

\$O\left(n! \cdot 2^n\right)\$ complexity I think, so can't run any testcases.

Ṗ                          # All permutations
 vøṖ                       # All partitions of these
    Þf                     # Flatten by 1 layer to get all partitions of permutations
      '   ;                # Filter by...
       L⁰=                 # Length is equal to input
           '  ;            # Filter by
            Ṡ≈             # Sums are all same
               vh          # Get first of each
                 ƛ     ;   # Map to...
                  ₍LΠ      # [length, product]
                     wJ    # Appended to original
                        ↓  # Minimum by last item ([length, product])
                         Ṫ # Remove the last of this.

22 byte version if sorting worked

Answer 13

Ruby, 181 144 140 129 bytes

->l,n{*r=l;(n**l.size).times{|x|z=l.group_by{(x/=n)%n}.values;z.map(&:sum).uniq[1]||r=(z<<r).min_by{|x|[x.size,x.reduce(:*)]}};r}

Try it online!

Answer 14

Wolfram Language (Mathematica), 88 bytes

<<Combinatorica`
SortBy[Join@@Select[KSetPartitions@##,Equal@@Tr/@#&],1##&@@#+0#&][[1]]&

Try it online!