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
  • 3
    \$\begingroup\$ Related? codegolf.stackexchange.com/questions/172824/… \$\endgroup\$ – Sumner18 Jan 17 at 20:47
  • 1
    \$\begingroup\$ Also some people might want to try openprocessing.org/sketch/580366 made by a youtuber called carykh. It is called "loopover" \$\endgroup\$ – Gareth Ma Jan 20 at 2:57
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 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)[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: 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
        u+=[(copy(p),s+f'v{v}',f':,{v}')    #add p,↓v to queue
            for v in r_[: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)

\$\endgroup\$
0
\$\begingroup\$

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.

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