9

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
Spektre
  • 49,595
  • 11
  • 110
  • 380
user3328187
  • 193
  • 2
  • 2
  • 6
  • 3
    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. – Dúthomhas Nov 13 '15 at 02:45
  • @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 :) )? – Spektre Nov 13 '15 at 08:41
  • You asked about the algorithm, not your specific application. Sorry, I didn't mean to be confusing. – Dúthomhas Nov 13 '15 at 11:40
  • @Dúthomhas don't worry I was thinking more that I missed something obvious ... (I do that a lot) – Spektre Nov 13 '15 at 12:03

5 Answers5

9

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;
    }
}
Khaled.K
  • 5,828
  • 1
  • 33
  • 51
  • Would some one please explain what does it mean Chains: Count(K-chain)=2 for K = 1..(SIZE-2) + 3 for Count = SIZE-1 – Suman g Feb 05 '19 at 14:56
  • @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 – Khaled.K Feb 07 '19 at 18:15
6

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

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
0
    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.

4ipideil
  • 1
  • 1
  • 2
0
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;
}
Kunal C
  • 1
0

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()
user3458211
  • 141
  • 2
  • 1