revised: 01/13/2008
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.
[H-15]
Reverse the order of the elements in an MxN array of integers,
so that
x[0][0]
x[M-1][N-1]
x[0][1]
x[M-1][N-1-1]
x[0][2]
x[M-1][N-1-2]
x[3][2]
x[M-1-3][N-1-2]
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
[M-10]
The diagonal of a 2D array consists of the elements
x[i][i]
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
[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
[M-7]
Write a function that moves every element of an array down
one position in raster order.
Element
moves to
,
unless
is
.
Then it is moved to
.
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
[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
.
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
[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
[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
[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
[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.
[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.