The idea for this code-challenge is simple: given a matrix of integers, let's sort it by applying Rubik-style movements. This means that you can select a single row or column and rotate its elements in any direction:
[1, 3, 2, 4] => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4] => [4, 1, 3, 2] (rotate right for rows/down for columns)
So, given a matrix of integers of any dimension, sort its elements applying only these Rubik-style transformations. A matrix
$$ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} $$
will be considered sorted iff its elements comply with the following restriction:
$$ a_{11} \leq a_{12} \leq a_{13} \leq a_{14} \leq a_{21} \leq a_{22} \leq a_{23} \leq a_{24} \leq a_{31} \leq a_{32} \leq a_{33} \leq a_{34} $$
I/O
- Input will be a matrix of positive integers with no repeated values.
- Output will be the movements needed to sort it. As this is not a code golf challenge and you don't need to worry about its length, the proposed format for every movement is
#[UDLR]
where#
is the number of the row or column to move (0-indexed) and[UDLR]
is a single character in that range that specifies if the movement is Up/Down (for columns) or Left/Right (for rows). So1U
would mean "move the 1-th column upwards" but1R
would be "move the 1-th row rightwards". Movements will be comma-separated, so a solution will be expressed like this:1R,1U,0L,2D
.
Scoring
Trying to sort a matrix this way can be costly as there are a lot of possible combinations of moves, and there are also a lot of possible lists of moves that can sort it, so the goal is to write some code that sorts the N*N matrices below. The score will be the greatest size N that you can solve in a reasonable amount of time1 without errors (the greater the size of the matrix solved, the better). In case of a tie, the tie-breaker will be the number of movements in your found path (the shorter the path, the better).
Example: if a user A finds a solution for N=5 and B finds a solution for N=6, B wins regardless of the length of both paths. If they both find solutions for N=6 but the solution found by A has 50 steps and B's solution has 60 steps, A wins.
Explanations on how your code works are highly encouraged and please post the solutions found so we can test them. You can use Pastebin or similar tools if the solutions are too big. Also, an estimation of the time spent by your code to find your solutions will be appreciated.
Test cases
The following matrices (Pastebin link for a more copy-pasteable version) have been created starting from already sorted matrices by scrambling them with 10K random, Rubik-style movements:
\begin{bmatrix} 8 & 5 & 6 \\ 11 & 10 & 1 \\ 3 & 15 & 13 \\ \end{bmatrix} \begin{bmatrix} 21 & 10 & 12 & 16 \\ 17 & 6 & 22 & 14 \\ 8 & 5 & 19 & 26 \\ 13 & 24 & 3 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 13 & 8 & 16 & 5 \\ 9 & 40 & 21 & 26 & 22 \\ 11 & 24 & 14 & 39 & 28 \\ 32 & 19 & 37 & 3 & 10 \\ 30 & 17 & 36 & 7 & 34 \\ \end{bmatrix} \begin{bmatrix} 34 & 21 & 40 & 22 & 35 & 41 \\ 18 & 33 & 31 & 30 & 12 & 43 \\ 19 & 11 & 39 & 24 & 28 & 23 \\ 44 & 1 & 36 & 5 & 38 & 45 \\ 14 & 17 & 9 & 16 & 13 & 26 \\ 8 & 3 & 47 & 6 & 25 & 4 \\ \end{bmatrix} \begin{bmatrix} 20 & 36 & 17 & 1 & 15 & 50 & 18 \\ 72 & 67 & 34 & 10 & 32 & 3 & 55 \\ 42 & 43 & 9 & 6 & 30 & 61 & 39 \\ 28 & 41 & 54 & 27 & 23 & 5 & 70 \\ 48 & 13 & 25 & 12 & 46 & 58 & 63 \\ 52 & 37 & 8 & 45 & 33 & 14 & 68 \\ 59 & 65 & 56 & 73 & 60 & 64 & 22 \\ \end{bmatrix} \begin{bmatrix} 85 & 56 & 52 & 75 & 89 & 44 & 41 & 68 \\ 27 & 15 & 87 & 91 & 32 & 37 & 39 & 73 \\ 6 & 7 & 64 & 19 & 99 & 78 & 46 & 16 \\ 42 & 21 & 63 & 100 & 4 & 1 & 72 & 13 \\ 11 & 97 & 30 & 93 & 28 & 40 & 3 & 36 \\ 50 & 70 & 25 & 80 & 58 & 9 & 60 & 84 \\ 54 & 96 & 17 & 29 & 43 & 34 & 23 & 35 \\ 77 & 61 & 82 & 48 & 2 & 94 & 38 & 66 \\ \end{bmatrix} \begin{bmatrix} 56 & 79 & 90 & 61 & 71 & 122 & 110 & 31 & 55 \\ 11 & 44 & 28 & 4 & 85 & 1 & 30 & 6 & 18 \\ 84 & 43 & 38 & 66 & 113 & 24 & 96 & 20 & 102 \\ 75 & 68 & 5 & 88 & 80 & 98 & 35 & 100 & 77 \\ 13 & 21 & 64 & 108 & 10 & 60 & 114 & 40 & 23 \\ 47 & 2 & 73 & 106 & 82 & 32 & 120 & 26 & 36 \\ 53 & 93 & 69 & 104 & 54 & 19 & 111 & 117 & 62 \\ 17 & 27 & 8 & 87 & 33 & 49 & 15 & 58 & 116 \\ 95 & 112 & 57 & 118 & 91 & 51 & 42 & 65 & 45 \\ \end{bmatrix}
Plaintext Test Cases:
[[8, 5, 6], [11, 10, 1], [3, 15, 13]]
[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]
[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]
[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]
[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]
[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]
[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]
Please ask for more if you solve them all. :-) And many thanks to the people who helped me refine this challenge while in the sandbox.
1 A reasonable amount of time: any amount of time that doesn't undermine our patience while testing your solution. Note that TIO only runs code for 60 seconds, any amount of time over that limit will make us test the code in our machines. Example: my rather inefficient algorithm takes a few milliseconds to solve matrices of order 3x3 and 4x4, but I have just tested it with a 5x5 matrix and it took 317 seconds to solve it (in over 5 million movements, very funny if we consider that the matrix to solve was scrambled only 10K times). I tried to reduce the number of movements to less than 10K but I surrendered after 30 minutes executing the code.
O(input size)
then? For a 5x5 matrix it wouldO(25)
? That seems to be extremely fast, so I would be very interested to see that algorithm or implementation of yours. EDIT: You do realize we input the 'scrambled' matrix and output the movements, right? Not the other way around. \$\endgroup\$