This simple code tries to move through a 2 by 2 matrix in a spiral manner from index [0][0] until there is no elements left in the original. For example if there is a matrix like below,
[[1 2 3]
[4 5 6]
[7 8 9]]
The output would be,
[1 2 3 6 9 8 7 4 5]
This code runs ok but it pauses briefly in the last and then finally print the output array. What is the cause of this behavior?
#include <stdio.h>
#include <stdlib.h>
typedef enum {
move_right,
move_down,
move_left,
move_up
}States;
void print_array(int* arr, int n)
{
for(int i = 0; i<n; i++){
printf(" %d", arr[i]);
}
}
void spiral_matrix(int* input, int row_size, int col_size, int* output)
{
int size = row_size * col_size;
int max_col = col_size-1;
int max_row = row_size-1;
int min_col = 0;
int min_row = 0;
int i = 0;
int j = 0;
States current_state = move_right;
int idx = 0;
while(idx < size) {
switch (current_state)
{
case move_right:
if(j < max_col) {
output[idx] = *(input+i*col_size + j);
j++;
idx++;
} else {
current_state = move_down;
min_row += 1;
}
break;
case move_down:
if(i < max_row) {
output[idx] = *(input+i*col_size + j);
i++;
idx++;
} else {
current_state = move_left;
max_col--;
}
break;
case move_left:
if(j > min_col) {
output[idx] = *(input+i*col_size + j);
j--;
idx++;
} else {
current_state = move_up;
max_row--;
}
break;
case move_up:
if(i > min_row) {
output[idx] = *(input+i*col_size + j);
i--;
idx++;
} else {
current_state = move_right;
min_col += 1;
}
break;
default:
break;
}
}
}
#define N 4
#define M 4
void main(void)
{
int A[N][M] = {{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};
int* spiral_out = (int*)malloc(N*M*sizeof(int));
spiral_matrix(A[0], N, M, spiral_out);
print_array(spiral_out, N*M);
free(spiral_out);
}
This code runs ok but it pauses briefly in the last and then finally print the output array. What is the cause of this behavior?
That's only your assumption and it is missing facts.
There is a flaw in your logic -
When printing the first row 1,2,3,4, it only writes till element 3 to output array and set the current_state to move_down and in move_down case, writes 4 to output array. But logically it should write till element 4 and then set current_state to move_down. Same behavior for all the corner elements when traversing matrix in spiral manner.
When it reaches to last element, the values of variables max_col, max_row, min_col, min_row, i, j, idx set in such a way that neither while loop condition results in false nor any of the if condition in while loop body results in true and value of variables max_col, max_row, min_col and min_row either increment or decrement based on else block statement. At one stage, they either overflow/underflow (depends on whether its incrementing/decrementing) and end up in undefined behavior.
[An undefined behavior includes it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended.]
Values of variables max_col, max_row, min_col, min_row, i, j, idx after writing element 11 (second last element in spiral traversal) in output array (recorded only for a few iterations):
max_col : 1, max_row : 2, min_col : 1, min_row : 2, i : 2, j : 1, idx : 15
max_col : 1, max_row : 1, min_col : 1, min_row : 2, i : 2, j : 1, idx : 15
max_col : 1, max_row : 1, min_col : 2, min_row : 2, i : 2, j : 1, idx : 15
max_col : 1, max_row : 1, min_col : 2, min_row : 3, i : 2, j : 1, idx : 15
max_col : 0, max_row : 1, min_col : 2, min_row : 3, i : 2, j : 1, idx : 15
max_col : 0, max_row : 0, min_col : 2, min_row : 3, i : 2, j : 1, idx : 15
max_col : 0, max_row : 0, min_col : 3, min_row : 3, i : 2, j : 1, idx : 15
max_col : 0, max_row : 0, min_col : 3, min_row : 4, i : 2, j : 1, idx : 15
max_col : -1, max_row : 0, min_col : 3, min_row : 4, i : 2, j : 1, idx : 15
max_col : -1, max_row : -1, min_col : 3, min_row : 4, i : 2, j : 1, idx : 15
max_col : -1, max_row : -1, min_col : 4, min_row : 4, i : 2, j : 1, idx : 15
max_col : -1, max_row : -1, min_col : 4, min_row : 5, i : 2, j : 1, idx : 15
max_col : -2, max_row : -1, min_col : 4, min_row : 5, i : 2, j : 1, idx : 15
max_col : -2, max_row : -2, min_col : 4, min_row : 5, i : 2, j : 1, idx : 15
max_col : -2, max_row : -2, min_col : 5, min_row : 5, i : 2, j : 1, idx : 15
max_col : -2, max_row : -2, min_col : 5, min_row : 6, i : 2, j : 1, idx : 15
max_col : -3, max_row : -2, min_col : 5, min_row : 6, i : 2, j : 1, idx : 15
max_col : -3, max_row : -3, min_col : 5, min_row : 6, i : 2, j : 1, idx : 15
max_col : -3, max_row : -3, min_col : 6, min_row : 6, i : 2, j : 1, idx : 15
......
......
...... // keep on incrementing/decrementing in same pattern
...... // and loop iterates as there is no change in idx value
The while loop continuously iterates, gives you an impression of pause.
To fix this problem, when changing the current_state, set i (row) and j (column) properly based on the state to be execute:
while(idx < size) {
switch (current_state)
{
case move_right:
if(j <= max_col) { // write to array till max column
output[idx] = *(input+i*col_size + j);
j++;
idx++;
} else {
current_state = move_down;
j = max_col; i++; // if moving down, increment row and set column to max
min_row += 1;
}
break;
case move_down:
if(i <= max_row) { // write to array till max row
output[idx] = *(input+i*col_size + j);
i++;
idx++;
} else {
current_state = move_left;
i = max_row; j--; // if moving left, set row to max and decrement column
max_col--;
}
break;
case move_left:
if(j >= min_col) { // write to array till min column
output[idx] = *(input+i*col_size + j);
j--;
idx++;
} else {
current_state = move_up;
j = min_col; i--; // if moving up, set column to min and decrement row
max_row--;
}
break;
case move_up:
if(i >= min_row) { // write to array till min row
output[idx] = *(input+i*col_size + j);
i--;
idx++;
} else {
current_state = move_right;
i = min_row; j++; // if moving right, set row to min and increment column
min_col += 1;
}
break;
default:
break;
}
The spiral traversal of a matrix can be implemented in much better and simpler way but you have tagged your question with state-machine, so I am assuming, you have intentionally included current_state in your code which is not at all required.
EDIT:
Fellow SO contributor @David C. Rankin added a comment -
I'm a bit lost on why current_state isn't needed -- you need a switch(var) regardless of that you call it. What is the point I"m obviously missing?
Below is the explanation:
Neither we need to maintain the current state nor we need to set next state at the end of current state when traversing a matrix in spiral manner because the traversal scheme itself define the path to traverse and the required information for every ring, like start/end row and start/end column, is already available.
E.g. Clockwise spiral traversal of a matrix -
Start from element at index [0][0] and traverse the outermost ring based on given number of rows and columns of matrix i.e. move right and traverse all elements of matrix till last column, then move down and traverse all elements of matrix till last row, then move left and traverse all elements of matrix till first column, then move up and traverse all elements of matrix till second row.
Now, if there are elements remain inside the ring traversed, reset the start/end row and start/end column and repeat the traversal again.
Here, no need to maintain any state and for every nested ring to traverse, start/end row and start/end column calculation is straight forward.
Demonstration:
#include <stdio.h>
#include <stdlib.h>
#define N 4
#define M 4
void print_array (int * arr, int n) {
for(int i = 0; i < n; ++i) {
printf (" %d", arr[i]);
}
printf ("\n");
}
void spiral_matrix (int rows, int cols, int input[rows][cols], int * output) {
int size = rows * cols;
int row_max = rows;
int col_max = cols;
int row_min = 0;
int col_min = 0;
int idx = 0;
while (idx < size) {
for (int j = col_min; j < col_max; ++j) {
output[idx++] = input[row_min][j];
}
for (int j = row_min + 1; j < row_max; ++j) {
output[idx++] = input[j][col_max - 1];
}
for (int j = col_max - 1; j > col_min ; --j) {
output[idx++] = input[row_max - 1][j - 1];
}
for (int j = row_max - 1; j > row_min + 1; --j) {
output[idx++] = input[j - 1][row_min];
}
row_max = row_max - 1;
col_max = col_max - 1;
row_min = row_min + 1;
col_min = col_min + 1;
}
}
int main (void) {
int A[N][M] = {{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};
int * spiral_out = malloc (N * M * sizeof (int));
if (!spiral_out) {
exit (EXIT_FAILURE);
}
spiral_matrix (N, M, A, spiral_out);
print_array (spiral_out, N * M);
free (spiral_out);
return 0;
}
Output:
# ./a.out
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10