12
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Here's a website where you can solve these puzzles yourself. \$\endgroup\$ – Doorknob Jan 17 at 17:25
  • 1
    \$\begingroup\$ @Doorknob That would have been useful when I was writing the challenge Dx. Thanks anyway! \$\endgroup\$ – Luis felipe De jesus Munoz Jan 17 at 17:26
  • \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Jan 17 at 19:16
  • \$\begingroup\$ @FryAmTheEggman Yes, It doesnt matter how long your solution (output) is as long as it creates the correct result \$\endgroup\$ – Luis felipe De jesus Munoz Jan 17 at 19:18
  • 3
    \$\begingroup\$ Related? codegolf.stackexchange.com/questions/172824/… \$\endgroup\$ – Sumner18 Jan 17 at 20:47
3
\$\begingroup\$

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[0][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[0][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[0])
            ) && 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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Jonah Jan 26 at 3:04
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$ – Arnauld Jan 26 at 10:20
  • \$\begingroup\$ Wow, thank you @Arnauld \$\endgroup\$ – Jonah Jan 26 at 15:29
2
\$\begingroup\$

Python 2, 296 277 245 Python 3, 200 bytes

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

Try it online!

-19: apparently I failed to notice that 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)


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

These moves are sufficient to find every solution, 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.


from numpy import*
def f(p):
    s=''                                    #s: sequence of moves, as string
    u=[]                                    #u: queue of states to check
    while any(diff(ravel(p))<0):            #while p is not sorted
        u+=[(copy(p),s+f'v{v}',f':,{v}')    #add p,↓v to queue
            for v in range(shape(p)[1])]    # for all 0<=v<#columns
        u+=[(p,s+'>0',0)]                   #add p,→0
        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)

Can I assume a numpy array as input? That could save a couple more bytes.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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