Given an unsorted list of unique strictly positive integers, minimally sort it into a 2D matrix. The input list is guaranteed to be of composite length, which means the output matrix is not necessarily square, but is of size n x m
with n,m > 1
.
"Minimally sort" here means the following:
- Sort the list in ascending order.
- Compact the output matrix as much as possible -- minimize the sum of the dimensions of the matrix (for example, for
20
input elements as input, a5x4
or4x5
output matrix is required, and not a2x10
). - Compact the sorted numbers as far to the upper-left of the matrix as possible, starting with the first element in the sorted list.
- This can be thought of as sorting the list, then slicing it along the matrix's anti-diagonals, starting with the upper-left.
Examples:
For input 1..20
output is either a 5x4 or a 4x5 matrix as follows:
1 2 4 7 11
3 5 8 12 15
6 9 13 16 18
10 14 17 19 20
1 2 4 7
3 5 8 11
6 9 12 15
10 13 16 18
14 17 19 20
For input [3, 5, 12, 9, 6, 11]
output is a 2x3 or 3x2 as follows
3 5 9
6 11 12
3 5
6 9
11 12
For input [14, 20, 200, 33, 12, 1, 7, 99, 58]
, output is a 3x3 as follows
1 7 14
12 20 58
33 99 200
For input 1..10
the output should be a 2x5 or 5x2 as follows
1 2 4 6 8
3 5 7 9 10
1 2
3 4
5 6
7 8
9 10
For input [5, 9, 33, 65, 12, 7, 80, 42, 48, 30, 11, 57, 69, 92, 91]
output is a 5x3 or 3x5 as follows
5 7 11 33 57
9 12 42 65 80
30 48 69 91 92
5 7 11
9 12 33
30 42 57
48 65 80
69 91 92
Rules
- The input can be assumed to fit in your language's native integer type.
- The input and output can be given by any convenient method.
- Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
- Standard loopholes are forbidden.
- This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
15
element test case. \$\endgroup\$