Traversing an array spirally

Discussion in 'C Programming' started by Praveen, Feb 2, 2008.

  1. Praveen

    Praveen Guest

    Hi,

    I would like to know how to traverse an array spirally?
    i.e if I have an array as follows

    1 2 3 4
    5 6 7 8
    9 10 11 12

    I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

    Please help
    Praveen, Feb 2, 2008
    #1
    1. Advertising

  2. "Praveen" <> wrote in message
    news:...
    > Hi,
    >
    > I would like to know how to traverse an array spirally?
    > i.e if I have an array as follows
    >
    > 1 2 3 4
    > 5 6 7 8
    > 9 10 11 12
    >
    > I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.


    Is this homework?
    Chris Thomasson, Feb 2, 2008
    #2
    1. Advertising

  3. Praveen

    Bartc Guest

    "Praveen" <> wrote in message
    news:...
    > Hi,
    >
    > I would like to know how to traverse an array spirally?
    > i.e if I have an array as follows
    >
    > 1 2 3 4
    > 5 6 7 8
    > 9 10 11 12
    >
    > I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.
    >
    > Please help


    Interesting exercise. But not really specific to C except array bounds have
    to start at 0.

    This is my effort. Probably some clever logic needed but I found it easier
    to use a map of 1s and 0s to indicate which array elements have been
    visited.

    Ints m and n have the array dims hardcoded. Dynamic bounds are a little more
    involved.

    BTW I'm new to C so if this is homework... don't rely on this!

    Bart


    #include <stdio.h>
    #include <stdlib.h>

    int main(void)
    {
    int m=8,n=6;
    int x[n][m];
    int map[n][m];
    int i,j,k,c,l,count,total,dir;

    k=1;
    c=1;
    l=1;

    /* print array grid */
    while (1)
    { printf("%3d",k);
    ++k;
    ++c;
    if (c>m)
    {
    printf("\n");
    c = 1;
    ++l;
    if (l>n) break;
    }
    }

    printf("\n");

    /* Set up map of 1's for each array element */
    k = 1;
    for (j=0; j<n; ++j)
    for (i=0; i<m; ++i)
    {
    x[j] = k++; /* the grid */
    map[j] = 1; /* the map */
    };


    /* now search clockwise spiral */
    i = 0;
    j = 0;
    dir = 'R'; /* One of 4 directions R D L U */
    total = m*n;
    count = 0;

    while (1)
    {/*w1"*/

    printf(" %d",x[j]); /* output contents of this grid element */
    map[j] = 0; /* mark as visited */
    ++count;
    if (count==total) break;

    while (1)
    {/*w2*/
    switch (dir)
    {/*sw*/
    case 'R':
    if (i<(m-1) && map[j][i+1])
    {++i;
    goto endwhile; /* C can't use break out of 2 levels :) */
    }
    else
    dir = 'D';
    break;
    case 'D':
    if (j<(n-1) && map[j+1])
    {++j;
    goto endwhile;
    }
    else
    dir = 'L';
    break;
    case 'L':
    if (i>0 && map[j][i-1])
    {--i;
    goto endwhile;
    }
    else
    dir = 'U';
    break;
    case 'U':
    if (j>0 && map[j-1])
    {--j;
    goto endwhile;
    }
    else
    dir = 'R';
    break;
    }; /*sw*/
    }; /*w2*/
    endwhile:;

    }; /*w1*/

    printf("\n");
    }
    Bartc, Feb 2, 2008
    #3
  4. Praveen

    santosh Guest

    Praveen wrote:

    > Hi,
    >
    > I would like to know how to traverse an array spirally?
    > i.e if I have an array as follows
    >
    > 1 2 3 4
    > 5 6 7 8
    > 9 10 11 12
    >
    > I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.
    >
    > Please help


    In addition to the other responses I also recommend that you do a search
    of Google Groups' archive of comp.lang.c. This is a fairly regular
    homework problem and there have been many good answers given over the
    years.
    santosh, Feb 2, 2008
    #4
  5. Praveen

    yeti Guest

    On Feb 2, 6:51 pm, Praveen <> wrote:
    > Hi,
    >
    > I would like to know how to traverse an array spirally?
    > i.e if I have an array as follows
    >
    > 1 2 3 4
    > 5 6 7 8
    > 9 10 11 12
    >
    > I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.
    >
    > Please help


    Hmm I guess this is not s C question, but anyway this is my strategy

    strategy 1

    1. print first line
    2. remove first line
    3. take transpose of matrix
    4 go to step 1 till matrix is not empty

    strategy 2

    assuming a function printcircle(mat) that prints boundary circle of a
    matrix beginning at first element
    i=0,j=0
    1. printcircle(&(mat[j]))
    2. i++,j++
    3. goto step 1 till matrix is not empty
    yeti, Feb 2, 2008
    #5
  6. Praveen

    Randy Howard Guest

    On Sat, 2 Feb 2008 10:07:27 -0600, santosh wrote
    (in article <fo23pf$3ea$>):

    > Praveen wrote:
    >
    >> Hi,
    >>
    >> I would like to know how to traverse an array spirally?
    >> i.e if I have an array as follows
    >>
    >> 1 2 3 4
    >> 5 6 7 8
    >> 9 10 11 12
    >>
    >> I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.
    >>
    >> Please help

    >
    > In addition to the other responses I also recommend that you do a search
    > of Google Groups' archive of comp.lang.c. This is a fairly regular
    > homework problem and there have been many good answers given over the
    > years.
    >


    Yes, by all means, help make sure that he doesn't accidentally learn
    anything during this or any other course. We need more college grads
    that don't understand the material on their diploma.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
    Randy Howard, Feb 2, 2008
    #6
  7. "Chris Thomasson" <> wrote in message
    news:p...
    >
    > "Praveen" <> wrote in message
    > news:...
    >> Hi,
    >>
    >> I would like to know how to traverse an array spirally?
    >> i.e if I have an array as follows
    >>
    >> 1 2 3 4
    >> 5 6 7 8
    >> 9 10 11 12
    >>
    >> I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

    >
    > Is this homework?


    If it is, go ahead and post your solution before you turn it in. Only then
    can we give you some "pointers" to help you out some... Think about it: Do
    the work, and ask for some clues on how you can make a possible improvement.
    IMHO, that's okay; just don't ask us to do it all for you... That would mean
    you did not learn; which is BAD!

    Also, ask your professor for tips and tricks; do NOT be afraid/intimidated
    to ask for help!!!
    Chris Thomasson, Feb 4, 2008
    #7
  8. Praveen

    Army1987 Guest

    yeti wrote:

    > On Feb 2, 6:51 pm, Praveen <> wrote:
    >> I would like to know how to traverse an array spirally?

    [snip]
    > Hmm I guess this is not s C question, but anyway this is my strategy
    >
    > strategy 1
    >
    > 1. print first line
    > 2. remove first line
    > 3. take transpose of matrix
    > 4 go to step 1 till matrix is not empty

    An O(n**4) strategy where the most naive one is O(n**2)?
    > strategy 2
    >
    > assuming a function printcircle(mat) that prints boundary circle of a
    > matrix beginning at first element
    > i=0,j=0
    > 1. printcircle(&(mat[j]))

    How do you implement printcircle?
    > 2. i++,j++
    > 3. goto step 1 till matrix is not empty




    --
    Army1987 (Replace "NOSPAM" with "email")
    Army1987, Feb 5, 2008
    #8
  9. Praveen

    user923005 Guest

    On Feb 2, 5:51 am, Praveen <> wrote:
    > Hi,
    >
    > I would like to know how to traverse an array spirally?
    > i.e if I have an array as follows
    >
    > 1   2   3  4
    > 5   6   7  8
    > 9   10 11 12
    >
    > I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.



    Your question is more appropriate on news:comp.programming.

    In order to solve it, ask yourself how you would solve it with pencil
    and paper.
    It appears that you would traverse the top and edges and then
    increment or decrement the edge as appropriate and then repeat until a
    dimension is zero.

    Try it symbolically with this matrix that has m rows and n columns:

    {col 0} {col 1} {col n-1} {col n}
    [A(0,0)] [A(0,1)] ... [A(0,n-1)] [A(0,n)] {row 0}
    [A(1,0)] [A(1,1)] ... [A(1,n-1)] [A(1,n)] {row 1}
    ...
    [A(m-1,0)][A(m-1,1)]... [A(m-1,n-1)][A(m-1,n)] {row m-1}
    [A(m,0)] [A(m,1)] ... [A(m,n-1)] [A(m,n)] {row m}

    Once you figure out how you would do it using two indexes i and j on
    paper, do exactly the same thing using C.
    user923005, Feb 6, 2008
    #9
  10. Praveen

    yeti Guest

    On Feb 6, 1:24 am, Army1987 <> wrote:
    > yeti wrote:
    > > On Feb 2, 6:51 pm, Praveen <> wrote:
    > >> I would like to know how to traverse an array spirally?

    > [snip]
    > > Hmm I guess this is not s C question, but anyway this is my strategy

    >
    > > strategy 1

    >
    > > 1. print first line
    > > 2. remove first line
    > > 3. take transpose of matrix
    > > 4 go to step 1 till matrix is not empty

    >
    > An O(n**4) strategy where the most naive one is O(n**2)?> strategy 2
    >
    > > assuming a function printcircle(mat) that prints boundary circle of a
    > > matrix beginning at first element
    > > i=0,j=0
    > > 1. printcircle(&(mat[j]))

    >
    > How do you implement printcircle?
    >
    > > 2. i++,j++
    > > 3. goto step 1 till matrix is not empty

    >
    > --
    > Army1987 (Replace "NOSPAM" with "email")


    here is the complete program (not tested)

    #include <stdio.h>
    #define COLS 6
    #define ROWS 6

    int array[ROWS][COLS]=
    {{1 ,2 ,3 ,4 ,5 ,6 },
    {7 ,8 ,9 ,10,11,12},
    {13,14,15,16,17,18},
    {19,20,21,22,23,24},
    {25,26,27,28,29,30},
    {31,32,33,34,35,36}
    };

    void printcircle(int map_ptr[][COLS], int rows, int cols)
    {
    int j=0;
    if(rows<1 || cols <1)
    {
    return;
    }
    for(j=0; j<cols; j++)
    {
    printf("%d->", map_ptr[0][j]);
    }

    for(j=1; j<rows; j++)
    {
    printf("%d->", map_ptr[j][cols-1]);
    }
    for(j=cols-2; j>=0; j--)
    {
    printf("%d->", map_ptr[rows-1][j]);
    }
    for(j=rows-2; j>=1; j--)
    {
    printf("%d->", map_ptr[j][0]);
    }

    }


    int main()
    { int rows=ROWS,cols=COLS,i=0;

    while(rows>0&&cols>0)
    {
    printcircle((int(*)[])&array,rows,cols);
    rows-=2;
    cols-=2;
    i++;
    }
    getchar();
    return 0;
    }
    yeti, Feb 10, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. steven
    Replies:
    6
    Views:
    900
    steven
    Aug 27, 2003
  2. Asad

    XML - traversing in VB

    Asad, Apr 16, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    572
    Matt Berther
    Apr 16, 2004
  3. wallacej

    Traversing a 2D array

    wallacej, Feb 1, 2006, in forum: C++
    Replies:
    7
    Views:
    511
    wallacej
    Feb 1, 2006
  4. TonyShirt

    traversing array slices

    TonyShirt, Feb 27, 2004, in forum: Perl Misc
    Replies:
    4
    Views:
    156
    valued customer
    Feb 28, 2004
  5. Bryan
    Replies:
    6
    Views:
    198
    -berlin.de
    Apr 11, 2007
Loading...

Share This Page