Print 2-D Array in clockwise expanding spiral from center

Question

I have an guaranteed to be a perfect square matrix. I want to start at the center of the matrix in this case it would be matrix[2][2], I know how to figure the center (int)(dimensions / 2). I need to output the contents of the array in this following outward spiral pattern. Of course the algorithm should work with any perfect square matrix. I wasn't sure if this algorithm already existed and I didn't want to re-invent the wheel.

int dimensions / 2;

21 22 23 24 25
20 7  8  9  10
19 6  1  2  11
18 5  4  3  12 
17 16 15 14 13

The output for this example should be

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Wilek

There are a gazillion variations on this simple algorithm. For a hint, try keeping track of which direction you are travelling, and how many elements you traverse for each direction. You'll notice the pattern. Hope this helps. – Oneirocritic

@Dúthomhas I agree the pattern is obvious but I see only 8 variations Am I missing something (It is early morning for me so That is a strong possibility :) )? – Kileykilgore

You asked about the algorithm, not your specific application. Sorry, I didn't mean to be confusing. – Oneirocritic

@Dúthomhas don't worry I was thinking more that I missed something obvious ... (I do that a lot) – Kileykilgore

Answer 1

Let's identify the patterns first ..

Even-Size Square Matrix, Example: 4x4

  07 > 08 > 09 > 10
  ^               v
  06  (01)> 02   11
  ^          v    v
  05 < 04 < 03   12
                  v
 [16]< 15 < 14 < 13

Starting Point: [2, 2] ~ [SIZE/2, SIZE/2]

Ending Point: [4, 1] ~ [SIZE, 1]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

Odd-Size Square Matrix, Example: 5x5

  21 > 22 > 23 > 24 >[25]
  ^
  20   07 > 08 > 09 > 10
  ^    ^               v
  19   06  (01)> 02   11
  ^    ^          v    v
  18   05 < 04 < 03   12 
  ^                    v
  17 < 16 < 15 < 14 < 13

Starting Point: [2, 2] ~ [⌊SIZE/2⌋, ⌊SIZE/2⌋]

Ending Point: [1, 5] ~ [1, SIZE]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

Live Code

void print_spiral (int ** matrix, int size)
{
    int x = 0; // current position; x
    int y = 0; // current position; y
    int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
    int c = 0; // counter
    int s = 1; // chain size

    // starting point
    x = ((int)floor(size/2.0))-1;
    y = ((int)floor(size/2.0))-1;

    for (int k=1; k<=(size-1); k++)
    {
        for (int j=0; j<(k<(size-1)?2:3); j++)
        {
            for (int i=0; i<s; i++)
            {
                std::cout << matrix[x][y] << " ";
                c++;

                switch (d)
                {
                    case 0: y = y + 1; break;
                    case 1: x = x + 1; break;
                    case 2: y = y - 1; break;
                    case 3: x = x - 1; break;
                }
            }
            d = (d+1)%4;
        }
        s = s + 1;
    }
}

Cleanly

Would some one please explain what does it mean Chains: Count(K-chain)=2 for K = 1..(SIZE-2) + 3 for Count = SIZE-1 – Cecilycecity

@Sumang if you look at where the spiral starts, the number of steps it takes each time before it turns increase by 1 every 2 turns basically.. the formula is how the number of steps in each direction is taken before turning is calculated – Cleanly

Answer 2

As this smells like homework then no code or direct answer instead just few hints:

You can look at this as an turtle problem:

Let m be movement by 1 cell and r be rotation by 90 degrees in your spiral direction (CW or CCW). then the spiral can be encoded as series of turtle commands forming this pattern (from the start point):

    m,r,m,r, 
    m,m,r,m,m,r,
    m,m,m,r,m,m,m,r,
    m,m,m,m,r,m,m,m,m,r,
    m,m,m,m,m,r 

As you can see you start with 1x move then rotate after two repetition you switch to 2x move, after 2 moves switch to 3x move,... and so on. This can be done with just few for loops (or just by one with some proper iterations and stopping when matrix number of cells is hit ... or the endpoint corner is hit)

You need to handle even/odd matrix sizes

for odd matrix sizes is the middle point easy. For even sizes it is a bit more complicated. if you use CW rotation then use the rounded down division result of halving the size and start with moving to the right. (if you need different spiral then you need to add +1 to x and/or y and change starting direction) so the spiral will stay centered.

So If you got even sized matrix then the last movement is twice if you got odd size then the last movement is there just once (like in this example)

rotation

Have direction stored as 2D vector. for example d=(+1,0) means right. to rotate 2D vector you just swap coordinates and negate one axis (which one means the CW/CCW). For example (x,y) -> (y,-x)

movement

Store current position as 2D vector too. The movement is just adding current direction vector to it.

Have fun with solving this ...

Kileykilgore

Answer 3

    int radius = 0;
    int i = centerX;
    int j = centerY;
    Debug.Log("i=" + i + "; j=" + j);
    ++i;
    radius += 2;
    while ((i < dimm) && (i >= 0))
    {
        for (int c = j; j < c + radius; j++)
            Debug.Log("i=" + i + "; j=" + j);
        --j;
        --i;
        for (int c = i; i > c - radius + 1; i--)
            Debug.Log("i=" + i + "; j=" + j);
        if (i < 0)
            break;
        else
            Debug.Log("i=" + i + "; j=" + j);
        --j;
        for (int c = j; j > c - radius; j--)
            Debug.Log("i=" + i + "; j=" + j);
        ++i;
        ++j;
        for (int c = i; i < c + radius; i++)
            Debug.Log("i=" + i + "; j=" + j);
        radius += 2;
    }

This Code will output counterclockwise squared matrix (dimm X dimm) indexes from custom center(CenterX, CenterY); and end up, if it came out of matrix size.

Pears

Answer 4

bool IsIterationComplete(int iteration, int nCenter, std::vector<std::vector<bool>>& vVisited)
{
    int nHigh = nCenter+iteration;
    int nLow = nCenter-iteration;
    //cout<<endl<<"High "<<nHigh<<"Low "<<nLow<<endl;
    for(int i=nLow;i<=nHigh;i++)
    {
        if(!vVisited[nHigh][i] || !vVisited[nLow][i]) 
            return false;
    }

    for(int i=nLow;i<=nHigh;i++)
    {
        if(!vVisited[i][nHigh] || !vVisited[i][nLow])
            return false;
    }

    return true;
}
void PrintSpiral(std::vector<std::vector<int>>& vMat,std::vector<std::vector<bool>>& vVisited, int row, int col, int nCenter, int iteration)
{
    cout<<vMat[row][col];
    vVisited[row][col]=true;

    if(row==0 && col==0)
        return;

    if(IsIterationComplete(iteration,nCenter,vVisited))
        iteration++;

    //cout<<endl<<"row "<<row<<" column "<<col<<"Iteration "<<iteration<<endl;

//left
    if(col-1>=0 && !vVisited[row][col-1] && col-1>=nCenter-iteration)
    {
        cout<<"Left "<<endl;
        PrintSpiral(vMat,vVisited,row,col-1,nCenter,iteration);
    }

    //Down
    if((row+1)<vMat.size() && !vVisited[row+1][col] && row+1<=nCenter+iteration)
    {
        cout<<"Down "<<endl;
        PrintSpiral(vMat,vVisited,row+1,col,nCenter,iteration);
    }

    //right
    if((col+1)<vMat.size() && !vVisited[row][col+1] && col+1<=nCenter+iteration)
    {
        cout<<"Right "<<endl;
        PrintSpiral(vMat,vVisited,row,col+1,nCenter,iteration);
    }

    //up    
    if(row-1>=0 && !vVisited[row-1][col] && row-1>=nCenter-iteration)
    {
        cout<<"Up "<<endl;
        PrintSpiral(vMat,vVisited,row-1,col,nCenter,iteration);
    }
}


int main (int argc, const char * argv[])
{
    int nCount=1;
    std::vector<std::vector<int>> vMat;
    std::vector<std::vector<bool>> vVisited;
    for(int i=0; i<7; i++)
    {
        std::vector<int> row;
        std::vector<bool> visitedRow;
        for(int j=0; j<7; j++)
        {
            row.push_back(nCount);
            cout<<nCount<<'\t';
            nCount++;
            visitedRow.push_back(false);
        }
        cout<<'\n';
        vMat.push_back(row);
        vVisited.push_back(visitedRow);
    }
    cout<<'\n';
    PrintSpiral(vMat,vVisited,vMat.size()/2,vMat.size()/2,vMat.size()/2,0);
    return 0;
}

Consistent

Answer 5

Here is a simple solution in Python:

def spiral_matrix(n): 
    # Create an n x n matrix filled with zeros
    mat = [[0 for i in range(n)] for j in range(n)]   
    
    # Start from the middle of the matrix
    x = n // 2
    y = n // 2

    # If n is even, adjust the start position
    if n % 2 == 0:
        x -= 1
        y -= 1

    # Initialize the first value to be filled into the matrix
    val = 1

    # Initialize the directions for movement (right, down, left, up)
    dirs = [(0,1), (1,0), (0,-1), (-1,0)]
    dir = 0  # Start with the first direction (right)

    # Begin filling the matrix
    while val <= n * n:  # Continue until all cells are filled
        # If the next cell is within the matrix and has not been visited
        if 0 <= x < n and 0 <= y < n and mat[x][y] == 0:
            # Fill the cell and increment the value
            mat[x][y] = val
            val += 1
        else:  # If the next cell is outside the matrix or already visited
            # Move back to the previous cell and change the direction
            x = px
            y = py
            dir -= 2  # Go back two steps in the direction sequence

        # Save the current position
        px = x
        py = y

        # Move to the next cell in the current direction
        x += dirs[dir][0]
        y += dirs[dir][1]

        # Change the direction (right -> down -> left -> up -> right -> ...)
        dir = (dir + 1) % 4

    # Return the filled matrix
    return mat

# Test the function with n = 5
n = 4           
mat = spiral_matrix(n)

# Print the filled matrix
for row in range(n):
    for col in range(n):
        print(mat[row][col], end="\t")
    print()

Koopman

Answer 6

There is a C# version base on Khaled.K's answer:

        /// <summary>
        /// 从中心向外螺旋遍历
        /// </summary>
        /// <param name="matrix"></param>
        /// <param name="action"></param>
        /// <typeparam name="T"></typeparam>
        private static void TraverseSpiralExpand<T>(T[,] matrix, Action<T> action)
        {
            var length = matrix.GetLength(0);
            if (length != matrix.GetLength(1))
            {
                throw new InvalidDataException("SpiralExpand only supported on Square Matrix.");
            }

            // starting point
            var x = (length - 1) / 2;
            var y = (length - 1) / 2;

            // 0=>x++, 1=>y++, 2=>x--, 3=>y--
            var direction = 0;

            action(matrix[x, y]);
            for (var chainSize = 1; chainSize < length; chainSize++)
            {
                for (var j = 0; j < (chainSize < length - 1 ? 2 : 3); j++)
                {
                    for (var i = 0; i < chainSize; i++)
                    {
                        switch (direction)
                        {
                            case 0:
                                x++;
                                break;
                            case 1:
                                y++;
                                break;
                            case 2:
                                x--;
                                break;
                            case 3:
                                y--;
                                break;
                        }
                        action(matrix[x, y]);
                    }
                    direction = (direction + 1) % 4;
                }
            }
        }

Candlepin

Answer 7

Spiral Pattern

As @Khaled.K and @Spektre have said in their answers/comments, we should first look at the pattern of the spiral and notice how the length of each segment (or steps) is increased after every two segments printed.

Algorithm Logic

With this in mind, I'd like to share a solution that I think is easier to read. I basically start from the middle of the matrix and then rely on a segmentLength variable and a direction array to determine how many numbers to print on the current segment and in which direction to move within the matrix. After printing the current segment, I then check whether the next segment's length should be increased or not according to the behavior described above.

int** generateSpiral(int n) {
    int** spiral = new int*[n];
    for (int i = 0; i < n; i++){
        spiral[i] = new int[n];
    }

    // Defining the directions order and offsets: Right, Down, Left, Up
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    //Adjusting the center for even inputs
    int center = n % 2 == 0 ? n / 2 - 1 : n / 2;
    int row, col, num = 1;
    row = col = center;

    //In an expanding spiral pattern, the length of a segment is increased after drawing two segments
    int segmentsAfterToIncrease = 2;
    int segmentCounter = 0;
    int segmentLength = 1;
    int dir = 0;

    //As soon as we're exceeding a boundary the spiral ends
    while (!(row >= n || row < 0 || col >= n || col < 0)) {

        //Printing the numbers of the current segment
        for (int i = 0; i < segmentLength; i++) {
            spiral[row][col] = num++;
            row += directions[dir][0];
            col += directions[dir][1];
        }

        //Rotating to the next direction
        dir = (dir + 1) % 4;

        //Checking if we've printed the number of segments necessary to increase the length of the next segment
        segmentCounter = (segmentCounter + 1) % segmentsAfterToIncrease;
        if (segmentCounter == 0) {
            segmentLength++;
        }
    }

    return spiral;
}

Online Example

I've also created an online example at ideone.com showing the different outputs with even and odd numbers: https://ideone.com/69V68l

Pecuniary

Answer 8

def spiral_matrix(n): 
    mat = [[0 for i in range(n)] for j in range(n)]   
    
    x = n // 2
    y = n // 2

    if n % 2 == 0:
        x -= 1
        y -= 1

    val = 1 
  
    dirs = [(0,1),(1,0),(0,-1),(-1,0)]   #right, down, left, up
    dir = 0  

    while val <= n * n:  
        if 0 <= x < n and 0 <= y < n and mat[x][y] == 0:
            mat[x][y] = val
            val += 1
        else: 
            x = px
            y = py
            dir -= 2  

        px = x
        py = y

        x += dirs[dir][0]
        y += dirs[dir][1]

        dir = (dir + 1) % 4

    return mat

n = 7    
mat = spiral_matrix(n)

for row in range(n):
    for col in range(n):
        if col == n - 1:
            print("{:02d}".format(mat[row][col]), end="")
        else:
            print("{:02d}".format(mat[row][col]), end=" ")
    print()
    
# Output:
# 43 44 45 46 47 48 49
# 42 21 22 23 24 25 26
# 41 20 07 08 09 10 27
# 40 19 06 01 02 11 28
# 39 18 05 04 03 12 29
# 38 17 16 15 14 13 30
# 37 36 35 34 33 32 31

Editheditha