Calling all algorithm lovers!

July 15, 2009 3:36 PM

I need help solving an interesting algorithm using 'C'!

Say for example, I have a daisy chain laid out like this which snakes from 0 to 15:

15 14 13 12
08 09 10 11
07 06 05 04
00 01 02 03

I know the height and width ahead of time (4x4), but I want to know what index of the daisy chain corresponds to a certain (x,y) coordinate.

If I want the index of coordinate (1,2), I would get 9.
If I want the index of coordinate (3,1), I would get 4.
If I want the index of coordinate (3,3), I would get 12.
etc...

Using 'C' I envision it something like this:


#define WIDTH 4
#define HEIGHT 4

Index = CalculateIndex(WIDTH, HEIGHT, 1, 2);
//Index should be equal to 9.



What's inside CalculateIndex?

posted by niwnfyc to computers & internet (6 comments total)

int CalculateIndex(int w, int h, int x, int y) {
    if (y % 2 == 0) {
        return y * w + x;
    } else {
        return (y + 1) * w - x - 1;
    }    
}

posted by Emanuel at 3:52 PM on July 15 [1 favorite]

So it's always starts at zero and is sequential, starting from the highest number?
posted by notsnot at 3:53 PM on July 15

Suppose that instead of your array, it looked like

12 13 14 15
08 09 10 11
04 05 06 07
00 01 02 03

the element at location (i, j) will be (j * WIDTH) + i, right?

The only difference between your case and the one I described is that some of your rows (every other one) go backwards. If the row goes backwards, that is the equivalent of indexing into (WITDHT - 1 - i)th element of the forward row, right?

So, the algorithm will have to check whether height is even or odd, and adjust accordingly.
posted by bsdfish at 3:58 PM on July 15

I believe emmanuel has it, provided the numbers are always in sequence and start from zero. And possibly only if it's square.

I'm really curious what the application for this is...?
posted by gjc at 5:06 PM on July 15

Thanks Emanuel!

@gjc: I'm designing a light rope with individually controlled LEDs, and my idea is to snake the rope back and forth into a big square on my wall. I then have a very rudimentary "screen" which I can use to play animations. I can now treat this big string of LEDs as a square screen and design animations using (x,y) coordinates. For example, if I wanted the top right LED to turn on (3,3), I can now use this function to tell the LED at index 12 to turn on.
posted by niwnfyc at 5:25 PM on July 15

There is also a single-statement testless version:
y*w + x + (y&1)*(w-2*x-1)

or use y%2= y&1 for the all-arithmetic statement
posted by hexatron at 6:54 PM on July 15