Spiral Matrix

Two-dimensional arrays

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

41 Replies - 15639 Views - Last Post: 22 September 2010 - 01:12 PM Rate Topic: -----

#1 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Spiral Matrix

Posted 12 July 2010 - 11:35 PM

Write a program to print a spiral matrix of n X n order. Eg. if n=4:

1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

The code is wrote is following. It is for printing a spiral matrix when n=5. It gave a correct output only for the elements on the sides.


class spiral_matrix
{
public static void main()
{
int m[][] = new int [4][4];
int n=1, s=4, c=1, i=0, j=0;
while(n>=1)
{ 
do
{
m[i][j] = c++;
n++;
j++;
}
while(n<s);
n =  0;
do
{
m[i][j] = c++;
n++;
i++;
} 
while(n<s-1);
n = 0;
do
{
m[i][j]=c++;
n++;
j--;
}
while(n<s-1);
n = -1;
do
{
m[i][j] = c++;
n++;
i--;
}
while(n<s-2);
n = n - 2;
}
for(i=0; i<s; i++)
{
for(j=0; j<s; j++)
{
System.out.print(m[i][j] + " ");
}
System.out.println();
}
}
}




Is This A Good Question/Topic? 0
  • +

Replies To: Spiral Matrix

#2 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Spiral Matrix

Posted 12 July 2010 - 11:44 PM

While I take a look at your code, please take the time to indent code properly, it really makes it much easier to follow the code :)

Before I look any further, I must ask you this, as this is very important:

You stated the program should take an "n by n" matrix. Your program has an array of 4 x 4, which is not n x n. If your program is supposed to take an n by x matrix, i.e. prompt the user for the n x n specifics, your code is all wrong. If however, the code runner chooses the n x n and HARDCODES it, it is possible your code is right, BUT IT IS QUITE FOOLISH TO HARDCODE IT as I am quite sure your instructor wants a prompt for n by n.
Was This Post Helpful? 0
  • +
  • -

#3 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Spiral Matrix

Posted 13 July 2010 - 12:08 AM

The indented code:


class spiral_matrix
{
    public static void main()
    {
        int m[][] = new int [4][4];
        int n=1, s=4, c=1, i=0, j=0;
        while(n>=1)
        { 
            do
            {
                m[i][j] = c++;
                n++;
                j++;
            }
            while(n<s);
            n =  0;
            do
            {
                m[i][j] = c++;
                n++;
                i++;
            } 
            while(n<s-1);
            n = 0;
            do
            {
                m[i][j]=c++;
                n++;
                j--;
            }
            while(n<s-1);
            n = -1;
            do
            {
                m[i][j] = c++;
                n++;
                i--;
            }
            while(n<s-2);
            n = n - 2;
        }
        for(i=0; i<s; i++)
        {
            for(j=0; j<s; j++)
            {
                System.out.print(m[i][j] + " ");
            }
            System.out.println();
        }
    }
}




And yes, it's got to be n X n. The user should be prompted to input a number, which will be the array dimension n. But I made this code for a situation when n=5, will correct it.
Was This Post Helpful? 0
  • +
  • -

#4 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Spiral Matrix

Posted 13 July 2010 - 12:13 AM

Alright give me a few minutes.

Edit:

As I have already told you in your other post, the main method MUST have a String array to accept command-line args:

public static void main(String[] args)



How are you getting user input for n x n?

Have you covered the Scanner class to accept user input?

Edit: To make sure I understand right, can N x N refer to two different N's or do the N's have to be the same i.e. 2 x 2, 3 x 3, or is 3 x 7 legal?

This post has been edited by bcranger: 13 July 2010 - 12:26 AM

Was This Post Helpful? 0
  • +
  • -

#5 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Spiral Matrix

Posted 13 July 2010 - 12:27 AM

I provide input either by writing
 public static void main(int n) 
or by using
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); 


There is only one value for n; like 3 X 7 is invalid.

This post has been edited by adhish94: 13 July 2010 - 12:30 AM

Was This Post Helpful? 0
  • +
  • -

#6 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Spiral Matrix

Posted 13 July 2010 - 12:28 AM

Alright, that's good! I'll get back to this assignment after we've finished your other 1, jsut to stop from confusing ourselves.

Edit:
Go to your lucky number assignment first please. It is better to finish one assignment at a time rather than work on two simultaneously.

This post has been edited by bcranger: 13 July 2010 - 12:32 AM

Was This Post Helpful? 0
  • +
  • -

#7 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Spiral Matrix

Posted 13 July 2010 - 12:31 AM

Yeah, sure! :)
Was This Post Helpful? 0
  • +
  • -

#8 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Spiral Matrix

Posted 13 July 2010 - 01:41 AM

Although I have figured out a method to accomplish your spiral program, it does not use recursion :(

I am still trying to figure out how to recursively obtain the result, if possible. Interesting program we got here :bananaman:

Edit:

As it is now 4:00 a.m. here, I shall leave you to the best of luck on this assignment :D

I'm sorry but I can't post the code for this assignment as we haven't gone over it much.

But I can give you some advice:

- you want a variable to keep track of the current row/col
- you want a variable to keep track of which direction your going in your array (up,down,left,right)

I'm still not through with the recursive version but I'll try to figure that out tomorrow, if at all possible :donatello:

Edit:

Now 4:34 A.M. here...was so interesting I could not resist but work on the recursive method...victim of Java :surrender:

Anyways WOOOOOOOOOOOOOOOOOOT
:w00t:

FINALLY FIGURED IT OUT, SORRY FOR THE MESSED UP POST BUT I'M SO HAPPY I FINALLY FIGURED IT OUT (after 40min :( )

But anyways, soon as you post your changes, I'll be glad to help you with either nonrecursive or recursive!

I'm giddy I figured it out, even though it sounds stupid :D

This post has been edited by macosxnerd101: 13 July 2010 - 04:17 PM
Reason for edit:: Removed Excess O's so as not to break everyone's V-Scrolls

Was This Post Helpful? 0
  • +
  • -

#9 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Spiral Matrix

Posted 13 July 2010 - 04:15 PM

Very cute little program but your number od do while is directly related to the size of the square
a very bad hardcoded value
I would use a complete different approach something like

public class Spiral {

	Spiral(int dim) {
		int array[][] = new int[dim][dim];
		int x = 0, y = 0;
		int maxX = dim -1, maxY = dim-1;
		int minX = 0, minY = 0;
		int directionX = +1, directionY = 0;
		
		int n = 0;
		while(n < dim * dim)
		{
			array[x][y] = ++n;
			if(x == maxX && directionX == +1) {
				directionY = +1;
				directionX = 0;
				maxX--;
			}
			else if(x == minX && directionX == -1) {
				directionY = -1;
				directionX = 0;
				minX++;
			}
			else if(y == maxY && directionY == +1) {
				directionX = -1;
				directionY = 0;
				maxY--;
			}
			else if(y == minX && directionY == -1) {
				directionX = +1;
				directionY = 0;
				minY++;
			}
			x += directionX;
			y += directionY;
		}
		for(int i = 0; i < dim; i++) {
			for(int j = 0; j < dim; j++) {
				System.out.printf("%3d", array[i][j]);
			}
			System.out.println();
		}
		
	}
	public static void main(String[] args) {
		for(int i = 2; i < 6; i++)
			new Spiral(i);
	}
}


Not tested, no garanty just an idea
Was This Post Helpful? 0
  • +
  • -

#10 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Spiral Matrix

Posted 13 July 2010 - 04:32 PM

I believe nonrecursive wins this one :D

Here's my nonrecursive version:

public static void main(String[] args) 
  { 
    Scanner in = new Scanner(System.in);
    System.out.println("Enter n:");
    int n = in.nextInt();
    int a[][]=new int[n][n];
    int x = 1;
    for (int i = n - 1, j = 0; i > 0; i--, j++) 
    {
      for (int k = j; k < i; k++)
        a[j][k] = x++;
      for (int k = j; k < i; k++)
        a[k][i] = x++;
      for (int k = i; k > j; k--)
        a[i][k] = x++;
      for (int k = i; k > j; k--)
        a[k][j] = x++;
    } 
    if (n % 2 == 1)
      a[(n - 1) / 2][(n - 1)/2] = x++;
    for(int i = 0; i<n; i++)
    {
      for(int j = 0; j<n; j++)
        System.out.print(a[i][j] + " ");
      System.out.println();
    } 
  }



Here's my recursive version:

public static int[][] fillSpiral(int[][] n, int attempt, int start)
  {
    if(start == n.length * n[0].length + 1)
      return n;
    
    if(attempt % 4 == 1)
    {
      loop:
      for(int i = 0; i < n.length; i++)
        for(int j = 0; j < n[i].length; j++)
          if(n[i][j] == 0)
          {
            for(int k = j; k < n[i].length; k++)
              if(n[i][k] == 0)
                n[i][k] = start++;
            break loop;
          }
    }
    else if(attempt % 4 == 2)
    {
      loop:
      for(int i = 0; i < n.length; i++)
        for(int j = n[i].length - 1; j >= 0; j--)
          if(n[i][j] == 0)
          {
            for(int k = i; k < n.length; k++)
              if(n[k][j] == 0)
                n[k][j] = start++;
            break loop;
          }
    }
    else if(attempt % 4 == 3)
    {
      loop:
      for(int i = n.length - 1; i >= 0; i--)
        for(int j = n[i].length - 1; j >= 0; j--)
          if(n[i][j] == 0)
          {
            for(int k = j; k >= 0; k--)
              if(n[i][k] == 0)
                n[i][k] = start++;
            break loop;
          }
    }
    else if(attempt % 4 == 0)
    {
      loop:
      for(int i = n.length - 1; i >= 0; i--)
        for(int j = 0; j < n[i].length; j++)
          if(n[i][j] == 0)
          {
            for(int k = i; k >= 0; k--)
              if(n[k][j] == 0)
                n[k][j] = start++;
            break loop;
          }
    }
    
    return fillSpiral(n,attempt + 1,start);
  }


This post has been edited by bcranger: 13 July 2010 - 04:33 PM

Was This Post Helpful? 1
  • +
  • -

#11 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1940
  • View blog
  • Posts: 4,027
  • Joined: 11-December 07

Re: Spiral Matrix

Posted 13 July 2010 - 06:03 PM

My unreadable recursive code is shorter than your unreadable recursive code. :P

	public static int[][] spiral(int n) {
		return horizontal(new int[n][n], n, 0, 0, 1, 1);
		}
	
	private static int[][] horizontal(int[][] arr, int n, int x, int y, int dx, int counter) {
		if (n == 0) {return arr;}
		for(int i = 0; i < n; i++, x += dx, counter++) {
			arr[y][x] = counter;
			}
		return vertical(arr, n-1, x-dx, y+dx, dx, counter);
	}

	private static int[][] vertical(int[][] arr, int n, int x, int y, int dy, int counter) {
		if (n == 0) {return arr;}
		for(int i = 0; i < n; i++, y += dy, counter++) {
			arr[y][x] = counter;
			}
		return horizontal(arr, n, x-dy, y-dy, -dy, counter);
	}


This post has been edited by cfoley: 13 July 2010 - 06:04 PM

Was This Post Helpful? 1
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10392
  • View blog
  • Posts: 38,458
  • Joined: 27-December 08

Re: Spiral Matrix

Posted 13 July 2010 - 06:16 PM

@cfoley: You may consider submitting your solution as a snippet, with maybe a comment or two thrown in. :)
Was This Post Helpful? 0
  • +
  • -

#13 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1940
  • View blog
  • Posts: 4,027
  • Joined: 11-December 07

Re: Spiral Matrix

Posted 13 July 2010 - 06:19 PM

Are you suggesting I make that mess readable?
Was This Post Helpful? 0
  • +
  • -

#14 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Spiral Matrix

Posted 13 July 2010 - 06:21 PM

View Postmacosxnerd101, on 13 July 2010 - 07:16 PM, said:

@cfoley: You may consider submitting your solution as a snippet, with maybe a comment or two thrown in. :)

You mean with:
- a design document
- a proof of concept
- a pilot example
- a code review report
- a few comments in the code
- a Wikipedia article describing the algorithm
- a certified copy of the patent pending document

:)
+1 Jolly good show :^: but static is not OO you should have made a Spiral object

This post has been edited by pbl: 13 July 2010 - 06:24 PM
Reason for edit:: typo in static :D

Was This Post Helpful? 0
  • +
  • -

#15 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1940
  • View blog
  • Posts: 4,027
  • Joined: 11-December 07

Re: Spiral Matrix

Posted 13 July 2010 - 07:03 PM

Quote

but static is not OO you should have made a Spiral object


Quite right, but when I see the OP put the entire program in their main method, I prefer to take the smaller step of showing them a method.

Anyway, I submitted my unreadable, useless, non OO snippet. :)
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3