Hunter Liu's Website

9.2. Challenge Problem Solution

A student approached me during office hours to discuss the challenge problem from the worksheet, which I’ll restate here:

Sample run: 
INPUT   5
OUTPUT  #####
OUTPUT      #
OUTPUT  ### #
OUTPUT  #   #
OUTPUT  #####

INPUT   10
OUTPUT  ##########
OUTPUT           #
OUTPUT  ######## #
OUTPUT  #      # #
OUTPUT  # #### # #
OUTPUT  # #  # # #
OUTPUT  # #    # #
OUTPUT  # ###### #
OUTPUT  #        #
OUTPUT  ##########

This is a very challenging problem! Please do not feel bad if you weren’t able to get a working solution. I’m uploading a solution and some commentary because I think it’s illustrative of many real-world applications of coding, wherein you must implement programs that are far easier for humans to do than computers.

The trap in this challenge problem is to try and print out the rows one at a time, all the while attempting to use string manipulations to determine what each row should look like. This is a fine approach, and it seems to be a good fit for the problem. After all, the computer can only print out one line at a time.

However, a multitude of difficulties present themselves when applying this approach. How exactly does one determine a given row of the spiral, even with the knowledge of the rows that came before it? There are some patterns, but not only are these patterns hard to capture in words and in code, but these patterns change depending on the total number of rows and where in the spiral you are.

These challenges can be overcome with enough tenacity, but there is a cleaner solution.

How would a human draw a \(5\times 5\) spiral? They might start with an empty \(5\times 5\) grid, then use a pen, pencil, or finger to trace out the following path through the grid:

1   2   3   4   5
                
.   .   .   .   6

15  16  17  .   7

14  .   .   .   8

13  12  11  10  9

This is probably the most natural way to describe drawing a spiral, and it has several advantages over the previous approach:

1. It’s simple to state and describe to humans. “Just go in a spiral”, one would say. “Go straight to the right until you hit the wall, then turn right and keep doing that”. We can make this algorithmically precise later.
2. The “algorithm” does not depend on the size of the spiral. It just works, no strings attached. In contrast, the previous approach searched for patterns in each row of the spiral, which do depend on how big the spiral is.

In what follows, we’ll incrementally develop the code. We’ll start by giving a broad, high-level set of pseudocode, then fill in the pieces in code, starting with the easiest parts and working our way up to the more delicate and difficult segments.

The main idea is that, rather than figuring out what each row of the spiral looks like individually, we should determine what the entire spiral looks like ahead of time, then print out the rows one by one. One way to do this is to index the grid of characters, left to right and top to bottom:

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

This way, we can represent our spiral using a single string of \(n^2\) characters, with the indices running across the grid. You can think of this as stacking the rows end-to-end. For instance, a \(5\times 5\) spiral would be represented by the string

#####    #### ##   # #####

We can start with a string of \(n^2\) spaces, then “spiral” our way around the grid and replace any character in our path with a #. At the very end, we’ll print \(n\) characters at a time, separated by a new line, to create a grid.

It’s much more natural to think about the grid with 2D coordinates:

    | Column
    | 0 1 2 3 4
----+-----------
R 0 | # # # # #
o 1 |         #
w 2 | # # #   #
  3 | #       #
  4 | # # # # #

We’ll be using these 2D coordinates to describe our path along the spiral. Given a point \((x, y)\), however, we need to know what index it is in our 1D string, with the rows stacked together. In this case, the index of this point would be \(5y+x\). Make sure you understand why this formula works, and make sure you can see how it generalises to the \(n\times n\) grid!

We are now ready to write some pseudocode.

1. Take an integer \(n\) as input from the user.
2. Create a string containing \(n^2\) spaces.
3. Follow a spiral path around the grid, replacing the corresponding characters in the string with a #.
4. Print out \(n\) characters of the string at a time, separated by new lines.

Step 1 is pretty straight forward:

1int n; 
2cin >> n; 

For step 2, we will start with an empty string, then append a space (n^2) times using the push_back function.

1string spiral = ""; 
2for(int i = 0; i < n * n; i++) {
3    spiral.push_back(' '); 
4}

Step 3 is very complicated, so we’ll skip that for now. Instead, let’s look at step 4. Thinking about our characters in grid form, we should be looking at coordinate pairs \((x, y)\) for \(0\leq x, y< n\). We’ll use a nested for loop to do so, with the loop over \(y\) on the inside so we print out the rows instead of the columns.

1for(int x = 0; x < n; x++) {
2    for(int y = 0; y < n; y++) {
3        int index = n * x + y; 
4        cout << spiral.at(index); 
5    }
6
7    cout << endl; 
8}

Make sure you understand how these nested for loops work! Try writing out what it’s doing for \(n=3\) if you’re having trouble visualising it.

The meat of the program is in step 3, where we snake around the spiral until we reach the centre. But how do we represent this in code?

It may not be the most obvious solution, but we’re going to code this the way one would explain this to a human. For the \(5\times 5\) spiral, the steps are as follows:

1. Start at \((0, 0)\).
2. Move one unit towards the right until you reach \(x=4\).
3. Move one unit down until you reach \(y=4\).
4. Move one unit to the left until you reach \(x=0\).
5. Move one unit up until you reach \(y=2\).
6. Move one unit to the right until you reach \(x=2\).

Based on this procedure, we should keep track of the following data:

1. Which direction are we moving, and
2. where are the “walls”, i.e. when do we stop and turn?

For the first piece of data, we will be keeping track of how (x) and (y) change with each step; for the second piece of data, we’ll hold four variables, one for each “wall”. Every time we hit a wall, we need to update it as well. When we move across the top (left to right), the upper wall gets “lowered” by 2, etc. We’ll summarise the changes in a table:

 dx | dy | Direction | Walls
----+----+-----------+-------------
  1 |  0 | Right     | Top += 2
  0 |  1 | Down      | Right -= 2
 -1 |  0 | Left      | Bottom -= 2
  0 | -1 | Up        | Left += 2

Finally, we need to keep spiralling until the walls “close in” on each other. That is to say, we need top <= bottom and left <= right in order for our instructions to make sense. Thus, our pseudocode for marking the spiral is as follows:

1. Initialise x = 0 and y = 0, the starting point of our spiral.
2. Initialise dx = 1 and dy = 0, the initial direction of our spiral.
3. Initialise top = 0, right = n - 1, bottom = n - 1, and left = 0, the four “walls” of the spiral.
4. While top <= bottom and left <= right, repeat the following:
   • Repeat until you hit the appropriate “wall”:
     • Mark the point at ((x, y)) with a #
     • Increment x += dx and y += dy
   • Update the walls according to the direction.
   • Update dx and dy to reflect a “right turn”

Try writing these instructions in code yourself before looking at the full solution below! Think about how you should be updating the walls, and think about how to update the directions in the last step.

This is how my code turned out:

 1#include <iostream>
 2#include <string>
 3
 4using namespace std;
 5
 6int main() {
 7    // input the size of the spiral
 8    int n;
 9    cin >> n;
10
11    // create a string of n^2 spaces
12    string spiral = "";
13    for(int i = 0; i < n * n; i++) {
14        spiral.push_back(' ');
15    }
16
17    // let x, y represent the position on the grid
18    int x = 0, y = 0;
19
20    // let dx, dy represent the changes in x and y
21    // as we move along the spiral.
22    int dx = 1, dy = 0;
23
24    // these represent the "boundaries" of our spiral
25    int left = 0, right = n - 1, top = 0, bottom = n - 1;
26
27    // while some mystery condition is true,
28    // move along the spiral and turn things into *'s.
29    while(top <= bottom || left <= right) {
30        // move until you hit the appropriate wall
31        while((dx == 1 && x <= right) || (dx == -1 && x >= left) ||
32              (dy == 1 & y <= bottom) || (dy == -1 && y >= top)) {
33            spiral.at(n * y + x) = '*';
34            x += dx;
35            y += dy;
36        }
37
38        // correct the overshoot
39        x -= dx;
40        y -= dy;
41
42        // update the walls
43        if(dx == 1)  {  top += 2;    }
44        if(dy == 1)  {  right -= 2;  }
45        if(dx == -1) {  bottom -= 2; }
46        if(dy == -1) {  left += 2;   }
47
48        // update the directions
49        int temp = dy;
50        dy = dx;
51        dx = -1 * temp;
52    }
53
54    // actually print out the spiral, n characters at a time
55    for(int row = 0; row < n; row++) {
56        for(int col = 0; col < n; col++) {
57            cout << spiral.at(n * row + col);
58        }
59
60        cout << endl;
61    }
62    return 0;
63}

Again, this was a very challenging problem, and I’m very impressed if you were able to solve the problem to any degree yourself!

A remark about this problem: the emphasis is on the thinking that goes on before you start coding, not the coding itself. The code only uses a few loops, a few print statements, and strings, each of which we have learned about in the first few weeks!

Instead, the challenge of this problem is figuring out how to express our human intuition and thought processes of making a spiral in a way that’s specific enough to be put into code. Often (but not always), the human brain quickly identifies a near-optimal way to solve simple and familiar problems. In fact, a lot of tasks and algorithms exist specifically to capture our human intuition at an algorithmic level of consistency and precision, from lines of best fit to facial recognition to modern artificial intelligence.