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

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.

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 .

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.

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();
		}