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!
[a..b]
includesa
and excludesb
, correct? \$\endgroup\$ – Alex A. Mar 27 '16 at 17:21