-1

I need to flip a 1-D 64-element array of shorts (I can switch to ints if it's easier, but I assume the same processes will work for either) on it's head in Java. I represent it here as a square table for ease of understanding, since the actual problem is on a chessboard.

For example:

short[] example = new short[]
{
    1, 2, 3,
    4, 5, 6,
    7, 8, 9
};

would become:

7 8 9
4 5 6
1 2 3

Please note that this is NOT the same as reversing the array (every answerer to similar questions I have found has made this mistake, hence my having to ask!). Reversing the array would give:

9 8 7
6 5 4
3 2 1

Apologies if I've missed any important info, any help is appreciated!

EDIT: The array is 1D and contains 64 elements, so short[64], and the reversed array is separate to the original. As far as what I've tried, I'm just struggling to wrap my head around it. I know how to reverse the array, but that's not what I'm after, and I had originally tried to reverse the index using:

byte index = (byte)(((byte)(position + 56)) - (byte)((byte)(position / 8) * 16));

Which is a code snippet I found on Chessbin, but this returns incorrect values and gives IndexOutOfBounds errors. In hindsight it's not clear to me if that code is meant to flip the index or reverse it. Since maths is not my strong suit, I tried to work around it with separate arrays.

Andy Thomas
  • 84,978
  • 11
  • 107
  • 151
Heydiddly
  • 77
  • 1
  • 8
  • 12
    You've missed what you have tried – Alexis C. May 13 '13 at 18:07
  • 3
    What does this array look like in code? Is it `short[][]`? Have you tried anything yet? Was there an error? – thegrinner May 13 '13 at 18:08
  • 1
    Is this a multidimensional array ? – Adarsh May 13 '13 at 18:09
  • 3
    Is this a 2D array? Otherwise I don't see how you would know where to start `flipping` the array... – SOfanatic May 13 '13 at 18:10
  • Knew I'd miss something, sorry... I will update the OP, bear with me. – Heydiddly May 13 '13 at 18:17
  • 1
    Why not use a multidimensional array for this? How do you know how many "rows" there should be (I know it is probably 8, but is this always the case)? – MAV May 13 '13 at 18:40
  • I think a multidimensional array will make it easier to swap around the rows, too. The math would be pretty minimal, as you'll just be swapping row references, instead of every individual spot. – ajp15243 May 13 '13 at 18:41
  • Thanks for your patience with my edit. These arrays are used in a chess move evaluation function, and are thus accessed many thousands of times, so efficiency is important. My (probably misguided) understanding is that multi-dimensional arrays are slower to access, so I used a single 64x1 array since there will always effectively be 8 rows and 8 columns. If I'm wrong though, I'll have a go with an 8x8 array instead and see what I come up with. Thanks! – Heydiddly May 13 '13 at 18:47
  • There's a decent answer [here](http://stackoverflow.com/questions/2512082/java-multi-dimensional-array-vs-one-dimensional) about efficiency of a 1D array vs a 2D array. Since your 2D array would be a (relatively) measely 8x8 in size, I don't think much meaningful or noticeable efficiency is going to be gained by moving to a single 64-element array. Also, you should read a bit about [premature code optimization](http://programmers.stackexchange.com/questions/45259/is-premature-optimization-always-bad) (i.e. don't optimize until after things are written and working). – ajp15243 May 13 '13 at 18:54
  • Both interesting reads, particularly the one about premature code optimisation, will definitely bear in mind for the future, thanks! – Heydiddly May 13 '13 at 19:27

2 Answers2

2

My proposal would be like this:

public class Flipper {

    public short[] flip(short[] array, int columns) {
        short[] flipped = new short[array.length];
        for(int i=0;i<array.length;i++){
            int row = (i/columns); //use the fact that integer/integer is rounded down
            int column = (i%columns);
            flipped[i] = array[array.length-((columns*(row+1))-column)];
        }
        return flipped;
    }

}

Which can be tested with:

public class FlipperTest {

    private Flipper flipper = new Flipper();

    @Test
    public void test() {
        short[] array = new short[]{1,2,3,4,5,6,7,8,9};
        short[] actualResult = flipper.flip(array, 3);
        assertThat(actualResult, equalTo(new short[]{7,8,9,4,5,6,1,2,3}));
    }

}

Hope the code is self-explanatory

makasprzak
  • 5,082
  • 3
  • 30
  • 49
  • 1
    +1 for a solution with single loop. Not in-place, but could easily be made in-place. Less readable for me. Note: "row" is 1-based while "column" is 0-based; that merits some mention in the code, preferably in the variable name, or at least in-line documentation. – Andy Thomas May 13 '13 at 19:34
  • @Andy Thomas-Cramer - Agree, answer improved – makasprzak May 13 '13 at 19:51
1

You have a physical 1D array representing a logical 2D array, and you want to swap rows. You can do this partly by mapping 2D array indices into a 1D array index.

Let height be the number of rows, and width be the number of columns.

for ( int i = 0; i < height/2; ++i ) {
    int k = height - 1 - i;
    for ( int j = 0; j < width; ++j ) {
        short temp = array[i * width + j];
        array[i * width + j] = array[k * width + j];
        array[k * width + j] = temp;
    }
}

I've written this for readability. You or the compiler may optimize some of the repeated computations.

You might be able to optimize further by using a 2D array, which would allow you to swap references to rows in O(height), rather than copying all the rows in O(height * width).

Andy Thomas
  • 84,978
  • 11
  • 107
  • 151