20
\$\begingroup\$

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, a 5x4 or 4x5 output matrix is required, and not a 2x10).
  • 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 so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Oh, wow, a word I haven't seen since Linear Algebra; easily overlooked. My apologies. \$\endgroup\$ Feb 16, 2018 at 17:37
  • \$\begingroup\$ @LuisMendo Added a 15 element test case. \$\endgroup\$ Feb 16, 2018 at 19:04

10 Answers 10

10
\$\begingroup\$

Jelly, 24 22 20 bytes

pS€ỤỤs
LÆDżṚ$SÞḢç/ịṢ

Try it online!

Saved 2 bytes thanks to @Jonathan Allan.

Explanation

pS€ỤỤs  Helper link. Input: integer a (LHS), integer b (RHS)
p       Cartesian product between [1, 2, ..., a] and [1, 2, ..., b]
 S€     Sum each pair
   Ụ    Grade up
    Ụ   Grade up again (Obtains the rank)
     s  Split into slices of length b

LÆDżṚ$SÞḢç/ịṢ  Main link. Input: list A
L              Length
 ÆD            Divisors
     $         Monadic pair
    Ṛ            Reverse
   ż             Interleave
                 Now contains all pairs [a, b] where a*b = len(A)
      SÞ       Sort by sum
        Ḣ      Head (Select the pair with smallest sum)
         ç/    Call helper link
            Ṣ  Sort A
           ị   Index into sorted(A)
\$\endgroup\$
2
  • \$\begingroup\$ L%J¬TżṚ$ -> LÆDżṚ$ should save two I think \$\endgroup\$ Feb 16, 2018 at 19:18
  • \$\begingroup\$ The first link can become pSÞỤs. \$\endgroup\$
    – Dennis
    Apr 24, 2018 at 16:42
4
\$\begingroup\$

Python 2, 160 158 153 151 bytes

-2 bytes thanks to Erik the Outgolfer
-2 bytes thanks to Mr. Xcoder

s=sorted(input())
l=len(s)
x=int(l**.5)
while l%x:x+=1
n=1
o=eval(`l/x*[[]]`)
while s:
 for i in range(l/x)[max(0,n-x):n]:o[i]+=s.pop(0),
 n+=1
print o

Try it online! or Try all test cases

\$\endgroup\$
1
  • \$\begingroup\$ I belive you can use max(0,n-x) for -2 bytes. \$\endgroup\$
    – Mr. Xcoder
    Feb 16, 2018 at 17:32
4
\$\begingroup\$

R 110 95 bytes

function(x){n=sum(x|1)
X=matrix(x,max(which(!n%%1:n^.5)))
X[order(col(X)+row(X))]=sort(x)
t(X)}

Try it online!

How it works

f <- function(x) {
  n <- sum(x|1)                           # length
  p <- max(which(!n%%1:n^.5))             # height of matrix
  X <- matrix(x, p)                       # initialize matrix
  X[order(col(X) + row(X))] <- sort(x)    # filling the matrix using position distance to the top left corner
  t(X)                                    # probably required by OP
}

Giuseppe saved a whopping 15(!) bytes by the following tricks

  • replacing length(x) by sum(x|1) (-1 byte)
  • floor() is not required as : rounds down anyway (-7)
  • ^.5 is shorter than sqrt() (-3)
  • using col(X) + row(X) instead of outer (nice!)
  • could not get rid of the t(X) though - disappointing ;)

Original solution

function(x){
n=length(x)
p=max(which(!n%%1:floor(sqrt(n))))
X=outer(1:p,1:(n/p),`+`)
X[order(X)]=sort(x)
t(X)}

It would look more fancy with outer being replaced by row(X)+col(X), but that would require to initialize the output matrix X first.

Try it online!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Very nice! You can get down to 95 bytes \$\endgroup\$
    – Giuseppe
    Feb 17, 2018 at 2:10
  • 1
    \$\begingroup\$ Might be able to use something from my solution to a related challenge to help here as well. \$\endgroup\$
    – Giuseppe
    Apr 25, 2018 at 11:29
  • \$\begingroup\$ It is indeed closely related. Very nice approach! \$\endgroup\$
    – Michael M
    Apr 25, 2018 at 11:53
3
\$\begingroup\$

JavaScript (ES6), 172 bytes

l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r)

Explanation

l=>(                                // Take a list l as input
 l.sort((a,b)=>b-a),                // Sort it
 n=l.length,                        // Get the length n
 w=l.findIndex((_,i)=>!(i*i<n|n%i)),// Find the first integer w where w >= √n and n % w = 0
 a=l=>[...Array(l)],                // Helper function a
 r=a(n/w).map(_=>a(w)),             // Create the grid r of size w, n/w
 a(w+n/w).map((_,x)=>               // For every x from 0 to w + n/w:
  r.map((s,y)=>                     //  For every row s in r:
   x-y in s&&(                      //   If the index x-y is in s:
    s[x-y]=l.pop()))),              //    Set s[x-y] to the next element of l
 r)                                 // Return r

Test Cases

f=l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r)

l=m=>console.log(JSON.stringify(m))

l(f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]))
l(f([3,5,12,9,6,11]))
l(f([14,20,200,33,12,1,7,99,58]))
l(f([1,2,3,4,5,6,7,8,9,10]))

\$\endgroup\$
3
\$\begingroup\$

Perl 5, 132 bytes

sub d{$,=0|sqrt(@_=sort{$a-$b}@_);--$,while@_%$,;map{$r++,$c--for@_/$,..$c;$a[$r++][$c--]=$_;$c=++$i,$r=0if$r<0||$c<0||$r>=$,}@_;@a}

Try it online!

Subroutine returns a 2-D array. TIO link includes footer code for displaying test result.

\$\endgroup\$
3
\$\begingroup\$

Octave, 151 bytes

function f(v)n=floor(sqrt(l=nnz(v)));while i=mod(l,n);++n;end;A=nan(m=l/n,n);for k=[1:m 2*m:m:l];do A(k)=sort(v)(++i);until~mod(k+=m-1,m)|k>l;end;A'end

Using three different kinds of loop constructs.

Try it online!

Unrolled:

function f(v)
    n = floor(sqrt(l=nnz(v)));

    while i = mod(l,n);
        ++n;
    end;

    A = nan(m=l/n, n);

    for k = [1:m 2*m:m:l];
        do
            A(k) = sort(v)(++i);
        until ~mod(k+=m-1, m) | k>l;
    end;

    A'
end
\$\endgroup\$
7
  • \$\begingroup\$ Nice answer! Why is the ' in nnz(v') required? \$\endgroup\$
    – Luis Mendo
    Feb 18, 2018 at 4:34
  • 1
    \$\begingroup\$ @LuisMendo Thanks! Turns out the ' is not required if I wrap the range expression, e.g. 1:20, around brackets ([1:20]) at the call site (to make it an actual vector). Apparently in Octave, the colon operator doesn't create a vector, but a range constant that takes much less space in memory. For some reason, nnz() doesn't work with that type, but transposing the range constant yields a vector, so it works with the apostrophe. Calling the function with an actual vector removes the need for the '. \$\endgroup\$
    – Steadybox
    Feb 18, 2018 at 13:06
  • 1
    \$\begingroup\$ Thanks for the explanation. I didn't know that a range expression had that special treatment in Octave. Anyway, the fact that it doesn't create a vector for memory efficiency should be transparent to the programmer. That is, the fact that nnz(1:20) doesn't work is probably a bug (max(1:20), sum(1:20) etc are valid). \$\endgroup\$
    – Luis Mendo
    Feb 18, 2018 at 16:38
  • 1
    \$\begingroup\$ We should report it. It might affect other functions than nnz . Do you want to do it yourself, or shall I? \$\endgroup\$
    – Luis Mendo
    Feb 18, 2018 at 18:06
  • 1
    \$\begingroup\$ Reported. It also affected MATL; now solved. Thanks for noticing this! \$\endgroup\$
    – Luis Mendo
    Feb 18, 2018 at 18:44
0
\$\begingroup\$

Husk, 15 bytes

ḟȯΛ≤Σ∂MCP¹→←½ḊL

This works by brute force, so longer test cases may time out. Try it online!

Explanation

ḟȯΛ≤Σ∂MCP¹→←½ḊL  Implicit input, a list of integers x.
              L  Length of x (call it n).
             Ḋ   List of divisors.
            ½    Split at the middle.
          →←     Take last element of first part.
                 This is a divisor d that minimizes d + n/d.
        P¹       List of permutations of x.
      MC         Cut each into slices of length d.
ḟ                Find the first of these matrices that satisfies this:
     ∂            Take anti-diagonals,
    Σ             flatten them,
 ȯΛ≤              check that the result is sorted (each adjacent pair is non-decreasing).
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 233 bytes

f=s=>{l=s.length;i=Math.sqrt(l)|0;for(;l%++i;);p=(x)=>(x/i|0+x%i)*l+x%i;m=[...Array(l).keys()].sort((x,y)=>p(x)-p(y));return s.sort((a,b)=>a-b).map((x,i)=>m.indexOf(i)).reduce((a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a,[])}

Explanation

f=s=>{                         // Take array `s` of numbers as input
  l=s.length                   // short-hand for length
  i=Math.sqrt(l)|0             // = Math.floor(Math.sqrt(l))
  for(;l%++i;);                // i = width           
  j=l/i                        // j = height

  p=(x)=>(x/i|0+x%i)*l+x%i     // helper to calculate (sort-of) ~manhattan
                                 // distance (horizontal distance weighted
                                 // slightly stronger), from top-left corner
                                 // to the number x, if numbers 0,...,l are
                                 // arranged left-to-right, top-to-bottom
                                 // in an l=i*j grid

  m=[...Array(l).keys()]         // range array
  .sort((x,y)=>p(x)-p(y)),       // manhatten-sorted, sort-of...

  return s.sort((a,b)=>a-b)      // sort input array by numbers,
    .map((x,i,w)=>w[m.indexOf(i)])    // then apply inverse permutation of the
                                 // range-grid manhatten-sort mapping.
    .reduce(                     // slice result into rows
      (a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a
      ,[]
     )
}
\$\endgroup\$
0
\$\begingroup\$

Java 10, 199 188 186 bytes

a->{int j=a.length,m=0,n,i=0,k=0;for(n=m+=Math.sqrt(j);m*n<j;n=j/++m);var R=new int[m][n];for(java.util.Arrays.sort(a);i<m+n;i++)for(j=0;j<=i;j++)if(i-j<n&j<m)R[j][i-j]=a[k++];return R;}

Try it online.

Based on my answer here.

Explanation:

a->{                        // Method with int-array parameter and int-matrix return-type
  int j=a.length,           //  Length of the input-array
      m=0,n,                //  Amount of rows and columns
      i=0,k=0;              //  Index integers
   for(n=m+=Math.sqrt(j);   //  Set both `m` and `n` to floor(√ `j`)
       m*n<j;               //  Loop as long as `m` multiplied by `n` is not `j`
       n=j/++m);            //   Increase `m` by 1 first with `++m`
                            //   and then set `n` to `j` integer-divided by this new `m`
   var R=new int[m][n];     //  Result-matrix of size `m` by `n`
   for(java.util.Arrays.sort(a);
                            //  Sort the input-array
       i<m+n;)              //  Loop as long as `i` is smaller than `m+n`
     for(j=0;j<=i;j++)      //   Inner loop `j` in range [0,`i`]
       if(i-j<n&j<m)        //    If `i-j` is smaller than `n`, and `j` smaller than `m`
                            //    (So basically check if they are still within bounds)
         R[j][i-j]=a[k++];  //     Add the number of the input array at index `k`,
                            //     to the matrix in the current cell at `[j,i-j]`
  return R;}                //  Return the result-matrix
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 269 253 226 bytes

j,w,h,x,y;c(int*a,int*b){a=*a-*b;}f(A,l)int*A;{int B[l];qsort(A,l,4,c);for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}

Try it online!


C (gcc), 214 bytes, using -zexecstack-lambdas

  • Thanks to ceilingcat for this hackier, yet slimmer version.
j,w,h,x,y;f(A,l)int*A;{int B[l];qsort(A,l,4,L"\x62b078bǃ");for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ May 24, 2020 at 22:47
  • \$\begingroup\$ @ceilingcat Thank you. I assume you implemented a 'lambda' -- giving qsort a function pointer disguised as a wide-character string? Whilst I appreciate the solution, I added it as an addendum as I feel it is a tad too briddle to qualify as generic 'C'. \$\endgroup\$ May 26, 2020 at 0:41
  • \$\begingroup\$ no "lambda" 225 bytes \$\endgroup\$
    – ceilingcat
    May 26, 2020 at 1:31
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ May 26, 2020 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.