5
\$\begingroup\$

The question is as follows: Rotate an NxN matrix clockwise by one element and display the new matrix. For example, if

A = [[1, 2, 3, 4],
     [5, 6, 7, 8],
     [9, 10,11,12],
     [13,14,15,16]]

Then the rotated matrix obtained from A will be

[[5,  1,  2,  3], 
 [9,  10, 6,  4], 
 [13, 11, 7,  8], 
 [14, 15, 16, 12]]

You may think of it as rotating each of the "rings" clockwise by one element. So, that was the question given to us and we were told to absolutely not use Numpy or any other library that can handle matrices.

Here's what I did:

def get_previous_pos(i, j, matrix_size):
    ring_no = min(j, matrix_size-1-j, i, matrix_size-1-i)
    max_no = matrix_size - 1 - ring_no
    x = i + (j==ring_no) - (j==max_no) - (i==max_no and j==ring_no) + (j==max_no and i==ring_no)
    y = j + (i==max_no) - (i==ring_no) - (i==max_no and j==max_no) + (i==ring_no and j==ring_no)
    return x,y

def get_rotated_matrix(matrix):
    n = len(matrix)
    rotated_matrix = [matrix[row_no][:] for row_no in range(n)]
    for i in range(n):
        for j in range(n):
            prev = get_previous_pos(i, j, n)
            rotated_matrix[i][j] = matrix[prev[0]][prev[1]]
    return rotated_matrix



n = int(input("Enter size of the square matrix: "))
matrix = [[int(input()) for j in range(n)] for i in range(n)]
print("original matrix --> ", matrix)
print("rotated matrix --> ", get_rotated_matrix(matrix))

The function, get_rotated_matrix(matrix) takes any 2D NxN list and returns the rotated 2D list. The get_previous_pos(i,j,matrix_size) function takes a matrix position as its (i,j) value, the matrix size(N), and returns the position of the element that will occupy (i,j) after the clockwise rotation.

I have tested this code for matrix sizes ranging from 1X1 up to 5x5. It did produce the desired output. So, I suppose its safe to say that it works. However, I'm sure there's a much better way to go about this and was wondering if you can help me out.

Edit:

I've added a bit of driver code to the original so it can be tested without further modification. I've also attached a sample input/output below for a 4x4 matrix:

Enter size of the square matrix: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
original matrix -->  [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
rotated matrix -->  [[5, 1, 2, 3], [9, 10, 6, 4], [13, 11, 7, 8], [14, 15, 16, 12]]
\$\endgroup\$
5
  • \$\begingroup\$ This is a good first question. If you have the test program that validates the correctness, that's certainly worth adding for review. \$\endgroup\$ Jan 15 at 13:45
  • \$\begingroup\$ @TobySpeight I'll add that now. Also, I've seen people post links to their code running on some website so others can see it working without having to download it. Can you plz tell me where I can do that? I remember jsfiddle for javascript. Is there a python equivalent? \$\endgroup\$
    – st0n3r
    Jan 15 at 13:51
  • \$\begingroup\$ There are many online Python repls; perhaps try python.codepad.org \$\endgroup\$
    – Reinderien
    Jan 15 at 14:03
  • \$\begingroup\$ Why "no libraries"? \$\endgroup\$
    – Reinderien
    Jan 15 at 16:27
  • \$\begingroup\$ @Reinderien It was a question on a test. Those were the requirements. \$\endgroup\$
    – st0n3r
    Jan 15 at 16:29

2 Answers 2

2
\$\begingroup\$

When possible, iterate directly over collections. Most of the time, you don't need indexes when iterating over Python collections. As an example, here's an easier way to initialize an independent copy of the matrix. (Or just use deepcopy).

rotated_matrix = [list(row) for row in matrix]

Put all code inside of functions or methods. Some will say it's alright to put a little bit of logic, including defining variables, after the __main__ guard. Don't do it. Just adopt the discipline of never doing more than calling a function and you'll avoid time wasted on silly bugs caused by the unexpected presence of global variables that you had forgotten about during the heat of code writing. Here's the template I use for scripts like this:

# Only imports, functions, classes, and constants at top level.

import sys

def main(args):
    ...

if __name__ == '__main__':
    main(sys.argv[1:])

Don't make humans enter a matrix one cell at a time. Python is powerful. You can easily parse a variety of simple input formats for a matrix (e.g., "1,2,3,4 5,6,7,8 9,10,11,12 13,14,15,16"). Even better, since this is mostly a learning project, just define a matrix or two in your code (as constants) and let the user pick one via a short name. I'm not endorsing any particular strategy, but the current usage implementation too painful, too much work. Part of becoming a better software engineer is developing a deep loathing for that kind of tedium -- in other words, cultivating your laziness.

An opaque algorithm that is probably fine but isn't easy to understand. You've done a good job posing a clear question, and I can understand the general outlines of your code and strategy easily enough. However, the logic in get_previous_pos() -- in many ways, the heart of the program -- is opaque. It's the kind of math-heavy logic that one has to dig into deeply to understand. I assume it works but it's neither intuitive nor self-evidently correct.

An alternative to consider. I don't know if this will be valuable to you, but here's how I worked when trying to solve this interesting problem. I started in fantasy land, with a top level function that is easy to understand only because it hand-waves away the complexity to a not-yet-written utility function:

def get_rotated_matrix(matrix):
    rotated = [list(row) for row in matrix]
    for (r1, c1), (r2, c2) in get_index_rings(len(matrix)):
        rotated[r2][c2] = matrix[r1][c1]
    return rotated

And then I tried to write the utility function in an intuitive way. I envisioned each of the matrix "rings" as a starting position on the diagonal (eg, (0, 0)) plus a sequence of movements (right, down, left, up). To the extent that I have succeeded in writing a more intuitive version, here are some of the key points that I would emphasize: (1) declarative names when helpful (eg, the direction constants); (2) comments to guide the reader by providing context and information about purpose or strategy; (3) the use of blank lines plus those comments to group the code into meaningful sub-units; and (4) an algorithm backed by a simple narrative (we drive around the ring, making turns).

def get_index_rings(n):
    # Movement directions.
    RIGHT, DOWN, LEFT, UP = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # The starting positions for each of the rings are the points
    # on the diagonal: (0,0), (1,1), etc until we reach the middle.
    # When n is odd, the innermost ring is a single cell and can be ignored.
    for start in range(n // 2):
        # Inital position.
        r, c = (start, start)

        # The movements around the current ring.
        times = n - start - start - 1
        moves = [RIGHT] * times + [DOWN] * times + [LEFT] * times + [UP] * times

        # Yield position pairs as we move around the ring: (CURRENT, NEXT).
        for dr, dc in moves:
            p1 = (r, c)
            r += dr
            c += dc
            yield (p1, (r, c))
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I have no idea how you were able to take the time out to write such an awesome, detailed review but I want you to know that I really appreciate it! Your solution truly is a lot more intuitive. I mean, it makes sense without even reading the comments. Heck, even I find my get_previous_pos() function disgusting now! I have a question - How do I, for lack of a better word, "see" like you do? I mean, when you put it as "drive around the ring, making turns", I was like, why didn't I think of this! Is this something you can get better at with practice? \$\endgroup\$
    – st0n3r
    Jan 16 at 6:29
  • \$\begingroup\$ @st0n3r No magic secrets, but a few ideas. (1) Yes, practice helps. (2) If you find an interesting problem, try to solve it, but don't stop at "working". Rewrite it (even multiple times) to make it intuitive. (3) Really study the APIs of the core data structures (list, tuple, dict, str) as well as the main data-wrangling modules (itertools, collections, operator) so you known how to whip data around easily. (4) Focus first on data: well-structured data (like the group of movement directions or the list of those directions in moves) tends to simplify code and make for easier algorithms. \$\endgroup\$
    – FMc
    Jan 16 at 7:51
  • \$\begingroup\$ @st0n3r Regarding #4, search the internet for Rob's Pike's 5 rules, or the Fred Brooks quote with "show me your flowcharts", or Linus Torvalds' discussion of the centrality of a good data model to the success of git. Data is often the key to simpler code. \$\endgroup\$
    – FMc
    Jan 16 at 8:01
  • \$\begingroup\$ thx, I'll keep these in mind from now on :) \$\endgroup\$
    – st0n3r
    Jan 17 at 6:34
2
\$\begingroup\$

Add a main guard

This is a standard idiom:

if __name__ == '__main__':
    n = int(input("Enter size of the square matrix: "))
    matrix = [[int(input()) for j in range(n)] for i in range(n)]
    print("original matrix --> ", matrix)
    print("rotated matrix --> ", get_rotated_matrix(matrix))

This allows your definitions to be imported from another program, without executing the main program. That facilitates my next suggestion:

Consider automating the tests

The current method of testing is error prone - values have to be supplied to the program and the output must be inspected. Have the computer do those tasks for you!

Example:

import rotate_matrix

if __name__ == '__main__':
    input = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
    expected = [[5, 1, 2, 3], [9, 10, 6, 4], [13, 11, 7, 8], [14, 15, 16, 12]]
    assert rotate_matrix.get_rotated_matrix(input) == expected
   

We can build on this if we use one of the available unit-testing frameworks; that improves on this very simple testing by executing independent tests separately and reporting on them all, rather than exiting on the first failure.

Look up the doctest module for an easy way to add tests to your code.

\$\endgroup\$
3
  • \$\begingroup\$ Hey, thx for reviewing my code. I will add the main guard to my codes from now on. And this testing method is so much better than what I was doing manually! I had a question about my code - in lines 3 & 4 of the get_previous_pos function, I use boolean values with regular integers to get the job done. Since booleans are subclasses of int, its kind of like regular arithmetic. However, what I wanted to know was, is this kind of thing acceptable? Performing regular arithmetic operations like + - * / using the int value of a boolean? \$\endgroup\$
    – st0n3r
    Jan 15 at 15:47
  • \$\begingroup\$ I hadn't actually looked at the implementation. Personally, as more of a C and C++ guy, I'm comfortable with that, but perhaps give greater regard to someone who does more Python than me! BTW, I'd hold back on the "accepted" tick until you have answers that address all your concerns - accepting an answer this early might dissuade others who can provide more insight. \$\endgroup\$ Jan 15 at 16:01
  • \$\begingroup\$ Ok, I'll undo the accept :) \$\endgroup\$
    – st0n3r
    Jan 15 at 16:24

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.