Velocity Reviews > Traversing an array spirally

# Traversing an array spirally

Praveen
Guest
Posts: n/a

 02-02-2008
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.

Chris Thomasson
Guest
Posts: n/a

 02-02-2008

"Praveen" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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?

Bartc
Guest
Posts: n/a

 02-02-2008

"Praveen" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.
>

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][i] = k++; /* the grid */
map[j][i] = 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][i]); /* output contents of this grid element */
map[j][i] = 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][i])
{++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][i])
{--j;
goto endwhile;
}
else
dir = 'R';
break;
}; /*sw*/
}; /*w2*/
endwhile:;

}; /*w1*/

printf("\n");
}

santosh
Guest
Posts: n/a

 02-02-2008
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.
>

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.

yeti
Guest
Posts: n/a

 02-02-2008
On Feb 2, 6:51 pm, Praveen <(E-Mail Removed)> 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.
>

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[i][j]))
2. i++,j++
3. goto step 1 till matrix is not empty

Randy Howard
Guest
Posts: n/a

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

> 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.
>>

>
> 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.

--
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Chris Thomasson
Guest
Posts: n/a

 02-04-2008

"Chris Thomasson" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
>
> "Praveen" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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
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

Army1987
Guest
Posts: n/a

 02-05-2008
yeti wrote:

> On Feb 2, 6:51 pm, Praveen <(E-Mail Removed)> 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[i][j]))

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

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

user923005
Guest
Posts: n/a

 02-06-2008
On Feb 2, 5:51*am, Praveen <(E-Mail Removed)> 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.

yeti
Guest
Posts: n/a

 02-10-2008
On Feb 6, 1:24 am, Army1987 <(E-Mail Removed)> wrote:
> yeti wrote:
> > On Feb 2, 6:51 pm, Praveen <(E-Mail Removed)> 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[i][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[i][i],rows,cols);
rows-=2;
cols-=2;
i++;
}
getchar();
return 0;
}