Matrix Rotation
June 6, 2017
We have a two-part exercise today, based on a Microsoft interview question.
First, write a program to rotate an m × n matrix 90° to the right, as shown below; your solution should touch each matrix element only once:
a b c
d e f m j g d a
A = g h i rot(A) = n k h e b
j k l o l i f c
m n o
Second, write a program to rotate a square matrix with n rows and columns in-place. where the source and target matrices are the same matrix and there is no intermediate matrix (be sure your solution works for both even and odd n):
a b c d e u p k f a
f g h i j v q l g b
B = k l m n o rot(B) = w r m h c
p q r s t x s n i d
u v w x y y t o j e
Your task is to write the two programs that rotate matrices. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Advertisements
Pages: 1 2
;;; Implement a matrix as a vector in row-major order, with width. (define imp::matrix-contents cdr) (define matrix-width car) (define (matrix-height m) (/ (vector-length (imp::matrix-contents m)) (matrix-width m))) (define (make-matrix h w . o) (let ((o (if (null? o) #f (car o)))) (cons w (make-vector (* h w) o)))) (define (matrix-ref m r k) (vector-ref (imp::matrix-contents m) (+ (* (matrix-width m) r) k))) (define (matrix-set! m r k o) (vector-set! (imp::matrix-contents m) (+ (* (matrix-width m) r) k) o)) ;;; Some of the points appear to go from (r, k) to (k, h - r - 1), so ;;; guess they all do. By linearity or something. (define (rot m) (let* ((h (matrix-height m)) (w (matrix-width m)) (m1 (make-matrix w h))) (do ((r 0 (+ r 1))) ((= r h)) (do ((k 0 (+ k 1))) ((= k w)) (matrix-set! m1 k (- h r 1) (matrix-ref m r k)))) m1)) ;;; At each (r, k) apply the rotating transformation to the four ;;; corresponding points at once. But this rotates the matrix four ;;; times! So only do half of the rows and half of the columns to ;;; rotate only once. Rounding both ways seems to work already. (define (rot! m) (let ((hw (matrix-height m))) (do ((r 0 (+ r 1))) ((= r (floor (/ hw 2)))) (do ((k 0 (+ k 1))) ((= k (ceiling (/ hw 2)))) (let* ((nr r) (nk k) (n (matrix-ref m nr nk)) (er nk) (ek (- hw nr 1)) (e (matrix-ref m er ek)) (sr ek) (sk (- hw er 1)) (s (matrix-ref m sr sk)) (wr sk) (wk (- hw sr 1)) (w (matrix-ref m wr wk))) (matrix-set! m er ek n) (matrix-set! m sr sk e) (matrix-set! m wr wk s) (matrix-set! m nr nk w)))))) ;;; Nice display for ocular inspection. (define (lay m) (let* ((w (matrix-width m)) (h (matrix-height m))) (do ((r 0 (+ r 1))) ((= r h)) (do ((k 0 (+ k 1))) ((= k w) (newline)) (write-char #\space) (write (matrix-ref m r k)))))) ;;; Test some. Caught a few thinkoes and a typo. (define A (cons 3 '#(a b c d e f g h i j k l m n o))) (define B (cons 5 (apply vector '(a b c d e f g h i j k l m n o p q r s t u v w x y)))) (define C (cons 4 (apply vector '(a b c d e f g h i j k l m n o p)))) (lay A) (newline) (lay (rot A)) (newline) (lay B) (newline) (lay (rot B)) (newline) (rot! B) (lay B) (newline) (lay C) (newline) (lay (rot C)) (newline) (rot! C) (lay C) (newline)The first part of the exercise in Python
def rot_right(matrix): return list(zip(*reversed(matrix)))Both parts of the exercise in Julia. Just a single generic method covering all possibilities.
function rotate{T <: Any}(X::Matrix{T})
n = size(X, 1)
n1 = n + 1
Y = X'
for i = 1:div(n, 2)
j = n1 – i
Y[:,i], Y[:,j] = Y[:,j], Y[:,i]
end
return Y
end
The second part in Python. The rotation is done by swapping two matrix elements at the time.
def rot_right_in_place(matrix): n = len(matrix) c = n-1 size = (n+1)//2 def rot(row, col): col0, row0, col, row = col, row, row, c - col matrix[row0][col0], matrix[row][col] = matrix[row][col], matrix[row0][col0] # swap return row, col for i in range(size): for j in range(size if n % 2 == 0 else size-1): rot(*rot(*rot(i, j)))A better version of the second part. This version sets the matrix elements only once.
def rot_right_in_place(matrix): n = len(matrix) c = n-1 size = (n+1)//2 def rot(row, col): save = matrix[row][col] for _ in range(3): col0, row0, col, row = col, row, row, c - col matrix[row0][col0] = matrix[row][col] matrix[row][col] = save for i in range(size): for j in range(size if n % 2 == 0 else size-1): rot(i, j)