Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Grid algorithm not working properly

  1. #1
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Grid algorithm not working properly

    I'm trying to translate from pseudocode from a textbook into java, but it's not working, so I'm clearly doing something wrong. Before I show you my code, I think it's best I give you the text, so you know exactly what I'm trying to do.


    Let’s write down a more precise version of our algorithm:
    ALGORITHM GRID(n)
    The input will be a positive whole number.
    The output will be an n*n gridG. G[r,c] means the number in row r column c of the grid.
    The steps to be performed are:
    For each row r, numbered 1 up to n inclusive, and for each column c, numbered 1 up to n inclusive
    do this:
    Use algorithm GET-GRID-ENTRY to get the number m that we should fill into row r and column c of the grid G.
    Fill in m to G[r,c]

    This feels like cheating a little, we’ll need to specify what the GET-GRID-ENTRY algorithm is. Try that, in the more precise style we’ve just used for the GRID algorithm.

    ALGORITHM GET-GRID-ENTRY(G,n,r,c)
    The input will be a partially filled in grid G, n, the size of G, and two positive whole numbers r and c
    The output will be a single number m, that is the smallest number not appearing aboveG[r,c]in the same column, or to the left ofG[r,c]in the same row.
    The steps to be performed are:
    Let U be a piece of scratch space with n entries, with U[0,...,n] all zero.
    For each grid entry in row r, column i, with i ranging from1up to c-1 inclusive
    do this:
    Let x beG[r,i]
    SetU[x]to 1
    For each grid entry in column c row j, with j ranging from1up to r-1inclusive do this:
    Let y be G[j,c]
    SetU[y]to 1
    For each entry in U, numbered by k from 1 up to n inclusive
    do this:
    ifU[k]equals zero
    thenStop this algorithm, and give our answer as k.

    We now have a reasonably precise description of the algorithm to solve the grid problem.



    These two algorithms together are supposed to create a grid of size (n*n) where each cell in that grid is the smallest possible non-negative number not already to the left or directly above that cell. I can show some examples, if people think that will make it any clearer.

    Anyway, here is my attempt to code the algorithm(s)
    public class GRID {
    	public static void main(String[]args){
    		createGrid(4);
     
    	}
     
     
    	/**
    	 * Method for creating grid
    	 * @param n Size of grid
    	 */
    	public static void createGrid(int n){
     
    		//Initialize a grid of size n*n
    		int array[][] = new int[n][n];
     
     
    		for (int r=0;r<array.length;r++){
    			for (int c=0;c<array[r].length;c++){
    				//Use GetGridEntry to get the required number
    				int m =getGridEntry(array,n,r,c);
    				//Fill in m to G[r][c]
    				array[r][c]=m;
    			}
    		}
     
    		//Finally, print out the grid
    		for(int i=0;i<array.length;i++){
    			for(int j=0;j<array[i].length;j++){
    				System.out.print("\t"+array[i][j]);
    			}
    			System.out.println();
    		}
     
    	}
     
     
    /**
     * 	Method for finding grid entry
     * @param G Partially filled in grid G
     * @param n The size of G
     * @param r Row Designation
     * @param c Column designation
     * @return
     */
    	public static int getGridEntry(int G[][], int n, int r, int c){
     
    		//Iniitailze the int to be returned
    		int m =0;
     
    		//Le U be a piece of scratch space with n entries, with U[0,...,n] all zero
    		int U[]= new int[n];
     
    		//For each grid entry in row r, column i
    		for(int gridEntry: G[r]){
    			//i ranging from 1 to c-1 inclusive
    			for(int i=1;i<c;i++){
    				//Let x be G[r][i]
    				int x =G[r][i];
    				//Set U[x] to 1
    				U[x]=1;
    			}
     
    		}
     
    		//For each grid entry in column c row j, 
    		//with j ranging from 1 up to r-1 incluzive
    		for(int j=0;j<r;j++){
    			//Let y be G[j][c]
    			int y =G[j][c];
    			//Set U[y] to 1
    			U[y]=1;
     
    		}
     
    		//For each entry in U, numbered by k from 1 up to n inclusive
    		for(int k: U){
    			if(U[k]==0){
    				m=k;
    				return m;
     
    			}
    		}
     
     
    		return m;
     
    	}
    }

    This code only every gives me grids with output of zeros and ones, so I must have strayed from the instructions at some point. I know that the version in the text should definitely work. I've clearly gone wrong somewhere, but can you spot where?

    --- Update ---

    I've just realized I shouldn't have put this here.


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,517
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: Grid algorithm not working properly

    I think you've done this step wrong:

    For each entry in U, numbered by k from 1 up to n inclusive
    do this:
    ifU[k]equals zero
    thenStop this algorithm, and give our answer as k.

    I love your commenting and how you've used that as a basis for your coding (because that's how I work), but I think you strayed from the comments when you wrote the code for this step.

  3. #3
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Grid algorithm not working properly

    Hmm. I see what you mean. I'm not even using the number n for anything there, despite the fact it's explicitly stated. Nevertheless, I can't seem to interpret that part correctly. Of all the changes to that part I've tried so far, this strikes me as the closest:
    for(int k=0;k<n;k++){
     
    		if(U[k]==0){
    			return k;
    		}
     
    	}

    The above gives this as the output
    0 0 1 2
    1 1 0 3
    2 2 3 0
    3 3 2 1

    What I need to get is:
    0 1 2 3
    1 0 3 2
    2 3 0 1
    3 2 1 0

    Maybe I should just give my poor little brain a rest and come back to it. Maybe I'll find it was glaringly obvious all along. That's what usually happens. Thanks for the kind words about my commenting by the way .

  4. #4
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,517
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: Grid algorithm not working properly

    I think the part of the instructions, oft repeated, "row r, numbered 1 up to n inclusive, and for each column c, numbered 1 up to n inclusive," is the key to getting the results you need. "1 to n inclusive" is not how we typically deal with array elements, but that's what's required here, at least for the indices we use to get to those elements.

    I'll play with that a bit and let you know if I strike gold.

    Edit: Nope, I changed my mind. This line of the instructions:

    Let U be a piece of scratch space with n entries, with U[0,...,n] all zero.

    causes me question the whole set of instructions. U as defined by that line would contain n + 1 entries, so now I'm not sure of the "1 to x, inclusive" language used throughout the instructions. I don't trust them.

  5. #5
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Grid algorithm not working properly

    So, this problem was finally solved by replacing this:

    //For each grid entry in row r, column i
    		for(int gridEntry: G[r]){
    			//i ranging from 1 to c-1 inclusive
    			for(int i=1;i<c;i++){
    				//Let x be G[r][i]
    				int x =G[r][i];
    				//Set U[x] to 1
    				U[x]=1;
    			}			
    		}

    with this
    //i ranging from 0 to c-1 inclusive
    			for(int i=0;i<c;i++){
    				//Let x be G[r][i]
    				int x =G[r][i];
    				//Set U[x] to 1
    				U[x]=1;
    			}

    I then found out that the pattern being replicated is simply an XOR grid and the code below is all you need to get the required pattern:
    		for(int row = 0; row < n; ++row)
    		{
    		      for(int col = 0; col < n; ++col)
    		      {
    		           System.out.print("\t" + (row^col));
    		      }
    		      System.out.println();
    		}

Similar Threads

  1. Replies: 3
    Last Post: June 10th, 2013, 04:42 AM
  2. JScrollPane (/Scrollbar) not working on my grid
    By Vinvar in forum AWT / Java Swing
    Replies: 3
    Last Post: November 24th, 2012, 07:55 PM
  3. Applet not working properly
    By kookevk in forum AWT / Java Swing
    Replies: 1
    Last Post: February 3rd, 2012, 01:29 AM
  4. Grid movement randomly not working
    By pajfilms in forum What's Wrong With My Code?
    Replies: 9
    Last Post: August 27th, 2011, 07:35 AM
  5. Complete but not working properly
    By Noob101 in forum What's Wrong With My Code?
    Replies: 0
    Last Post: March 12th, 2011, 03:17 PM

Tags for this Thread