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.

# Thread: Grid algorithm not working properly

1. ## 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 fill 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 filled 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.   Reply With Quote

3. ## 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.  Reply With Quote

4. ## 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 .  Reply With Quote

5. ## 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.  Reply With Quote

6. ## 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();
}```  Reply With Quote

#### Tags for this Thread 