10
In this challenge, you need to partition a list, where partitions have a max size, a min size, and a preferred size. I'll be using the notation (min,pref,max)
to indicate the sizes in this challenge.
For those unfamiliar with partitioning, the following list has been partitioned into parts of 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]
When the list is not evenly divisible, you need the partitions to be as close to the preferred size as possible: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]
. This partitioning is preferable to [[0,1,2,3],[4,5,6,7],[8,9]]
, even though the latter has more of the preferred length. Formally, we need to minimize the sum of (partitionLength-preferredSize)^2
for each partition.
The order of the partition lengths does not matter: For [0..5], (2,3,3)
, either [[0,1,2],[3,4]]
or [[0,1],[2,3,4]]
works. If no partition is possible, return an empty array: [0..7], (4,4,5) -> []
.
You can assume that 1<=min<=pref<=max
, and that the array passed to you is a non-empty array of integers. The array will always be the first argument. You can accept min, max, and pref in any order and as a tuple or as separate arguments.
Your program must run under a couple of seconds. Basically, iterating through every possible partition size within the bounds is not allowed.
Test cases:
[1], (1,3,4) -> [[1]]
[100], (1,2,3) -> [[100]]
[1,2], (1,1,2) -> [[1],[2]]
[1,2], (1,2,2) -> [[1,2]]
[1,2], (1,3,3) -> [[1,2]]
[1,2,3], (1,2,3) -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4) -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49], (2,6,6) -> [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24],[25,26,27,28,29],[30,31,32,33,34],[35,36,37,38,39],[40,41,42,43,44],[45,46,47,48,49]]
This is a code-golf, so aim for as few bytes as possible in your favorite language!
The notation you're using of
[a..b]
includesa
and excludesb
, correct? – Alex A. – 2016-03-27T17:21:26.253A inclusive, B exclusive. – Nathan Merrill – 2016-03-27T18:32:49.700
Note that your interpretation of a is not the same as a partition from set theory...
– agtoever – 2016-03-27T20:53:04.827But it is effectively equivalent to integer partitioning. – Nathan Merrill – 2016-03-27T21:02:29.173
What if there is no solution? – feersum – 2016-03-27T21:23:29.993
"If no partition is possible, return an empty array" – Nathan Merrill – 2016-03-27T21:51:18.867