# Matrix rotation sort

Lets define a non-empty, unsorted and finite matrix with unique numbers as follow: $$N = \begin{Bmatrix} 4&5&7\\1&3&6 \end{Bmatrix}$$

Lets define 4 matrix moves as:

• ↑* (up): Moves a column up
• ↓* (down): Moves a column down
• →* (right): Moves a row to the right
• ←* (left): Moves a row to the left

The asterisk(*) represents the column/row that is affected by the move (It can be 0-indexed or 1-indexed. Up to you. Please state which one in your answer).

The challenge is, using above moves, sort the matrix in a ascendant order (being the top left corner the lowest and the bottom right corner the highest).

Example

Input: $$N=\begin{Bmatrix}4&2&3\\1&5&6 \end{Bmatrix}$$ Possible Output: ↑0 or ↓0. (Notice any of those moves can sort the matrix so both answer are correct)

Input: $$N=\begin{Bmatrix}2&3&1\\4&5&6 \end{Bmatrix}$$ Possible Output: →0

Input (Example test case): $$N = \begin{Bmatrix} 4&5&7\\1&3&6 \end{Bmatrix}$$ Possible Output: ↑0↑1←1↑2

Input: $$N = \begin{Bmatrix} 5&9&6\\ 8&2&4\\ 1&7&3 \end{Bmatrix}$$ Possible Output: ↑0↑2→0→2↑0→2↑1↑2←1

Input: $$N = \begin{Bmatrix} 1 & 27 & 28 & 29 & 6 \\10 & 2 & 3 & 4 & 5 \\17 & 7 & 8 & 13 & 9 \\15 & 11 & 12 & 18 & 14 \\26 & 16 & 21 & 19 & 20 \\30 & 22 & 23 & 24 & 25 \end{Bmatrix}$$ Possible Output: ↑2↑1←3→0←3↓0←0←2→3↑3↑4

Input: $$N = \begin{Bmatrix} 1 \end{Bmatrix}$$ Output: or any move

Input: $$N = \begin{Bmatrix} 1&2\\3&4 \end{Bmatrix}$$ Output:

Notes

• There can be different correct outputs (there don't need to be necessarily the same as the test cases or the shortest one)
• You can assume it will be always a way to order the matrix
• Edges connects (like pacman :v)
• There wont be a matrix with more than 9 columns or/and rows
• Assume matrix contains only positive non-zero unique integers
• You can use any 4 distinct values other than numbers to represent the moves (in case of that, please state that in your answer)
• Column/row can be 0 or 1 indexed
• Winning criteria

Extra test cases are always welcome

• Here's a website where you can solve these puzzles yourself. – Doorknob Jan 17 '19 at 17:25
• @Doorknob That would have been useful when I was writing the challenge Dx. Thanks anyway! – Luis felipe De jesus Munoz Jan 17 '19 at 17:26
• I don't think you say anywhere that the solution given has to be as short as possible. Is that intentional? For example is ←0←0 a valid solution for the second example where you have given a solution as →0. If it is, I think half of the move options likely won't be used. – FryAmTheEggman Jan 17 '19 at 19:16
• – Sumner18 Jan 17 '19 at 20:47
• Also some people might want to try openprocessing.org/sketch/580366 made by a youtuber called carykh. It is called "loopover" – Gareth Ma Jan 20 '19 at 2:57

# JavaScript (ES6),  226  219 bytes

Brute force search, using right ("R") and down ("D") moves.

Returns either a string describing the moves, or an empty array if the input matrix is already sorted. Columns and rows in the output are 0-indexed.

f=(m,M=2)=>(g=(s,m)=>m[S='some'](p=r=>r[S](x=>p>(p=x)))?!s[M]&&m[S]((_,x,a)=>g(s+'D'+x,m.map(([...r],y)=>(r[x]=(m[y+1]||a)[x])&&r)))|m[S]((_,y)=>g(s+'R'+y,m.map(([...r])=>y--?r:[r.pop(),...r]))):o=s)([],m)?o:f(m,M+2)


Try it online!

### Commented

f =                              // f = main recursive function taking:
(m, M = 2) => (                  //   m[] = input matrix; M = maximum length of the solution
g =                            // g = recursive solver taking:
(s, m) =>                      //   s = solution, m[] = current matrix
m[S = 'some'](p =            // we first test whether m[] is sorted
r =>                       // by iterating on each row
r[S](x =>                // and each column
p > (p = x)            // and comparing each cell x with the previous cell p
)                        //
) ?                          // if the matrix is not sorted:
!s[M] &&                   //   if we haven't reached the maximum length:
m[S]((_, x, a) =>       //     try all 'down' moves:
g(                       //       do a recursive call:
s + 'D' + x,           //         append the move to s
m.map(([...r], y) =>   //         for each row r[] at position y:
(r[x] =              //           rotate the column x by replacing r[x] with
(m[y + 1] || a)[x] //           m[y + 1][x] or a[x] for the last row (a = m)
) && r               //           yield the updated row
))) |                      //
m[S]((_, y) =>             //     try all 'right' moves:
g(                       //       do a recursive call:
s + 'R' + y,           //         append the move to s
m.map(([...r]) =>      //         for each row:
y-- ?                //           if this is not the row we're looking for:
r                  //             leave it unchanged
:                    //           else:
[r.pop(), ...r]    //             rotate it to the right
)))                        //
:                            // else (the matrix is sorted):
o = s                      //   store the solution in o
)([], m) ?                       // initial call to g(); if we have a solution:
o                              //   return it
:                                // else:
f(m, M + 2)                    //   try again with a larger maximum length

• Nice answer. Do you know if there exists an efficient algo for this, or if it's possible to determine the maximum number of moves a solution can have without brute forcing? – Jonah Jan 26 '19 at 3:04
• @Jonah Here is a paper describing a solution and giving an upper bound of the number of moves. (See also this challenge which is basically the same task with a different winning criterion.) – Arnauld Jan 26 '19 at 10:20
• Wow, thank you @Arnauld – Jonah Jan 26 '19 at 15:29

# Python 2, 296 277 245Python 3, 200 194 bytes

from numpy import*
def f(p):
s='';u=[]
while any(ediff1d(p)<0):u+=[(copy(p),s+f'v{v}',f':,{v}')for v in r_[:shape(p)]]+[(p,s+'>0',0)];p,s,i=u.pop(0);exec(f'p[{i}]=roll(p[{i}],1)')
return s


Try it online!

-19: unicode arrows weren't required...
-32: slightly reworked, but much slower performance on average.
-45: took some inspiration from @Arnauld's answer. Switched to Python 3 for f'' (-4 bytes)
-6: range( )r_[: ], diff(ravel( ))ediff1d( )

Exhaustively searches combinations of all possible ↓ moves and →0. Times out on the third test case.

Since →n is equivalent to

↓0↓1...↓(c-1) 	... repeated r-n times
→0
↓0↓1...↓(c-1)	... repeated n times


where r and c are the numbers of rows and columns, these moves are sufficient to find every solution.

from numpy import*
def f(p):
s=''                                    #s: sequence of moves, as string
u=[]                                    #u: queue of states to check
while any(ediff1d(p)<0):                #while p is not sorted
for v in r_[:shape(p)]]      # for all 0<=v<#columns
p,s,i=u.pop(0)                      #get the first item of queue
exec(f'p[{i}]=roll(p[{i}],1)')      #transform it
return s                                #return the moves taken


>v correspond respectively to →↓. (others undefined)

# Jelly, 35 bytes

ṙ€LXȮƊ¦1
ÇZÇZƊ⁾ULXȮOịØ.¤?F⁻Ṣ¿,“”Ṫ


Try it online!

Full program. Outputs moves to STDOUT using L for left and R for right. Keeps trying random moves until the matrix is sorted, so not very efficient in terms of speed or algorithmic complexity.