revised: 01/13/2008


Puzzles D11 ... D20

Part D — 2D Arrays

These puzzles involve 2D arrays. As with the previous puzzles, these use the old style of 2D array parameters where the number of columns has to be hard-coded.


Puzzle D11 — reverse the order of the elements in a 2D array

[H-15] Reverse the order of the elements in an MxN array of integers, so that x[0][0] is now at x[M-1][N-1], x[0][1] is now at x[M-1][N-1-1], x[0][2] is now at x[M-1][N-1-2], x[3][2] is now at x[M-1-3][N-1-2], and so on. For example:

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

becomes

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

Click here for a Testing Framework


Puzzle D12 — Initialize a 2D array so that its diagonal is 0, elements above the diagonal are 1, and elements below the diagonal are -1

[M-10] The diagonal of a 2D array consists of the elements x[i][i] with the same row number as column number. Initialize an array of ints so that elements on the diagonal are 0, elements above the diagonal are 1, and elements below the diagonal are -1. Here are some examples:

 0  1  1  1  1 1
-1  0  1  1  1 1
-1 -1  0  1  1 1
-1 -1 -1  0  1 1
-1 -1 -1 -1  0 1
-1 -1 -1 -1 -1 0
 0  1  1  1  
-1  0  1  1  
-1 -1  0  1  
-1 -1 -1  0  
-1 -1 -1 -1  
-1 -1 -1 -1  
 0  1  1  1  1 1
-1  0  1  1  1 1
-1 -1  0  1  1 1

A prototype for the function is:

void initDiagonal( int x[][NUMCOLS], int nrows );

Click here for a Testing Framework


Puzzle D13 — Transpose the elements of an array

[M-15] Assume that the array has the same number of rows as columns. To transpose such an array, exchange element x[r][c] with element x[c][r]. The diagonal does not change. Here are some examples:

Original:

  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
Transposed:

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

  0   1   2 
  5   6   7  
 10  11  12  
Transposed:

 0   5  10
 1   6  11
 2   7  12
Original:

  0   1   2
  3   4   5
  6   7   8
Transposed:

  0   3   6
  1   4   7
  2   5   8

A prototype for the function is:

int transpose( int x[NUMCOLS][NUMCOLS] );  /* Number of rows and columns must be the same */

Click here for a Testing Framework


Puzzle D14 — Rotate the elements of a 2D array

[M-7] Write a function that moves every element of an array down one position in raster order. Element x[i][j] moves to x[i][j-1], unless j is 0. Then it is moved to x[i-1][NUMCOLS-1]. The first element of the array is moved to the last location in the array.

Before:         After:

0 1 2 3 4       1 2 3 4 5
5 6 7 8 9       6 7 8 9 0

Click here for a Testing Framework


Puzzle D15 — Rotate the elements of a 2D array by N positions

[M-15] Write a function that moves every element of an array down by N positions in raster order. The easy way to do this is to use the previous function N times. But for this exercise, perform the rotation by moving each element only once.

Allow N to be in the range 0 <= N <= NUMROWS*NUMCOLS. If N is out of range, do nothing to the array and return 0. Otherwise, rotate the array and return 1.

Here is an example:

Original:
  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  25  26  27  28  29
 30  31  32  33  34  35  36  37  38  39
 40  41  42  43  44  45  46  47  48  49

Rotated by 13:
 13  14  15  16  17  18  19  20  21  22
 23  24  25  26  27  28  29  30  31  32
 33  34  35  36  37  38  39  40  41  42
 43  44  45  46  47  48  49   0   1   2
  3   4   5   6   7   8   9  10  11  12

A prototype for the function is:

int rotateDownN ( int x[][NUMCOLS], int nrows, int N )

Click here for a Testing Framework


Puzzle D16 — Zero the edges of an Array

[M-10] Write a function that clears to zero all the edge elements of an MxN matrix. Those are the elements that are in row 0, column 0, row M-1, or column N-1. For example:

Original:
  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  25  26  27  28  29
 30  31  32  33  34  35  36  37  38  39
 40  41  42  43  44  45  46  47  48  49

Edge Zeroed:
  0   0   0   0   0   0   0   0   0   0
  0  11  12  13  14  15  16  17  18   0
  0  21  22  23  24  25  26  27  28   0
  0  31  32  33  34  35  36  37  38   0
  0   0   0   0   0   0   0   0   0   0

Click here for a Testing Framework


Puzzle D17 — Initialize the diagonals of an NxM array

[M-10] Write a function that first finds which is least: the number of rows or the number of columns in a 2D array. Then the functions sets the main diagonal to that minimum, the two diagonals next to it to minimum, the next two diagonals to minimum, and so on untile the array is full. Some Examples:

  5   4   3   2   1
  4   5   4   3   2
  3   4   5   4   3
  2   3   4   5   4
  1   2   3   4   5

  9   8   7   6   5   4   3   2   1
  8   9   8   7   6   5   4   3   2
  7   8   9   8   7   6   5   4   3
  6   7   8   9   8   7   6   5   4

 10   9   8   7
  9  10   9   8
  8   9  10   9
  7   8   9  10
  6   7   8   9
  5   6   7   8
  4   5   6   7
  3   4   5   6
  2   3   4   5
  1   2   3   4

Click here for a Testing Framework


Puzzle D18 — Determine if any element in a 2D array is duplicated

[H-15] Write a function that returns 1 when a duplicate element is detected in a 2D array of integers. Otherwise the function returns 0. The function returns immediately when it detects the first duplicate; it does not need to look for additional duplicate elements.

A prototype for the function is:

int isDuplicate( int x[][NUMCOLS], int nrows );

Solve the puzzle without sorting the elements. This will result in an inefficient O(n2) algorithm, but that is good enough for n < 50 or so.

Click here for a Testing Framework


Puzzle D19 — Count the number of duplicate values in a 2D array of ints

[H-20] Write a function that counts the number of elements in a 2D array of ints that have the same value as some other element. For example, in the following array the count is 8 because there are 3 ones, 2 threes, and 3 fives.

 5  5  5  1  3
 1  2  3  0 10
 4  1  9  7 13

A prototype for the function is:

int numberDuplicates( int x[][NUMCOLS], int nrows )

Hint: to do this, copy the elements of the 2D array to a 1D array, sort the 1D array, then scan the sorted elements for duplicates. Use your answer to C49 (selection sort) to sort the array, or use the standard library qsort() function. In a sorted 1D array, duplicate elements will appear as runs. Add up the lengths of all the runs to get the total number of duplicates.

Click here for a Testing Framework, which includes selection sort.


Puzzle D20 — fill a 2D array with random ints, without any duplicates

[H-20]Write a function that fills an array with random integers in the range min .. max (inclusive). Ensure that any integer in the array occurs only once.

The function immediately returns 0 if the request is not possible. This will happen if there are more slots in the array than there are integers in the range low to high. Otherwise the function returns 1 after it has completed the request.

The straightforward way to do this takes O(n2) time, where n is the number of elements in the array. Although this would not be suitable for some situations, go ahead and use this approach.

A prototype for the function is:

void randomFill2DUnique( int x[][NUMCOLS], int nrows, int low, int high )

Click here for a Testing Framework, which includes selection sort.


— Return to the main contents page