Matrix spiral printing problem


CodeEval.com had an interesting problem called ‘Spiral Printing’. The problem required that you start with top-left of the matrix then continue printing matrix elements in a round clockwise order. (Ref: https://www.codeeval.com/public_sc/57/)

One logical way of solving this problem is to identify that after transversing the original matrix’s outer elements, the inner elements can be considered another smaller matrix. This small matrix can have a smaller matrix inside it and so on – analogous to layers of an onion. The following figure explains:

Spiral Printing
Spiral Printing a matrix

Hence, a neat way of coding this is to use recursive function. Initially, the function transverses the outer layer, then it would send the same matrix object as reference to itself in a recursive call. The function argument will contain pointers on what to consider start and end of the inner matrix. The following code snippet shows my solution:

void Matrix2D::SpiralWalk(vector<string>& vect_output, 
                int start_i = 0, int start_j = 0, 
                int n = UNASSIGNED_SIZE, int m = UNASSIGNED_SIZE)
{
     int i, j;

     if (n == UNASSIGNED_SIZE && m == UNASSIGNED_SIZE)
     {
         n = this->n;
         m = this->m;
     }

     if (m <= 0 || n <= 0)
         return;

     // Transverse (top, left) to (top, right)
     for (i = 0, j = 0; j < m; j++)
         vect_output.push_back(this->matrix2d[i + start_i][j + start_j]);

     ++i, --j;    // Re-adjust indices

     if (n > 2)    // If rows < 2 then there is no need to transverse
     {
         // Transverse (top + 1, right) to (bottom, right)
         for (; i < n; i++)
             vect_output.push_back(
                         this->matrix2d[i + start_i][j + start_j]);

         --i, --j;    // Re-adjust indices
     }

     if (n > 1)
     {
         // Transverse (bottom - 1, right) to (bottom, left)
         for (; j >= 0; j--)
             vect_output.push_back(
                         this->matrix2d[i + start_i][j + start_j]);
     }

     if (n > 2 && m > 1)
     {
         // Transverse (bottom - 1, left) to (top + 1, left)
         for (--i, ++j; i > 0; i--)
             vect_output.push_back(
                         this->matrix2d[i + start_i][j + start_j]);
     }
     else return;

     // Recursive call into smaller matrix
     SpiralWalk(vect_output, ++start_i, ++start_j, n-=2, m-=2);
}

Unfortunately, this is not the end of story. There are boundary conditions to consider. For instance, the matrix may have only one element, have only one row/column or even matrices having just two either rows/columns will also cause the function to enter invalid state. Hence, the need to protect the ‘for’ loop with ‘if’s in the codes above. If you are feeling experimental, try the above code with a matrix like ‘1;4;1 2 3 4’ and step through the code to see how it fails without the ‘if’ guards. Granted, that putting guards this way did cause the code to be hard to read but it also did avoid having to put a different ‘if’ statement to handle every boundary case separately.

Advertisements

Leave a reply here, thanks!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s