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[3], ref array[15]);
  swap(ref array[0], ref array[3]);
  swap(ref array[0], ref array[12]);

  // left inner (2 moves around)
  swap(ref array[7], ref array[14]);
  swap(ref array[1], ref array[7]);
  swap(ref array[1], ref array[8]);

  // right inner (3 moves around)
  swap(ref array[11], ref array[13]);
  swap(ref array[2], ref array[11]);
  swap(ref array[2], ref array[4]);

  // middle square (6,7,10,11)
  swap(ref array[5], ref array[9]);
  swap(ref array[6], ref array[10]);
  swap(ref array[6], ref array[9]);
}

private static void swap(ref int a, ref int b)
{
  a ^= b;
  b ^= a;
  a ^= b;
}