Sunday, September 14, 2008

Rotating an array

Over at polymathprogrammer there is an article about rotating an array, which was a response to Mr Chen's entry on an interview question

Reading the answers got me thinking as I had recently written a roate method in order in implement tic-tac-toe (don't ask why). My solution then had been along the lines of one of the suggested solutions:

`for (int y = 0; y < n; y++)  for (int x = 0; x < n; x++)    output[n - y - 1,x] = input[x,y];`

though I used a mapping intead of a direct move.

What was interesting was that someone else had suggested that you could just do it using two mirror operations (mirror horizontal and then a diagonal) which was a very elegant way of doing it.

I liked this and it made me think was there another way to do it (as in how many ways can this problem be solved. And I came up with this, which takes advantage of using a single dimension array for holding two dimensional data:

`1 &124; 2 &124; 3-----------4 &124; 5 &124; 6-----------7 &124; 8 &124; 9`

stored as

`int[] array = new int[] { 1, 2, 3, 4 , 5, 6, 7, 8, 9};`

which if rotated looks likes:

`int[] array = new int[] { 7, 4, 1, 8, 5, 2, 9, 6, 3};`

which looks like the mapping:

`destinationOffset += w;if (destinationOffset > l)  destinationOffset = destinationOffset % w;`

in effect, offset its new position by the width of the matrix (3) and wrap overflows back to the start. This looked good until number 4 as it collided with 1, so I just moved it back a step if it collided. Problem solved for 90° right:

gives:

`7 &124; 4 &124; 1-----------8 &124; 5 &124; 2-----------9 &124; 6 &124; 3`

Now you could just apply the function multiple times for 180°, 270° rotations, but looking at the resultant arrays shows two things:
180°: results is the original array in reverse order
270°: results is the 90° array in reverse order

So it looks like reversing an array is the same as a diagonal mirror! which means you need just two functions, a rotate and an array reverse (which is part of most array implementations, .Net as Arrray.Reverse)

Code for just the single rotation is:

`int size = 3*3;int[] array = new int[size];for (int i = 0; i < size; i++) array[i] = i + 1;int l = array.Length;int w = (int)Math.Sqrt(array.Length);int[] destination = Rotate(array, l, w);private static int[] Rotate(int[] array, int l, int w){  int[] destination = new int[l];  int destinationOffset = -1;  for (int sourceOffset = 0; sourceOffset < l; sourceOffset++)  {    destinationOffset += w;    // wrap around    if (destinationOffset > l)    {      destinationOffset %= w;      // collision avoidance      destinationOffset--;    }    destination[destinationOffset] = array[sourceOffset];  }  return destination;}`

and of course given we know the size of the array, and we can use XOR to do swaps in place
`swap(a, b) =>  a = a ^ b; // a^= b;  b = b ^ a; // b ^= a;  a = a ^ b; // a ^= b;`

then the fast version (without working at a bit level) might be:

`private static void RotateInPlace4by4(int[] array){  // corners (1,4 moves around)  swap(ref array, ref array);  swap(ref array, ref array);  swap(ref array, ref array);  // left inner (2 moves around)  swap(ref array, ref array);  swap(ref array, ref array);  swap(ref array, ref array);  // right inner (3 moves around)  swap(ref array, ref array);  swap(ref array, ref array);  swap(ref array, ref array);  // middle square (6,7,10,11)  swap(ref array, ref array);  swap(ref array, ref array);  swap(ref array, ref array);}private static void swap(ref int a, ref int b){  a ^= b;  b ^= a;  a ^= b;}`