arraysalgorithm2dspiral

Logical error in 2d array spiral alorithm


I am trying to make a spiral with a 2d array. However I am missing the last element as shown in the picture.

spirals example.

I tried to make all kinds of conditions in the while loop to stop the algorithm one cycle later, but I couldn't and I am getting crazy because of it. The main algorithm code below:

    // height is always bigger than width by 1
    char [][] blankGrid = new char [height][width];

    int dir = 0;
    int top = 0;
    int bottom = height-1;
    int left = 0;
    int right = width-1;

    //draw digit spiral
    while(top <= bottom && left <= right ) {

        //RIGHT
        if (dir == 0) {
            for (int i = left; i <= right; i++) {
                blankGrid[top][i] = '0';
                if(left != 0 )blankGrid[top ][i-1] = '0';
                System.out.println(" DIR = 0 Position changed: "+ top   + ", " + i);
            }
            top += 2;
            dir++;

            //DOWN
        } else if (dir == 1) {
            for (int i = top; i <= bottom; i++) {
                blankGrid[i][right] = '1';
                blankGrid[i-1][right] = '1';
                System.out.println(" DIR = 1 Position changed: "+ top   + ", " + i );
            }
            right -= 2;
            dir++;

            //LEFT
        }else if (dir == 2) {
            for (int i = right; i >= left; i--) {
                blankGrid[bottom][i] = '2';
                blankGrid[bottom][i+1] = '2';
                System.out.println(" DIR = 2 Position changed: "+ bottom   + ", " + i);
            }
            bottom -= 2;
            dir++;

            //UP
        }else if (dir == 3) {
            for (int i = bottom; i >= top ; i--) {
                blankGrid[i][left] = '3';
                blankGrid[i+1][left] = '3';
                System.out.println(" DIR = 3 Position changed: "+ top   + ", " + i);
            }
            left += 2;
            dir = 0;
        }
    }

   // display  grid
    for(int i = 0; i < height; i++) {
        for(int j = 0; j < width; j ++){
            System.out.printf("%c", blankGrid[i][j]);
        }
        System.out.println();
    }

My desired output:

desired output

I tried things like:

 while(top <= bottom +/- 1 && left <= right +/- 1 )
 while(top <= bottom +/- 2 && left <= right +/- 2)
 while(bottom - top >= 0 && right - left >=0 )

and many more, but the results stay the same like in the picture above.


Solution

  • The reason is that you update the boundary variables (top, left, right, bottom) with a step of two at a moment that you still need to fill one cell that is outside that box when you start with your next direction (which is why you do two blankGrid assignments in each iteration of the inner loops -- which looks strange). This is no problem as long as the while condition is true, but in the last phase that condition will be false, meaning that the "box" has narrowed to nothing. Yet there is still this one cell to place...

    One solution is to not change that boundary with 2, but just 1, and do the other increment/decrement when you start with in the next direction.

    Your loop body could be updated with this idea as follows:

            //RIGHT
            if (dir == 0) {
                for (int i = left; i <= right; i++) {
                    blankGrid[top][i] = '0';
                }
                if (left > 0) left++;
                top++;
                dir++;
                //DOWN
            } else if (dir == 1) {
                for (int i = top; i <= bottom; i++) {
                    blankGrid[i][right] = '1';
                }
                top++;
                right--;
                dir++;
                //LEFT
            }else if (dir == 2) {
                for (int i = right; i >= left; i--) {
                    blankGrid[bottom][i] = '2';
                }
                right--;
                bottom--;
                dir++;
                //UP
            }else if (dir == 3) {
                for (int i = bottom; i >= top ; i--) {
                    blankGrid[i][left] = '3';
                }
                bottom--;
                left++;
                dir = 0;
            }
    

    I just did minimal changes to make it work, but you should try to reduce the repetition of code. These 4 code blocks are similar and can be collapsed into one. But as that is not related to the question, I'll leave that for you to improve.