Hi Mukesh and everybody I find Spiral Structures interesting because they map locations in the 2D spiral (square matrix) to indices of an unwrapped 1D vector. The vector elements can be used to store anything, reals for example. Because it is linear, it can be expanded without moving data in a complex pattern and with any luck not at all.
Duncan Muirhead posted a neat (x, y)-> n solution in http://groups.google.co.in/group/comp.programming/browse_frm/thread/4a06904cbbd7c2d3/2ebddd5b2c138f6a?tvc=1#2ebddd5b2c138f6a A slightly more computationally efficient solution (bigger code but fewer instructions executed for any case) is available. It can be got by considering the relevant layer of the spiral divided into quadrants TL, TR, BL, BR, and using the diagonal of even squares for locations including TR*, but not TR, to compute an included corner value C. The odd squares diagonal gets TR and (0, 0). x < 0, y >= 0 x >= 0, y > 0 TL TL TL TR TR TR TR TL 21 22 23 24 25 TR* TL 20 7 8 9 10 TR* TL 19 6 1 2 11 BR BL 18 5 4 3 12 BR BL 17 16 15 14 13 BR BL BL BL BL BR BR BR x <= 0, y < 0 x > 0, y <= 0 Doing it this way eliminates using Abs( )and a few multiplications although this last may not be obvious. With compiler optimization turned on (2*k) for example, only gets computed once in each line: unsigned __fastcall Ix_from_coords( int x, int y) { int k; unsigned C; if ((x > 0) && (y <= 0)) { k = max(x,-y); C = (2*k)*(2*k)-(2*k)+1; if (x == k) return C - k - y; else return C + k - x; } if ((y < 0) && (x <= 0)) { k = max(-x,-y); C = (2*k)*(2*k)+1; if (x == -k) return C + k + y; else return C - k - x; } if ((x < 0) && (y >= 0)) { k = max(-x,y); C = (2*k)*(2*k)+(2*k)+1; if (x == -k) return C - k + y; else return C + k + x; } k = max(x,y); if (y==k) return (2*k+1)*(2*k+1) - k + x; else { return (2*k)*(2*k)-(2*k)+1 - k - y; } } Instructions executed compared with Duncan's solution are 66%, 74%, 81%, 85% for the corner locations BR, TR, BL, BR respectively. An assembler function with only a single query of x and y status and a jump table would level the playing field but this will have to wait for a practical application. My solution for the inverse function is: SpiralCoords[ n ] -> (x, y) r := sqrt(n); ~ square root m := next odd m >= r. p := m * m; ~ odd square on diagonal d := m - 1; ~ height, width of these cols, rows hd := d / 2; if (n >= p-d) ~ top row return (n - p + hd, hd); p := p - d; if (n >= p-d) ~ left col. return (-hd, n - p + hd); p := p - d; if (n >= p-d) ~ bottom row return (n - p - hd, -hd); ~ right col return (hd, p - d - n - hd); end SpiralCoords; I have tested these functions on a 32bit system and they give correct results with a spiral n of (2^15 + 1)^2 = 1073807361 ->(16384, 16384). (-16384, -16384)-> 1073741825 and (1073807361 - 1073741825) = 65536, (2^16), which has got to mean something - like it works maybe. Cheers, Martin On Oct 18, 9:54 am, mukesh tiwari <[EMAIL PROTECTED]> wrote: > Hello everybody , i am trying to solve this(http://online- > judge.uva.es/ p/v9/903.html) problem and input constrants are such > that it is not > possible to store the the numbers in the array and print those > numbers. So i use the algorithm > > 1)get the number and return its coordinate > 2) take the input all adjacent coordiantes and return the number > belonging to that coordinate . > > i am facing the problem in second part that is if i have given > coordiante how to get the number belonging to that coordinate, > > lets consider the spiral > > 21 22 23 24 25 26 > 20 7 8 9 10 > 19 6 1 2 11 > 18 5 4 3 12 > 17 16 15 14 13 > > let the coordinate of 1 is (0,0) ie origin then coordinate of 11 > will > be (2,0) and so on . > now my problem is if i give coordiante (2,-1) then my program should > return 12 . > > thnkx in advance --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
