10
\$\begingroup\$

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 , so aim for as few bytes as possible in your favorite language!

\$\endgroup\$
  • \$\begingroup\$ The notation you're using of [a..b] includes a and excludes b, correct? \$\endgroup\$ – Alex A. Mar 27 '16 at 17:21
  • \$\begingroup\$ A inclusive, B exclusive. \$\endgroup\$ – Nathan Merrill Mar 27 '16 at 18:32
  • \$\begingroup\$ Note that your interpretation of a is not the same as a partition from set theory... \$\endgroup\$ – agtoever Mar 27 '16 at 20:53
  • \$\begingroup\$ But it is effectively equivalent to integer partitioning. \$\endgroup\$ – Nathan Merrill Mar 27 '16 at 21:02
  • \$\begingroup\$ What if there is no solution? \$\endgroup\$ – feersum Mar 27 '16 at 21:23
2
\$\begingroup\$

Haskell, 152

_%0=[]
s%k|(a,b)<-splitAt(div(z s)k)s=a:b%(k-1)
z=length
f s n p x=snd$minimum$(z s*p^2,[]):[(sum[(z x-p)^2|x<-s%k],s%k)|k<-[-div(-z s)x..div(z s)n]]

In any partition, if there are two lists which have lengths that differ by two or more, it will always be beneficial to shrink the bigger list and enlarge the smaller list. therefore, we only need to consider partitions with only two list sizes, which simplifies the computation.

the program then runs on all the possible amounts of lists in the partition. given the amount of lists in the partition, the score is uniquely determined. the program computes a fitting partition, and its score.

then it finds the overall minimum, and returns it.

Usage: input like f [1,2,3,4,5] 1 3 4 (f is the function that solves the challenge)

Although it is possible to computing the best option completely numerically and only then partitioning the list accordingly, it took too many bytes. however, my last version of this approach is:

_%0=[]
s%k|(a,b)<-splitAt(div(length s)k)s=a:b%(k-1)
f s n p x|l<-length s=(s%)$snd$minimum$(l*p^2,0):[(k*j^2+mod l k*(1-2*j),k)|k<-[1..div l n],k*x>=l,j<-[p-div l k]]
\$\endgroup\$
1
\$\begingroup\$

CJam, 70

q~:S;_,[0L]a{_S2=e<),S0=>f{[__S1=-_*\]@@-j.+}[esL]a+:e<}j1={/(\e_}/;]p

Try it online

The code finds an optimal sequence of partition sizes based on the list size, using dynamic programming (via memoized recursion), then goes ahead and partitions the list.

\$\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.