Thursday, 9 July 2009

Nearly rotating a 2-dimensional array in Java

I had a 2-dimensional array in a java program and I needed to rotate the structure of that array and place the elements of the array in a specific order, I'll illustrate what I mean with the following illustration:

+----+----+----+
|1,1 |1,2 |1,3 |
|   A|   B|   C|
+----+----+----+
|2,1 |2,2 |2,3 |
|   X|   Y|   Z|
+----+----+----+

So you can see the above as an egg box. I've got six hens you see and one day those six hens lay two eggs each... the poor bloody chickens haven't got nice names but instead have the names "A", "B", "C", "X", "Y" and "Z". So I've got twelve eggs and I've placed one of each of those hens eggs in an egg box like in the illustration above, I place the remaining six eggs in another egg box like in the following illustration:

+----+----+
|1,1 |1,2 |
|   A|   X|
+----+----+
|2,1 |2,2 |
|   B|   Y|
+----+----+
|3,1 |3,2 |
|   C|   Z|
+----+----+

There we have the illustrations and I knew that I'd need to use two loops to populate the new array but how?

I spent about 3 hours thinking about it and playing with possible solutions without really knowing what I was doing... thought it might be something like SVG matrix calculations and started to get even more confused until I sat down with a bit of paper... Imagine, if you will, that you need to describe to someone the placement of the eggs in the two boxes.

Because we're human we'd spend ages saying things like, "Put the first B egg in the top middle hole in the top box and the left-hand middle hole in the bottom box." Should the boxes get bigger... something like:

+----+----+----+----+
|    |    |    |    |
|    |    |    |    |
+----+----+----+----+
|    |    |XXXX|    |
|    |    |XXXX|    |
+----+----+----+----+
|    |    |    |    |
|    |    |    |    |
+----+----+----+----+

THen things get a little more complicated and we might decide to tell the other person what we mean by saying, "Put it in the hole two down and three across".

This is how we navigate a 2 dimensional array in fact; if we had a Java array like in the big egg box above we'd get to the big red "X" egg by saying bigBox[1][2] (don't forget that we're starting counting from 0 rather than 1).

Anyway, something interesting happens if we write down the places of each egg in each box:

    | BOX1 -- BOX2
----+------------- 
A = | 1,1 -or- 1,1
B = | 1,2 -or- 2,1
C = | 1,3 -or- 3,1
X = | 2,1 -or- 1,2
Y = | 2,2 -or- 2,2
Z = | 2,3 -or- 3,2

And what do we notice? Sometimes it takes a pen and paper to get to the right answer... either that or a cycle ride with a nine-year-old who's rather smart!

So we get the following method:

  public static char[][] rotateArray(char[][] incoming){
    int width = incoming.length;
    int height = incoming[0].length;
    char[][] outgoing = new char[height][width];
    for(int x = 0; x < incoming.length; x++){
      for(int y = 0; y < incoming[0].length; y++){
        outgoing[y][x] = incoming[x][y];
      }
    }
    return outgoing;
  }

I did look at these two pages: http://blogs.msdn.com/oldnewthing/archive/2008/09/02/8918130.aspx and http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx. Of the two the latter is the better I think... at least in terms of me thinking about the problem and prompting me to get my finger out.