| Bytes | Lang | Time | Link |
|---|---|---|---|
| nan | Scala | 230521T003147Z | 138 Aspe |
| 074 | Julia 1.7 + Combinatorics | 230521T202413Z | MarcMush |
| 010 | Nekomata | 230522T060857Z | alephalp |
| 145 | Wolfram Language Mathematica | 230520T175933Z | lesobrod |
| 107 | Ruby | 210601T094932Z | G B |
| 124 | JavaScript ES6 | 210531T221301Z | Arnauld |
| 065 | J | 210601T043721Z | Jonah |
| 012 | Brachylog | 210531T224118Z | Unrelate |
| 012 | 05AB1E | 210531T202554Z | ovs |
| 013 | Jelly | 210531T191713Z | caird co |
Scala, 773 372 bytes
372 bytes
Golfed version. Try it online!
l=>{@tailrec def f(x:Int):Option[List[List[Int]]]=l.permutations.collectFirst{case p if p.foldRight(List[List[Int]]()){case(z,a)=>if(a.isEmpty||a.head.sum+z>x)List(z)::a else(z::a.head)::a.tail}.forall(_.sum==x)=>p}match{case Some(p)=>Some(p.foldRight(List[List[Int]]()){case(z,a)=>if(a.isEmpty||a.head.sum+z>x)List(z)::a else(z::a.head)::a.tail});case None=>f(x+1)};f(1)}
Ungolfed version. Try it online!
import scala.annotation.tailrec
object Main {
def main(args: Array[String]): Unit = {
println(findX(List(9, 5, 1, 2, 9, 2)))
println(findX(List(1, 1, 3, 5, 7, 4)))
println(findX(List(2, 9, 6, 1, 5, 8, 2)))
println(findX(List(2, 2, 2)))
println(findX(List(2, 4, 5)))
}
def findX(list: List[Int]): Option[List[List[Int]]] = {
@tailrec
def findXRec(x: Int): Option[List[List[Int]]] = {
val permutations = list.permutations
val validPartition = permutations.collectFirst {
case perm if {
var w = -1
val chunks = perm.foldRight(List.empty[List[Int]]) {
case (z, acc) =>
if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc
else (z :: acc.head) :: acc.tail
}
chunks.forall(_.sum == x)
} => perm
}
validPartition match {
case Some(perm) => {
var w = -1
Some(perm.foldRight(List.empty[List[Int]]) {
case (z, acc) =>
if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc
else (z :: acc.head) :: acc.tail
})
}
case None => findXRec(x + 1)
}
}
findXRec(1)
}
}
Julia 1.7 + Combinatorics, 74 bytes
using Combinatorics
~x=argmin(p->keys(sum.(p)∪0)=>sum.(p),partitions(x))
argmin(f, itr) needs julia 1.7 or later
Nekomata, 10 bytes
O:ᵐ∑≡$Ðaṁl
O:ᵐ∑≡$Ðaṁl
O Non-deterministically choose a set partition of the input
: Duplicate
ᵐ∑ Sum each
≡ Check if all sums are equal, and get the equal value
$Ð Pair the sum with the partition
a Get all possible values
ṁ Minimum (by the sum)
l Take the last element (the partition)
Wolfram Language (Mathematica), 145 bytes
(l=Length@#;Catch[Do[If[SameQ@@Total/@(t=TakeList[p,i]),Throw@t],{d,Reverse@Divisors@Total@#},{i,IntegerPartitions[l,{d}]},{p,Permutations@#}]])&
Rough compromise between speed/memory optimization and code-golf.
The following facts are used:
- Array can only be splitted by the number of parts that are dividing its sum
- The lengths of parts of any split must be integer partition of length of array
Of course, one can optimize the search much better (for example, the dividers of the sum of the array must be less than its length), but it lengthens the code. On the other hand, I don’t want to take away given optimization, because it reduces runtime significantly.
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}
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
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)
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
J, 65 bytes
<@/:~((i.~/:~@;&.>)>@{])[:(\:#&>)@,@(g/.~+/&>)g=:<@#~"#.2#:@i.@^#
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 asgso 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│ └───┴───┘
Brachylog, 12 bytes
∧≜S&p~c.+ᵛS∧
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.
05AB1E, 12 bytes
œ€.œ€`éR.ΔOË
œ # 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
Jelly, 13 bytes
Œ!ŒṖ€Ẏ§E$ƇLÐṀ
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