Question 3 (25 points)

Complete the method Spiral below. The method creates an (n+2)-by-(n+2) 2-D array with a border of -1's and inside that border, a clockwise spiral of the integers from 1 through n*n. For example, if n is 4, then the method should return the array shown below:

-1 -1 -1 -1 -1 -1

-1 1 2 3 4 -1

-1 12 13 14 5 -1

-1 11 16 15 6 -1

-1 10 9 8 7 -1

-1 -1 -1 -1 -1 -1

Solution

// Create clockwise spiral of size n >= 1 with in a border of -1's.

static int[][] spiral( int n )

{

int[][] A = new int[ n + 2 ][ n + 2 ];

int[] deltaR = {0, 1, 0, -1};

int[] deltaC = {1, 0, -1, 0};

// Fill the border of A with -1's

for( int i = 0; i < n + 2; i++ )

A[ 0 ][ i ] = A[ n + 1][ i ] = A[ i ][ 0 ] = A[ i ][ n + 1] = -1;

int r =1; // start in cell <1, 0>

int c = 0;

int d = 0; // facing right

// Create clockwise spiral by repeatedly visiting and numbering

// cells, as follows: if facing a non-zero cell, turn 90-degrees

// clockwise. Step forward. Record the cell number.

for( int i = 1; i <= n*n; i++ )

{

if ( A[ r + deltaR[ d ] ][ c + deltaC[ d ] ] != 0 )

d = (++d)%4;

r+=deltaR[ d ];

c+=deltaC[ d ];

A[ r ][ c ] = i;

}

return A;

}

Comments

A significant number of students left this question blank for the simple reason that they lacked the courage to proceed. Always remember that doing something -- anything -- can lead to success in analyzing a problem. Indeed, the body of our for-loop is nothing less than a direct translation (into code) of the preceding comments:

// if facing a non-zero cell, turn 90-degrees clockwise.

if ( A[ r + deltaR[ d ] ][ c + deltaC[ d ] ] != 0 )

d = (++d)%4;

// Step forward.

r+=deltaR[ d ];

c+=deltaC[ d ];

// Record the cell number.

A[ r ][ c ] = i;

A mere attempt at a translation should prove useful to the determined student. For instance, what would stepping forward mean? How do I record a cell number?

Students should note how the modulo function is here cleverly used to avoid an extra if statement.