Hacker Challenge: Spiral Grid Pattern

In this lesson, we’ll be practicing more with multi-dimensional arrays. We’ll start by initializing a square matrix in a spiral pattern. We’ll then map the same 2-D spiral-patterned grid to a 1-D grid.

Creating a spiral grid

Let’s begin by creating a 7 x 7 matrix with values in a spiral fashion, as shown in the image below:

The grid of values above can be viewed in terms of 4 squares. The first outer square has incremental values from 1 to 24. The second square has values from 1 to 16. The third square has values from 1 to 8, and finally, the fourth square consists of a single cell with a value of 1.

How do you think we can create this pattern?

Try and write your implementation in the coding playground given below:

As we go down the lesson, we’ll guide you through the steps to solve this problem. Use the editor above to write your code for all steps.

A grid can be either $m \times n$ or $n \times n$. So we would need to determine the number of squares or rectangles in a grid first. In our case, we are taking an $n \times n$ grid.

Determining the number of rectangles/squares

We need to know how many rectangles/squares we have in our grid. Knowing the total number of squares/rectangles can help us know how many times our outer for loop would run for the complete spiral grid. In our example above, it’s a total of 4 squares. For that, we take the minimum of the number of rows and columns and divide that minimum by 2. This is the total number of rectangles/squares in a grid.

// taking the minimum of the two and storing it inside the variable rank
int rank = min(Rows, Cols);
int nofRectangles = rank/2;

We are using the built-in C++ min() function. This function returns the minimum of the two values. If both values are equal, it returns the first one.

In our case, we’re taking only a square matrix; the rows and columns would be equal.

Initializing the spiral

Looking at the pattern above, how should we initialize the array?

We can divide the first outer square into four parts (from top-left to top-right, top-right to bottom-right, bottom-right to bottom-left, and bottom-left to top-left).

Similarly, we have second and third inner squares that can also be divided into four parts. Then, in the center, we have a fourth one-cell square.

• For the outer square (0th square), in the first part, we have values 1–6, that increase as we go down the right-most column (values 7–12) and then back to the first column (values 13–18) and finally from the bottom to top (values 19–24).
• For the second square (1st square), in the first part, we have values 1 to 4, that increase as we go down the right-most column (values 5–8) and then back to the first column (values 9–12) and finally from the bottom to top (values 13–16).
• Similarly, for the third square (2nd square), in the first part, we have values 1–2, that increase as we go down the right-most column (values 3–4) and then back to the first column (values 5–6) and finally from the bottom to top (from 7–8).
• Lastly, for the inner square (3rd square), we only have a single cell with a value of 1.

In the editor above, we’ve named as the function as squareInit() function, which would initialize the grid. It takes parameters Grid[MaxRows][MaxCols] (the grid array), int Rows (total number of rows), int Cols (total number of columns), and int val (the initializing value which is the first value of each spiral).

Note that we have initialized the parameter val with 1 in the squareInit() function. This is an example of assigning default values to parameters. This means that if no value is passed for the val parameter when calling the squareInit() function, it will automatically use the default value of 1. Also, note that the default parameter is always written at the end of other parameters.

Instruction: Write the code to initialize the squares inside that function.

First, we must know the grid’s total number of rectangles/squares. Then we can easily print a spiral of $n \times n$ rectangles/squares. So, our outer for loop should run rank/2 times. The outer loop would then be as follows:

Now, let’s learn to initialize each square.

Why don’t we focus on the patterns of each side of the square, that is, how are the values being printed from left to right, from top to bottom, and so on?

So, we can have four for loops to print each side of a square.

As numbers are written in incremental order, the var variable will get incremented in every iteration. After completing every square, var can be reinitialized with the initial value. That is easy to handle by maintaining one variable and incrementing its value every time it is placed on the grid.

Our focus, for now, is how every side of the square can be captured in terms of loop iterations for the four loops.

Identifying the 4 patterns

Let’s break down the square printing into four segments:

• For each square sqri $\in$ {0,1,...rank/2-1}
  • Write left to the right side of square sqri.
  • Write top to the bottom side of square sqri.
  • Write right to the left side of square sqri.
  • Write bottom to the top side of square sqri.

a. Left to right

Let’s look at the left-to-right pattern of each of our squares. For square 0, row is fixed to 0 and column starts from 0 and goes up to Cols-1-(0+1) (one less than the last column). For square 1, row is fixed to 1 and column iterates from 1 to Cols-1-(1+1). For square 2, row is fixed to 2 and column iterates from 2 to Cols-1-(2+1). This makes it the pattern of the fixed row as sqri and starting column as sqri and the ending column as Cols-1-(sqri+1).

Cols is the total number of columns of the grid.

Here’s the following pattern.

You may have noticed that the end column is Cols-1-(sqri+1). This should print the values from the first index to the index one less than the column size for each square. Notice that we consider the first part to print values from columns 0–5 in our grid above. The last column 6 will be considered in the second part (top to bottom). This is to create uniformity in writing code that every loop’s responsibility is to write the exact same number of times.

Here is the code:

Instructions: Add the code that we’ve explained so far in the editor above and call the squareInit() and printR2_Grid() functions inside main(). We’ve already implemented the printR2_Grid() function to print all the grid elements.

So for a 7x7 matrix, this for loop would print the following:

The left-to-right pattern is being printed as shown below:

b. Top to bottom

For the second part (values 7–12), the column remains the same but the Rows increase as we go down. So, the top-to-bottom pattern would be:

Instructions: Add this second for loop in the editor above and comment on the first for loop. Run the code to see the output.

Since we’ve commented out the first for loop, the second for loop starts from the initialized value (1 in our case) and is incremented accordingly.

So, the above for loop would print the following:

If we uncomment the first for loop, the first two loops would print the left-to-right and top-to-bottom patterns as shown below:

c. Right to left

Here, the row remains the same, but the columns decrease from bottom-right to bottom-left.

So the right-to-left pattern would be:

Instructions: Add this third for loop in the editor above and comment the first and second for loops. Run the code to see the output.

So, the above for loop would print the following:

So far, we have printed the left-to-right, top-to-bottom, and right-to-left patterns as shown below:

d. Bottom to top

The bottom-to-top pattern can also be formed similarly.

Instructions: Try and make a table for the bottom-to-top pattern yourself and write the fourth for loop in the editor above. Comment the first, second, and fourth for loops. Then, run the code to see the output.

The fourth for loop should print the following:

Using these four for loops, we can display a square. To print n number of squares, we execute these loops sqri<rank/2 number of times.

As for the third and last one-cell spiral in the center of the grid that contains the value 1, we equate it to the value val like this:

 Grid[rank/2][Cols/2] = val;

So the complete code should print the following:

So far, we have printed the left-to-right, top-to-bottom, right-to-left, and bottom-to-top patterns, as shown below:

Complete code

The complete implementation of the above program is given below. Click “Run” to see the output.

Exercise: Mapping from 2-D to 1-D array

Now that we’ve initialized the matrix, let’s map this 2-D array to a 1-D array, as shown in the illustration below:

For this, we’ll need to declare another array which will be a 1-D array. Let’s call it Map[].

Assuming ai as the index of our 1-D array, we can equate the values of Grid[][] to the respective Map[ai]. We can easily modify our above code to map the 2-D array values to a 1-D array values. Write the code in the given playground: