1<<-DOC 
 2Note: Try to solve this task in-place (with O(1) additional memory), since this is what you'll be asked to do during an interview.
 3
 4You are given an n x n 2D matrix that represents an image. Rotate the image by 90 degrees (clockwise).
 5
 6Example
 7
 8For
 9
10a = [[1, 2, 3],
11     [4, 5, 6],
12     [7, 8, 9]]
13the output should be
14
15rotateImage(a) =
16    [[7, 4, 1],
17     [8, 5, 2],
18     [9, 6, 3]]
19Input/Output
20
21[time limit] 4000ms (rb)
22[input] array.array.integer a
23
24Guaranteed constraints:
251 ≤ a.length ≤ 100,
26a[i].length = a.length,
271 ≤ a[i][j] ≤ 104.
28
29[output] array.array.integer
30DOC
31
32describe "rotate_image" do
33  def rotate_image(image)
34    copy = Array.new(image.size) { Array.new }
35
36    0.upto(image.size - 1) do |i|
37      (image.size - 1).downto(0) do |j|
38        copy[i].push(image[j][i])
39      end
40    end
41    copy
42  end
43
44  def rotate_image(image)
45    image.reverse!.transpose
46  end
47
48  def reverse(image)
49    head = 0
50    tail = image.size - 1
51
52    until head == tail || head > tail
53      image[head], image[tail] = image[tail], image[head]
54      head += 1
55      tail -= 1
56    end
57    image
58  end
59
60  def transpose(image)
61    copy = Array.new(image[0].size) { Array.new }
62    i = 0
63    until image.empty?
64      image.each do |row|
65        copy[i].push(row.shift)
66      end
67      i += 1
68      break if i == image.size
69    end
70    copy
71  end
72
73  def rotate_image(image)
74    transpose(reverse(image))
75  end
76
77  def rotate_image(image)
78    image.reverse!
79    (0...image.size).each do |i|
80      (i + 1...image.size).each do |j|
81        image[i][j], image[j][i] = image[j][i], image[i][j]
82      end
83    end
84    image
85  end
86
87  [
88    { a: [[1,2,3], [4,5,6], [7,8,9]], x: [[7,4,1], [8,5,2], [9,6,3]] },
89    { a: [[1]], x: [[1]] },
90    { a: [[10,9,6,3,7], [6,10,2,9,7], [7,6,3,8,2], [8,9,7,9,9], [6,8,6,8,2]], x: [[6,8,7,6,10], [8,9,6,10,9], [6,7,3,2,6], [8,9,8,9,3], [2,9,2,7,7]] },
91    { a: [[40,12,15,37,33,11,45,13,25,3], [37,35,15,43,23,12,22,29,46,43], [44,19,15,12,30,2,45,7,47,6], [48,4,40,10,16,22,18,36,27,48], [45,17,36,28,47,46,8,4,17,3], [14,9,33,1,6,31,7,38,25,17], [31,9,17,11,29,42,38,10,48,6], [12,13,42,3,47,24,28,22,3,47], [38,23,26,3,23,27,14,40,15,22], [8,46,20,21,35,4,36,18,32,3]], x: [[8,38,12,31,14,45,48,44,37,40], [46,23,13,9,9,17,4,19,35,12], [20,26,42,17,33,36,40,15,15,15], [21,3,3,11,1,28,10,12,43,37], [35,23,47,29,6,47,16,30,23,33], [4,27,24,42,31,46,22,2,12,11], [36,14,28,38,7,8,18,45,22,45], [18,40,22,10,38,4,36,7,29,13], [32,15,3,48,25,17,27,47,46,25], [3,22,47,6,17,3,48,6,43,3]] },
92    { a: [[33,35,8,24,19,1,3,1,4,5], [25,27,40,25,17,35,20,3,19,3], [9,1,9,30,9,25,32,12,15,22], [30,47,25,10,18,1,19,17,43,17], [40,46,42,34,18,48,29,40,31,39], [37,42,37,19,45,1,4,46,48,13], [8,26,31,46,44,24,34,29,12,25], [45,48,36,12,33,12,4,45,22,37], [33,15,34,25,34,8,50,48,30,28], [18,19,22,29,15,43,38,30,8,47]], x: [[18,33,45,8,37,40,30,9,25,33], [19,15,48,26,42,46,47,1,27,35], [22,34,36,31,37,42,25,9,40,8], [29,25,12,46,19,34,10,30,25,24], [15,34,33,44,45,18,18,9,17,19], [43,8,12,24,1,48,1,25,35,1], [38,50,4,34,4,29,19,32,20,3], [30,48,45,29,46,40,17,12,3,1], [8,30,22,12,48,31,43,15,19,4], [47,28,37,25,13,39,17,22,3,5]] }
93  ].each do |x|
94    it do
95      expect(rotate_image(x[:a])).to eql(x[:x])
96
97    end
98  end
99end