ArrayList of Arrays & "Array.rotate()"

Newbie & Debugging Questions
#1

(1)
I would like to access the first element of an ArrayList of Arrays:
ArrayList<int[]> MyArrayListOfArrays = new ArrayList<int[]>();

int value = (MyArrayListOfArrays.get(0))[0];
Would that work?

(2)
I have to rotate an array.

Example:
{1,2,3,4}
{2,3,4,1}
{3,4,1,2}
{4,1,2,3}

Any suggestions, please?

#2

(1)
Yes.

(2)
This algorithm can rotate 2D-arrays with odd dimensions (1x1, 3x3, 5x5 etc). Rotating counter-clockwise is the same as rotating clockwise three times.


    private static char[][] rotateRight(char[][] x) {
        char[][] rotated = new char[x.length][x.length];
        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < x[i].length; j++) {
                rotated[j][(x.length - 1) - i] = x[i][j];
            }
        }
        return rotated;
    }

For rotating a 4x4 array you might need a different algorithm, but you can find the right algorithm yourself. First write a unit test for 2x2 rotation and then write code which passes the test. Then write a test for 4x4 rotation, make it pass, and the algorithm should be complete (if you like, you can write one more test for 6x6 just to make sure that it passes).

The trick is that you figure out (on pen and paper) how the coordinates of each element change. Here are the notes which I made when writing the above code.


Coordinates when rotating a 3x3 grid right:

before   after
0-0      0-2
0-1      1-2
0-2      2-2
1-0      0-1
1-1      1-1
1-2      2-1
2-0      0-0
2-1      1-0
2-2      2-0

Coordinates when rotating a 5x5 grid right:

before   after
0-0      0-4
0-1      1-4
0-2      2-4
0-3      3-4
0-4      4-4
1-0      0-3
1-1      1-3
1-2      2-3
1-3      3-3
1-4      4-3
...

Do you notice a pattern?

#3

[quote=“Aoshi,post:1,topic:32267”]
This might work:

public int[] rotateLeft(int[] input)
{
    int[] output = new int[input.length];
    System.arrayCopy(input, 1, output , 0, input.length-1);
    output[input.length-1] = input[0];
    return output;
}
#4

Yeah, I also though he meant 1D rotation, like bit shifting, not 2D.

I’d prefer a copy-less function though…


public void rotateLeft(int[] arr)
{
   int tmp = arr[0];
   for(int i=1; i<arr.length; i++)
      arr[i-1] = arr[i];
   arr[arr.length-1] = tmp;
}
#5

So it seems. I had just some time ago been writing a tetris clone, so 2D rotation was the first thing which came into my mind. I interpreted his example as a 4x4 matrix instead of an 1x4 array with 4 states. :-X

#6

isn’t that unboxing going to bite you?

#7 
public int[] rotateLeft(int[] input)
{
    int tmp = input[0];
    System.arraycopy(input, 1, input, 0, input.length-1);
    input[input.length-1] = tmp;
    return output;
}

The specification is unclear whether or not that will copy the data or not, it just says it’s done “as if” the data was copied, but that code is more than twice as fast as yours in the test run I did. (an int[100000] rotated (in place) 10000 times via a call to a static method)

#8

I’d find out whether his arrays are going to be variable in size or not. If they’re all coming with a length of 4, why the need for all the hassle? Just index the array directly with indexes 0 through 3. Then you won’t have to worry about the overhead of looping or possible array copies.

#9 
public void rotateLeft(int[] arr)
{
   int tmp = arr[0];
   for(int i=1; i<arr.length; i++)
      arr[i-1] = arr[i];
   arr[arr.length-1] = tmp;
}

This is exactly what I was looking for. Thank you very much. And sorry for the ambiguous example…