18
\$\begingroup\$

The idea for this 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). So 1U would mean "move the 1-th column upwards" but 1R 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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Nice challenge! However, I have a few requests/questions: 1) Could you provide the test cases in a more copy-paste friendly format? (such as pastebin) 2) Could you provide a more precise definition of the time limit order? 3) Is the matrix guaranteed to be square? (The test cases suggest so, but the definition does not.) \$\endgroup\$
    – Arnauld
    Sep 26, 2018 at 10:46
  • \$\begingroup\$ @Arnauld 1) I'm on it. 2) I didn't want to establish a time limit, and nobody suggested any limit while the challenge was in the sandbox. If you need one, would you consider 30 minutes a reasonable limit? 3) Yes, the test matrices are the ones shown, and they will all be square if more are needed. \$\endgroup\$
    – Charlie
    Sep 26, 2018 at 10:56
  • \$\begingroup\$ There exists an (relatively easy to implement) O(input size) algorithm to this challenge, so it's not as interesting as it may look at first. \$\endgroup\$
    – DELETE_ME
    Sep 26, 2018 at 10:59
  • \$\begingroup\$ @user202729 What would the input-size be in your O(input size) then? For a 5x5 matrix it would O(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\$ Sep 26, 2018 at 11:08
  • 4
    \$\begingroup\$ I think, it's something like this algorithm \$\endgroup\$
    – Kirill L.
    Sep 26, 2018 at 12:25

2 Answers 2

10
\$\begingroup\$

Nim

import algorithm, math, sequtils, strutils

let l = split(stdin.readLine())
var m = map(l, parseInt)
let n = int(sqrt(float(len(m))))
let o = sorted(m, system.cmp[int])

proc rotations(P, Q: int): tuple[D, L, R, U: string, P, Q: int]=
  result = (D: "D", L: "L", R: "R", U: "U", P: P, Q: Q)
  if P > n - P:
    result.D = "U"
    result.U = "D"
    result.P = n - P
  if Q > n - Q:
    result.L = "R"
    result.R = "L"
    result.Q = n - Q

proc triangle(r: int): string=
  let p = r div n
  let q = r mod n
  let i = find(m, o[r])
  let s = i div n
  let t = i mod n
  var u = s
  var v = q
  if s == p and t == q:
    return ""
  var patt = 0
  if p == s: 
    u = s + 1
    patt = 4
  elif q == t:
    if q == n - 1:
      v = t - 1
      patt = 8
    else:
      u = p
      v = t + 1
      patt = 3
  elif t > q:
    patt = 2
  else:
    patt = 7
  var Q = abs(max([q, t, v]) - min([q, t, v]))
  var P = abs(max([p, s, u]) - min([p, s, u]))
  let x = p*n + q
  let y = s*n + t
  let z = u*n + v
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  let R = rotations(P, Q)

  result = case patt:
    of 2:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q)
    of 3:
      repeat("$#$#," % [$q, R.U], R.P) & 
        repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P) & 
        repeat("$#$#," % [$p, R.R], R.Q)
    of 4:
      repeat("$#$#," % [$p, R.L], R.Q) & 
        repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q) & 
        repeat("$#$#," % [$q, R.D], R.P)
    of 7:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q)
    of 8:
      repeat("$#$#," % [$s, R.R], R.Q) & 
        repeat("$#$#," % [$t, R.D], R.P) &
        repeat("$#$#," % [$s, R.L], R.Q) & 
        repeat("$#$#," % [$t, R.U], R.P)
    else: ""

proc Tw(p, t, P, Q: int): string =
  let S = P + Q
  result = "$#D,$#$#U,$#$#D,$#$#U," % [
    $t, if P > n - P: repeat("$#L," % $p, n - P) else: repeat("$#R," % $p, P),
    $t, if S > n - S: repeat("$#R," % $p, n - S) else: repeat("$#L," % $p, S), 
    $t, if Q > n - Q: repeat("$#L," % $p, n - Q) else: repeat("$#R," % $p, Q), 
    $t]

proc line(r: int): string=
  let p = n - 1
  let q = r mod n
  let i = find(m, o[r])
  var t = i mod n
  if t == q: 
    return ""
  let j = t == n - 1
  var P = t - q
  let x = p*n + q
  let y = x + P
  let z = y + (if j: -1 else: 1)
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  if j:
    let R = rotations(1, P)
    result = "$#D,$#$#U,$#$#R,$#D,$#L,$#U," % [
      $t, repeat("$#$#," % [$p, R.R], R.Q), 
      $t, repeat("$#$#," % [$p, R.L], R.Q), 
      $p, $t, $p, $t]
  else:
    result = Tw(p, t, P, 1)  
  
proc swap: string=
  result = ""
  if m[^1] != o[^1]:
    m = o
    for i in 0..(n div 2-1):
      result &= Tw(n - 1, n - 2*i - 1, 1, 1)
    result &= "$#R," % $(n - 1)
  
var moves = ""
for r in 0..(n^2 - n - 1):
  moves &= triangle(r)
if n == 2 and m[^1] != o[^1]:
  m = o
  moves &= "1R"
else:
  for r in (n^2 - n)..(n^2 - 3):
    moves &= line(r)
  if n mod 2 == 0:
    moves &= swap()
  if len(moves) > 0:
    moves = moves[0..^2]
  
echo moves

Try it online!

A quick attempt to implement the Torus puzzle solution algorithm from an article published in Algorithms 2012, 5, 18-29 that I mentioned in comments.

Accepts the input matrix in flattened form, as a line of space-delimited numbers.

Here also is a validator in Python 2. It takes two lines as input: the original scrambled matrix in the same form as the main code, and the proposed sequence of moves. The output of the validator is the matrix resulting from applying these moves.

Explanation

In the first part of the algorithm, we order all rows except the last one.

We do this by performing series of "triangle rotations" (proc triangle) - the sequences of moves that result in only three cells swapping places, and all the rest staying unchanged. We take each consecutive "working" cell with coordinates \$[p, q]\$, then find the cell \$[s, t]\$ that currently contains the number that should go to \$[p, q]\$, and complete the right triangle by selecting a third point \$[u, v]\$ according to some pattern, as shown in Fig. 4 of the linked article.

In Fig. 2, the authors present 8 possible patterns and the corresponding sequences of moves, but in my code all cases have actually been covered by only 5 patterns, so that no. 1, 5, and 6 are not used.

In the second part, the last row except the two last elements is ordered by performing "three elements rotations" on a line (proc line), which consist of two triangle rotations each (see Fig. 3 of the article).

We select our current working cell \$[p, q]\$ as the left point, cell containing the target value \$[s, t]\$ as the central point, and \$[s, t+1]\$ as the right point. This westbound movement is named \$T_W\$ in the article, and so is my string forming proc for this. If \$t\$ is already the last column, so that \$t+1\$ does not exist, we take \$[s, t-1]\$ as the third point, and modify the action accordingly: two triangle rotations are performed by patterns 7 and 8 (instead of 7 and 1 in the original \$T_W\$ sequence).

Finally, if \$n\$ is odd, the remaining two elements must be already in place, as we are guaranteed that a solution exists. If \$n\$ is even, and the two remaining elements are not in place, then according to Lemma 1 (page 22), they can be swapped by a series of \$T_W\$ moves, followed by one shift east (\$=R\$). Since the provided example swaps the first two entries, and we need to swap the last two, our proc swap performs \$T_W\$ moves in reverse order.

In the edge case of \$n = 2\$ we don't need all these complex procedures at all - if the last row elements are not in place after part 1, a single \$1R\$ move is sufficient to make the matrix fully ordered.

Update: Added new proc rotations that reverses the direction of moves if that would result in less steps.

\$\endgroup\$
4
  • \$\begingroup\$ Impressive! I'll create some more test cases then. Meanwhile, I'm sure this solution can be optimized, as there are chunks like 7L,7L,7L,7L,7D,7D,7D,7D than can be reduced and 8R,8R,8R,8R,8R,8R,8R than can be converted to 8L,8L for a 9x9 matrix. \$\endgroup\$
    – Charlie
    Sep 27, 2018 at 12:35
  • \$\begingroup\$ I've tried your algorithm with a 100x100 matrix and it solves it in less than 4 seconds. I really didn't expect this problem to have a linear-time solution. I'll try to write better challenges in the future! \$\endgroup\$
    – Charlie
    Sep 27, 2018 at 12:46
  • \$\begingroup\$ Maybe it would have been better to pose this challenge with a single, fixed matrix as the only test case, and set the winning criterion to be just the size of the found path to solve it, had I known before that this problem had a O(n^2) solution. Would you consider porting this answer to a new question with such winning criterion? \$\endgroup\$
    – Charlie
    Oct 1, 2018 at 9:34
  • \$\begingroup\$ @Charlie While I'll still try to refine the current solution a bit, I have really no idea, how to tackle the overall path optimization problem... \$\endgroup\$
    – Kirill L.
    Oct 1, 2018 at 15:09
5
\$\begingroup\$

Python 2, size 100 in <30 seconds on TIO

import random
def f(a):
 d = len(a)
 r = []
 def V(j, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "U%d" % j:r.pop()
    else:r.append("D%d" % j)
    b = a[-1][j]
    for i in range(len(a) - 1):
     a[-1 - i][j] = a[-2 - i][j]
    a[0][j] = b
  else:
   for k in range(b):
    if r and r[-1] == "D%d" % j:r.pop()
    else:r.append("U%d" % j)
    b = a[0][j]
    for i in range(len(a) - 1):
     a[i][j] = a[i + 1][j]
    a[-1][j] = b
 def H(i, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "L%d" % i:r.pop()
    else:r.append("R%d" % i)
    a[i] = a[i][-1:] + a[i][:-1]
  else:
   for k in range(b):
    if r and r[-1] == "R%d" % i:r.pop()
    else:r.append("L%d" % i)
    a[i] = a[i][1:] + a[i][:1]
 b = sorted(sum(a, []))
 for i in range(d - 1):
  for j in range(d):
   c = b.pop(0)
   e = sum(a, []).index(c)
   if e / d == i:
    if j == 0:H(i, e - j)
    elif j < e % d:
     if i:
      V(e % d, 1)
      H(i, j - e)
      V(e % d)
      H(i, e - j)
     else:
      V(e)
      H(1, e - j)
      V(j, 1)
   else:
    if j == e % d:
     H(e / d)
     e += 1
     if e % d == 0:e -= d
    if i:
     V(j, i - e / d)
    H(e / d, e - j)
    V(j, e / d - i)
 c = [b.index(e) for e in a[-1]]
 c = [sum(c[(i + j) % d] < c[(i + k) % d] for j in range(d) for k in range(j)) % 2 and d * d or sum(abs(c[(i + j) % d] - j) for j in range(d)) for i in range(d)]
 e = min(~c[::-1].index(min(c)), c.index(min(c)), key = abs)
 H(d - 1, e)
 for j in range(d - 2):
  e = a[-1].index(b[j])
  if e > j:
   c = b.index(a[-1][j])
   if c == e:
    if e - j == 1:c = j + 2
    else:c = j + 1
   V(e)
   H(d - 1, j - e)
   V(e, 1)
   H(d - 1, c - j)
   V(e)
   H(d - 1, e - c)
   V(e, 1)
 return r

Try it online! Link includes three small test cases with full move output, plus a silent test of 100x100 to show that the code works (the move output would exceed TIO's limits). Explanation: The code attempts to perform an insertion sort on the array, building it up in ascending order as it goes. For all the rows except the last row, there are a number of cases:

  • The element is in the correct row, but belongs in column 0. In this case, it is simply rotated until it reaches column 0.
  • The element is in the correct place. In this case, nothing happens. (This is also true if the element belongs in column 0, it's just that 0 rotations happen in that case.)
  • The element is in the top row but in the wrong column. In that case, it is rotated down, then horizontally until the element is in the correct column, then rotated up again.
  • The element is in the correct row but in the wrong column. In that case, it is rotated up, then the row is rotated to its column, then it is rotated down, then the row is rotated back. (Effectively this is a rotation of the next case.)
  • The element is in the correct column but in the wrong row. In that case, the row is rotated right, to reduce it to the last case.
  • The element is in the wrong row and the wrong column. In this case, the correct column is rotated to the wrong row (skipped for the top row), that row is then rotated to the correct column, and the column is then rotated back.

The above rotations are performed in whichever direction minimises the number of steps; a size 2 square is always solved using left and up moves, regardless of the description above.

Before the bottom row is completed, it is rotated to minimise the total distance out of place, but also to ensure that the parity of the bottom row is even, as it can't be changed by the final part of the algorithm. If there is more than one rotation with the same minimal distance, the rotation with the smallest number of moves is chosen.

The algorithm for the bottom row relies on a 7-operation sequence which exchanges the elements in three columns. The sequence is applied to each of the remaining numbers of the bottom row in order in turn to bring them to their desired location; if possible the element in that location is moved to its desired location, but if a straight swap is needed the element is simply moved to the nearest available column, hopefully allowing it to be fixed up next time.

\$\endgroup\$
12
  • \$\begingroup\$ Thank you very much for your answer, Neil! But remember, this is not a code golf. Instead of the length of the code you should indicate the greatest size N of the NxN matrix you have solved and the length of the list of movements to solve that matrix. \$\endgroup\$
    – Charlie
    Sep 26, 2018 at 20:49
  • \$\begingroup\$ @Charlie Well, that's 6, but only becuase I've been too lazy to paste in a bigger matrix. Although it's brute force, it scales linearly with area, so it should be capable of large matrices. \$\endgroup\$
    – Neil
    Sep 26, 2018 at 21:14
  • \$\begingroup\$ Actually, worst case might be quadratic with area. \$\endgroup\$
    – Neil
    Sep 26, 2018 at 21:19
  • 1
    \$\begingroup\$ @Charlie TIO link now solves a random 100x100 matrix. \$\endgroup\$
    – Neil
    Sep 28, 2018 at 23:05
  • 1
    \$\begingroup\$ @Charlie I've now come up with a major optimisation for the bottom row, but I think that's the last change I'm going to be making to this answer. \$\endgroup\$
    – Neil
    Oct 3, 2018 at 9:11

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.