6
\$\begingroup\$

I came up with the following solution for rotating an NxN matrix 90 degrees clockwise, to solve this CodeEval challenge:

Input

The first argument is a file that contains 2D N×N matrices (where 1 <= N <= 10), presented in a serialized form (starting from the upper-left element), one matrix per line. The elements of a matrix are separated by spaces.

For example:

a b c d e f g h i j k l m n o p

Output

Print to stdout matrices rotated 90° clockwise in a serialized form (same as in the input sample).

For example:

m i e a n j f b o k g c p l h d

It looks elegant to me, but can someone explain how its performance compares to the more common solutions mentioned here? Does it have \$O(n^2)\$ time complexity?

import sys, math

for line in open(sys.argv[1]):
    original = line.rstrip().replace(' ', '')
    nSquared = len(original)
    n = int(math.sqrt(nSquared))
    output = ''

    for i in range(nSquared):
        index = n * (n - 1 - i % n) + int(i / n)
        output += original[index] + ' '

    print(output.rstrip())

The expression n * (n - 1 - i % n) + int(i / n) is something I found while observing common patterns among rotated matrices.

\$\endgroup\$
4
\$\begingroup\$
  1. The formula is elegant, and the approach is correct.

  2. You have to be careful with complexities though. Specifically you have to be very clear about what \$n\$ is. Typically complexity is a function of the size of input (which is, provided that \$n\$ is a matrix dimension, \$n^2\$ itself), so I'd qualify your solution as linear. And since each element should be accounted for, no better solution is possible.

  3. The asymptotic constant could be better. The problem doesn't ask to rotate the matrix; it is only asks to print the matrix as if it was rotated. In other words, building output is technically a waste of time. Use your formula to print elements as you enumerate them.

\$\endgroup\$
  • \$\begingroup\$ Thanks! As a Python newbie, I only recently found how slow string concatenation using the + operator is. As I understand, the quicker method of string concatenation is ''.join(stringPartsList). Would repeatedly printing strings be faster than keeping them all in a list and then printing the list contents at once? \$\endgroup\$ – Ohas Feb 26 '15 at 23:03
4
\$\begingroup\$

This solution is equivalent to the one in the accepted answer of the question you linked. The expression you used is the 1D-array equivalent of how that answer derived the appropriate (row, col) indexes in a 2D-array. The time complexity is \$O(N^2)\$, because in an NxN matrix there are \$N^2\$ cells, and your main operation visits all of them. You have some extra costs due to .rstrip() and .replace() but those don't change the asymptotic complexity.

In terms of Python coding, you forgot to close the file you opened after reading. You should wrap the loop inside a with open(...) as fh:, iterate over fh, and it will be automatically closed when leaving the with block.

\$\endgroup\$
  • \$\begingroup\$ I'm new to Python, so maybe this is a silly question: Why close the file when I know that my program ends when I am done reading from the file? \$\endgroup\$ – Ohas Feb 26 '15 at 22:56
  • 1
    \$\begingroup\$ Because bad habits are hard to kill later? To be a good citizen? For the love of doing things the right and recommended way? For the wonderful day when you extend your program or copy paste a large chunk from it? \$\endgroup\$ – janos Feb 26 '15 at 23:02
1
\$\begingroup\$

I find the solution very complex.

I think you should first transform each line in a proper 2D array and then rotate it using the zip(*reversed(matrix)) before re-serializing the result.

How about this:

def rotate(data):
    size = int((len(data)/2)**0.5)+1
    matrix = [data.split(' ')[i:i+size] for i in range(0,size*size,size)]
    rotated_matrix = zip(*reversed(matrix))
    temp = [' '.join(row) for row in rotated_matrix]
    return ' '.join(temp)

data = 'a b c d e f g h i j k l m n o p'

rotate(data)

output - > 'm i e a n j f b o k g c p l h d'
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Your provided a short review (i.e. I find the solution very complex.) - could you expand this? Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. Please read Why are alternative solutions not welcome? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Oct 29 '18 at 22:34
  • 1
    \$\begingroup\$ thank you for your comment @SᴀᴍOnᴇᴌᴀ, i hope my submission is better now \$\endgroup\$ – denys Oct 30 '18 at 0:15

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.