I recently finished making an algorithm for a project I'm working on.
Briefly, a part of my project needs to fill a matrix, the requirements of how to do it are these:
- Fill the matrix in form of spiral, from the center.
- The size of the matrix must be dynamic, so the spiral can be large or small.
- Every two times a cell of the matrix is filled, //DO STUFF must be executed.
In the end, the code that I made works, it was my best effort and I am not able to optimize it more, it bothers me a bit having had to use so many ifs, and I was wondering if someone could take a look at my code to see if it is possible to optimize it further or some constructive comment (it works well, but it would be great if it was faster, since this algorithm will be executed several times in my project). Also so that other people can use it!
#include <stdio.h>
typedef unsigned short u16_t;
const u16_t size = 7; //<-- CHANGE HERE!!! just odd numbers and bigger than 3
const u16_t maxTimes = 2;
u16_t array_cont[size][size] = { 0 };
u16_t counter = 3, curr = 0;
u16_t endColumn = (size - 1) / 2, endRow = endColumn;
u16_t startColumn = endColumn + 1, startRow = endColumn + 1;
u16_t posLoop = 2, buffer = startColumn, i = 0;
void fillArray() {
if (curr < maxTimes) {
if (posLoop == 0) { //Top
for (i = buffer; i <= startColumn && curr < maxTimes; i++, curr++)
array_cont[endRow][i] = counter++;
if (curr == maxTimes) {
if (i <= startColumn) {
buffer = i;
} else {
buffer = endRow;
startColumn++;
posLoop++;
}
} else {
buffer = endRow;
startColumn++;
posLoop++;
fillArray();
}
} else if (posLoop == 1) { //Right
for (i = buffer; i <= startRow && curr < maxTimes; i++, curr++)
array_cont[i][startColumn] = counter++;
if (curr == maxTimes) {
if (i <= startRow) {
buffer = i;
} else {
buffer = startColumn;
startRow++;
posLoop++;
}
} else {
buffer = startColumn;
startRow++;
posLoop++;
fillArray();
}
} else if (posLoop == 2) { //Bottom
for (i = buffer; i >= endColumn && curr < maxTimes; i--, curr++)
array_cont[startRow][i] = counter++;
if (curr == maxTimes) {
if (i >= endColumn) {
buffer = i;
} else {
buffer = startRow;
endColumn--;
posLoop++;
}
} else {
buffer = startRow;
endColumn--;
posLoop++;
fillArray();
}
} else if (posLoop == 3) { //Left
for (i = buffer; i >= endRow && curr < maxTimes; i--, curr++)
array_cont[i][endColumn] = counter++;
if (curr == maxTimes) {
if (i >= endRow) {
buffer = i;
} else {
buffer = endColumn;
endRow--;
posLoop = 0;
}
} else {
buffer = endColumn;
endRow--;
posLoop = 0;
fillArray();
}
}
}
}
int main(void) {
array_cont[endColumn][endColumn] = 1;
array_cont[endColumn][endColumn + 1] = 2;
//DO STUFF
u16_t max = ((size * size) - 1) / maxTimes;
for (u16_t j = 0; j < max; j++) {
fillArray();
curr = 0;
//DO STUFF
}
//Demostration
for (u16_t x = 0; x < size; x++) {
for (u16_t y = 0; y < size; y++)
printf("%-4d ", array_cont[x][y]);
printf("\n");
}
return 0;
}
Notice that the numbers along the diagonal (1, 9, 25, 49) are the squares of the odd numbers. That's an important clue, since it suggests that the 1 in the center of the matrix should be treated as the end of a spiral.
From the end of each spiral, the x,y coordinates should be adjusted up and to the right by 1. Then the next layer of the spiral can be constructed by moving down, left, up, and right by the same amount.
For example, starting from the position of the 1, move up and to the right (to the position of the 9), and then form a loop with the following procedure:
move down, and place the 2
move down, and place the 3
move left, and place the 4
move left, and place the 5
etc.
Thus the code looks something like this:
int size = 7;
int matrix[size][size];
int dy[] = { 1, 0, -1, 0 };
int dx[] = { 0, -1, 0, 1 };
int directionCount = 4;
int ringCount = (size - 1) / 2;
int y = ringCount;
int x = ringCount;
int repeatCount = 0;
int value = 1;
matrix[y][x] = value++;
for (int ring = 0; ring < ringCount; ring++)
{
y--;
x++;
repeatCount += 2;
for (int direction = 0; direction < directionCount; direction++)
for (int repeat = 0; repeat < repeatCount; repeat++)
{
y += dy[direction];
x += dx[direction];
matrix[y][x] = value++;
}
}