16
\$\begingroup\$

Task

Given a non-empty list of positive digits, group them into sublists of equal sum. You may output any subset of solutions with maximal number of sublists (equivalently, minimal sum).

The input may contain repeat elements. There may not exist any solution but the singleton list containing the input itself. The output does not need to be in any particular order. You may not assume in the input list is in any particular order.

Format

You must accept a non-empty list of positive integers and output a 2D list of those integers, both in any reasonable format. Since I have restricted the inputs to 1-9, you may just accept a string of digits as input. However, your output give an obvious indication as to how the sublists are split.

Test Cases

These only show one solution, but if more exist, you may output them instead, or multiple, etc.

[9, 5, 1, 2, 9, 2]        ->  [[9, 5], [1, 2, 9, 2]]
[1, 1, 3, 5, 7, 4]        ->  [[1, 1, 5], [3, 4], [7]]
[2, 9, 6, 1, 5, 8, 2]     ->  [[2, 9], [6, 5], [1, 8, 2]]
[2, 8, 3, 9, 6, 9, 3]     ->  [[2, 3, 9, 6], [8, 9, 3]]
[5, 4, 1]                 ->  [[5], [4, 1]]
[3, 8, 1, 4, 2, 2]        ->  [[3, 1, 4, 2], [8, 2]]
[6, 9, 3, 8, 1]           ->  [[6, 3], [9], [8, 1]]
[4, 1, 6, 9, 1, 4, 5, 2]  ->  [[4, 1, 6, 1, 4], [9, 5, 2]]
[8, 7, 8, 6, 1]           ->  [[8, 7], [8, 6, 1]]
[2, 7, 4, 5]              ->  [[2, 7], [4, 5]]
[5, 2, 1, 4, 4]           ->  [[5, 2, 1], [4, 4]]
[5, 7, 4, 6, 2]           ->  [[5, 7], [4, 6, 2]]
[4, 1, 6, 6, 9]           ->  [[4, 9], [1, 6, 6]]
[2, 6, 4]                 ->  [[2, 4], [6]]
[6, 3, 1, 6, 8, 4, 5, 7]  ->  [[6, 3, 1, 6, 4], [8, 5, 7]]
[2, 2, 2]                 ->  [[2], [2], [2]]
[2, 4, 5]                 ->  [[2, 4, 5]]

Here is an extremely inefficient test case generator.

\$\endgroup\$
5
  • 4
    \$\begingroup\$ Note: this question was in the Sandbox for only an hour and a half. I strongly discourage this. The only reason I posted this so soon was because I want to repcap and I am confident with a challenge this simple. It's best to leave it for at least 48 hours and until you have sufficient upvotes or positive feedback. \$\endgroup\$
    – hyper-neutrino
    May 31, 2021 at 19:14
  • 1
    \$\begingroup\$ Why did you want to repcap so badly? \$\endgroup\$
    – user
    May 31, 2021 at 19:15
  • 3
    \$\begingroup\$ @user m̶y̶ ̶g̶o̶a̶l̶s̶ ̶a̶r̶e̶ ̶b̶e̶y̶o̶n̶d̶ ̶y̶o̶u̶r̶ ̶u̶n̶d̶e̶r̶s̶t̶a̶n̶d̶i̶n̶g̶ badge progress \$\endgroup\$
    – hyper-neutrino
    May 31, 2021 at 19:15
  • 2
    \$\begingroup\$ So these are multisets rather than lists? \$\endgroup\$
    – Neil
    May 31, 2021 at 20:09
  • 1
    \$\begingroup\$ @Neil I suppose that'd be more accurate, since you can reorder the numbers however you want. \$\endgroup\$
    – hyper-neutrino
    May 31, 2021 at 20:10

6 Answers 6

6
\$\begingroup\$

Jelly, 13 bytes

Œ!ŒṖ€Ẏ§E$ƇLÐṀ

Try it online!

Very slow, works on \$O(2^{n!})\$ complexity, where \$n\$ is the length of the array. Times out for anything with \$n \ge 8\$ on TIO.

This feels too long, especially the Œ!ŒṖ€Ẏ bit to generate all possible partitions.

This outputs all possible solutions, but the TIO link (the ÇḢ bit in the Footer) limits it to just one

How it works

Œ!ŒṖ€Ẏ§E$ƇLÐṀ - Main link. Takes a list L on the left
Œ!            - All permutations of L
  ŒṖ€         - Get all partitions of each permutation
     Ẏ        - Drop these down into a single list of 2d lists
        $Ƈ    - Keep those for which the following is true:
      §       -   Sums of each sublist
       E      -   Are all equal
          LÐṀ - Get those with a maximal length
\$\endgroup\$
2
  • \$\begingroup\$ Only replacement I can think of for Œ!ŒṖ€Ẏ is JṗL¹ƙ€, which comes out a byte longer if you account for chaining, but it doesn't feel impossible that there's something along those lines that would work. \$\endgroup\$ May 31, 2021 at 22:53
  • \$\begingroup\$ This is still a byte longer, but does get rid of the LÐṀ... \$\endgroup\$ May 31, 2021 at 23:18
6
\$\begingroup\$

J, 65 bytes

<@/:~((i.~/:~@;&.>)>@{])[:(\:#&>)@,@(g/.~+/&>)g=:<@#~"#.2#:@i.@^#

Try it online!

A different approach to brute force. All test cases execute in a few seconds on TIO.

Consider 2 7 4 5...

  • g=:<@#~"#.2#:@i.@^# Generate all subsets of the input, and save the verb that does this as g so we can use it again later.

    ┌┬─┬─┬───┬─┬───┬───┬─────┬─┬───┬───┬─────┬───┬─────┬─────┬───────┐
    ││5│4│4 5│7│7 5│7 4│7 4 5│2│2 5│2 4│2 4 5│2 7│2 7 5│2 7 4│2 7 4 5│
    └┴─┴─┴───┴─┴───┴───┴─────┴─┴───┴───┴─────┴───┴─────┴─────┴───────┘
    
  • (g/.~+/&>) Group subset elements by sum, and for each group of same-sum elements, generate all of its subsets:

    ┌┬─────────┬─────┬───────────┐
    ││┌┐       │     │           │
    ││││       │     │           │
    ││└┘       │     │           │
    ├┼─────────┼─────┼───────────┤
    ││┌─┐      │     │           │
    │││5│      │     │           │
    ││└─┘      │     │           │
    ├┼─────────┼─────┼───────────┤
    ││┌─┐      │     │           │
    │││4│      │     │           │
    ││└─┘      │     │           │
    ├┼─────────┼─────┼───────────┤
    ││┌───┐    │┌───┐│┌───┬───┐  │
    │││2 7│    ││4 5│││4 5│2 7│  │
    ││└───┘    │└───┘│└───┴───┘  │
    ├┼─────────┼─────┼───────────┤
    ││┌───┐    │┌─┐  │┌─┬───┐    │
    │││2 5│    ││7│  ││7│2 5│    │
    ││└───┘    │└─┘  │└─┴───┘    │
    ├┼─────────┼─────┼───────────┤
    ││┌───┐    │     │           │
    │││7 5│    │     │           │
    ││└───┘    │     │           │
    ├┼─────────┼─────┼───────────┤
     etc...
    
  • [:(\:#&>)@,@ Flatten, and sort down by length:

    ┌─────────┬───────┬───────────┬──┬───┬───┐
    │┌───┬───┐│┌─┬───┐│┌───┬─────┐│┌┐│┌─┐│┌─┐│
    ││4 5│2 7│││7│2 5│││7 4│2 4 5││││││5│││4││ ...etc..
    │└───┴───┘│└─┴───┘│└───┴─────┘│└┘│└─┘│└─┘│
    └─────────┴───────┴───────────┴──┴───┴───┘
    
  • <@/:~((i.~/:~@;&.>)>@{]) Find the first one whose elements match those of the input, and open it:

    ┌───┬───┐
    │4 5│2 7│
    └───┴───┘
    
\$\endgroup\$
6
  • 3
    \$\begingroup\$ Very nice! May not be the golfiest, but I always appreciate solutions that take a less brute-force approach to problems that offer a straightforward solution. \$\endgroup\$
    – hyper-neutrino
    Jun 1, 2021 at 4:40
  • 1
    \$\begingroup\$ For reference, porting this to Jelly comes to 21 bytes \$\endgroup\$ Jun 1, 2021 at 22:45
  • \$\begingroup\$ @cairdcoinheringaahing Nice. Jelly generally seems to clock in at about half or 40% of J from unscientific occasional noticing, so that's good compression. One of these days I'll learn Jelly.... \$\endgroup\$
    – Jonah
    Jun 1, 2021 at 22:47
  • \$\begingroup\$ The "generate all subsets" bit is definitely Jelly's main byte saver over J here tbh. ŒP does in 2 bytes what you assign to g. If J had a powerset builtin, this would be pretty close to Jelly in length \$\endgroup\$ Jun 1, 2021 at 22:49
  • 1
    \$\begingroup\$ Also, if/when you do want to start Jelly, feel free to drop by Jelly Hypertraining :) \$\endgroup\$ Jun 1, 2021 at 22:54
5
\$\begingroup\$

05AB1E, 12 bytes

œ€.œ€`éR.ΔOË

Try it online!

œ             # all permutations of the input
 €.œ          # for €ach permutation, get each partition
    €`        # flatten by one level to get a list of many partitions
      é       # sort by length (number of sublists in a partition)
       R      # reverse, longest are now at the front
        .Δ    # find the first partition where ...
          OË  # ... each sublist sums to the same value
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 12 bytes

∧≜S&p~c.+ᵛS∧

Try it online!

Even less efficient than caird's Jelly solution, as it recomputes every partition of every permutation for each sum it tries.

     ~c.        Output a partition of
   &p           a permutation of the input
        +ᵛ      in which every sublist has the same sum,
∧≜S       S∧    which is as small as possible.
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 124 bytes

f=(a,n=1)=>(g=(a,q=[],b=[],s=n)=>s?a.some((x,i)=>g(a.filter(_=>i--),q,[...b,x],s-x)):!a[Q=[...q,b],0]||g(a,Q))(a)?Q:f(a,n+1)

Try it online!

Commented

f = (                       // f is a recursive function taking:
  a,                        //   a[] = input list
  n = 1                     //   n = target sum, starting with 1
) => (                      //
  g = (                     // g is a recursive function taking:
    a,                      //   the original a[] or a subset of it
    q = [],                 //   q[] = list of sublists
    b = [],                 //   b[] = current sublist
    s = n                   //   s = n minus the sum of the terms in b[]
  ) =>                      //
  s ?                       //   if s is not equal to 0:
    a.some((x, i) =>        //     for each value x at index i in a[]:
      g(                    //       do a recursive call to g:
        a.filter(_ => i--), //         remove the i-th element from a[]
        q,                  //         pass q[] unchanged
        [...b, x],          //         append x to b[]
        s - x               //         subtract x from s
      )                     //       end of recursive call
    )                       //     end of some()
  :                         //   else:
    !a[ Q = [...q, b],      //     Q[] = copy of q[] with b[] appended
        0                   //     test whether a[] is empty
    ] ||                    //     if it's not:
      g(a, Q)               //       recursive call to g with q[] = Q[]
)(a) ?                      // initial call to g; if a solution is found:
  Q                         //   return it
:                           // else:
  f(a, n + 1)               //   try again with n + 1
\$\endgroup\$
3
\$\begingroup\$

Ruby, 110 109 107 bytes

->l,*r{1.step.find{|x|l.permutation.find{|c|w=-1;r=c.chunk{|z|(w+=z)/x}.map &:last;r.all?{|v|v.sum==x}}};r}

Try it online!

How:

  • Starting with x=1, check if we can split the list into chunks whose sum is x.

  • Do the same check with every possible permutation of the list.

  • If not, increase x and try again.

  • The trick is here: c.chunk{|z|(w+=z)/x}. This function splits an array into smaller

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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