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;

}

## 1 comment:

if you are looking to shift or rotate a single dimension array see the post on http://blog.figmentengine.com/2008/10/rotating-string.html

Post a Comment