<p>You are given an <code>m x n</code> integer matrix <code>grid</code>​​​, where <code>m</code> and <code>n</code> are both <strong>even</strong> integers, and an integer <code>k</code>.</p>

<p>The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid.png" style="width: 231px; height: 258px;" /></p>

<p>A cyclic rotation of the matrix is done by cyclically rotating <strong>each layer</strong> in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the <strong>counter-clockwise</strong> direction. An example rotation is shown below:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/explanation_grid.jpg" style="width: 500px; height: 268px;" />
<p>Return <em>the matrix after applying </em><code>k</code> <em>cyclic rotations to it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/19/rod2.png" style="width: 421px; height: 191px;" />
<pre>
<strong>Input:</strong> grid = [[40,10],[30,20]], k = 1
<strong>Output:</strong> [[10,20],[40,30]]
<strong>Explanation:</strong> The figures above represent the grid at every state.
</pre>

<p><strong class="example">Example 2:</strong></p>
<strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid5.png" style="width: 231px; height: 262px;" /></strong> <strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid6.png" style="width: 231px; height: 262px;" /></strong> <strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid7.png" style="width: 231px; height: 262px;" /></strong>

<pre>
<strong>Input:</strong> grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
<strong>Output:</strong> [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
<strong>Explanation:</strong> The figures above represent the grid at every state.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 50</code></li>
	<li>Both <code>m</code> and <code>n</code> are <strong>even</strong> integers.</li>
	<li><code>1 &lt;= grid[i][j] &lt;=<sup> </sup>5000</code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>
class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:

        # we can do the rotation by rotating every layer (write a function
        # for that) also we can save time by computing the modulo and 
        # rotation direction

        # save the dimensions of the grid
        m = len(grid)
        n = len(grid[0])

        # make a function to compute the next position in terms of rows
        # and columns
        def next_position(position, layer):

            # compute how many numbers we need to rotate in this layer
            # (two times the number of elements in a row
            # plus the elements in the column while subtracting elements
            # that are already counted by the row)
            counter = 2*(m-2*layer) + 2*(n-2*layer-2)

            # compute the modulo of the position so we do not encounter
            # shady positions
            position = position % counter

            if position < (m-2*layer-1):
                # print('left')
                return layer+position, layer
            elif position < (m-2*layer-1)+(n-2*layer-1):
                # print('down')
                return m-layer-1, layer + position - (m-2*layer) + 1
            elif position < 2*(m-2*layer-1)+(n-2*layer-1):
                # print('right')
                return (m-layer-1) - (position - (m-2*layer-1) - (n-2*layer-1)), n-layer-1
            else:
                # print('up')
                return layer, (n-layer-1) - (position - 2*(m-2*layer-1) - (n-2*layer-1))

        # first write a function that rotates a layer by x positions
        def rotate_layer(layer):

            # compute how many numbers we need to rotate in this layer
            # (two times the number of elements in a row
            # plus the elements in the column while subtracting elements
            # that are already counted by the row)
            counter = 2*(m-2*layer) + 2*(n-2*layer-2)
            
            # make an array to fill the numbers (we could do it in place
            # but that is to complicated for me currently)
            new_elements = [0]*counter

            # go through the matrix and rotate by position
            for idx in range(0, counter):

                # get the indices where we need to look for the current number
                rx, cx = next_position(idx, layer)
                # print('Layer', layer, 'Position', idx, 'Coordinates', rx, cx)

                # compute the new index
                nx = (idx+k) % counter

                # fill in the array
                new_elements[nx] = grid[rx][cx]
            
            # go through the original array and fill in the values
            for idx in range(0, counter):

                # get the indices where we need to look for the current number
                rx, cx = next_position(idx, layer)

                # fill in the array
                grid[rx][cx] = new_elements[idx]
                
        # go through each layer and make the rotation
        for lay in range(min(m, n)//2):
            rotate_layer(lay)
        return grid
142