Tuesday, 2 October 2018

Can't spot the bug in my rotate matrix code

I know there's an easy way using transpose to rotate a square-matrix 90 degrees, but I'm writing a solution as if I don't know that one (in other words, I want to do the swapping). The generally idea below is to swap layer by layer. The offset represents what layer (outward to inward) is being swapped.

Here's the algorithm (note that it is wrapped in a class because that's a Leetcode thing):

class Solution:
    def rotate(self, matrix):
        for start in range(len(matrix)//2):
            end = len(matrix) - start - 1

            # swap all 4 coordinates:
            for offset in range(start, end): 
                # swap top_left over top_right
                temp, matrix[start+offset][end] = matrix[start+offset][end], matrix[start][start+offset]

                # swap top_right -> bottom_right 
                temp, matrix[end][end-offset] = matrix[end][end-offset], temp

                # swap bottom_right -> bottom_left
                temp, matrix[end-offset][start] = matrix[end-offset][start], temp

                # swap bottom_left -> top_left 
                matrix[start][start+offset] = temp


This works for some hand tests with small matrices, as well as the smaller input test cases in the Leetcode submission. However, it fails on the following input:

[[ 2,  29,  20,  26,  16,  28],
 [12,  27,   9,  25,  13,  21],
 [32,  33,  32,   2,  28,  14],
 [13,  14,  32,  27,  22,  26],
 [33,   1,  20,   7,  21,   7],
 [ 4,  24,   1,   6,  32,  34]]

Expected output:

[[ 4,  33,  13,  32,  12,   2],
 [24,   1,  14,  33,  27,  29],
 [ 1,  20,  32,  32,   9,  20],
 [ 6,   7,  27,   2,  25,  26],
 [32,  21,  22,  28,  13,  16],
 [34,   7,  26,  14,  21,  28]]

My output:

[[ 4,  33,  13,  32,  12,   2],
 [24,   1,   7,  33,  27,  29],
 [ 1,  20,  32,   2,  14,  20],
 [ 6,  28,  32,  27,  25,  26],
 [32,  21,  22,   9,  13,  16],
 [34,   7,  26,  14,  21,  28]]


This matrix is just big enough to where it becomes tedious to walk through the algorithm by hand like I did for the smaller input cases to debug. Where is the bug in my implementation?



from Can't spot the bug in my rotate matrix code

No comments:

Post a Comment