C Array Randomly Shrinks

Question

I'm writing a solution to the 'flea problem' on Project Euler (https://projecteuler.net/problem=213). The 'movement' of the 'fleas' and all that works fine. However, after a few turns (different amount every time) the array shrink to half of the original size (30 to 15 or 16, 20 to 10 or 11).

Any help would be appreciated.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main() {
//https://projecteuler.net/problem=213

int grid[30][30];
int size = sizeof(grid) / sizeof(grid[0]);

for(int x = 0; x < size; x++) { //Setting the fleas down.
    for (int y = 0; y < size; y++) {
        grid[x][y] = 1;
    }
}

srand(time(NULL)); //Setting the random stuff

for(int turn = 1; turn <= 50; turn++) {
    for(int x = 0; x < size; x++) { //Showing the full grid every turn.
        for (int y = 0; y < size; y++) {
            printf("%d", grid[x][y]);
        }
        printf("\n");
    }

    printf("\n\n\n");

    for(int x = 0; x < size; x++) {
        for(int y = 0; y < size; y++) {
            for(int flea = 0; flea < grid[x][y]; flea++) { //Moving the fleas.
                grid[x][y]--; //Taking them off of their cell.

                int direction = rand() % 4; // 3 is up, 2 is down, 1 is left, 0 is right

                while (x == 0 && y == 0 && (direction == 3 || direction == 1)) { //Grab a new direction if it's at the corner and wants to go off.
                    direction = rand() % 4;
                }
                while (x == 0 && y == size && (direction == 3 || direction == 0)) {
                    direction = rand() % 4;
                }
                while (x == size && y == 0 && (direction == 2 || direction == 1)) {
                    direction = rand() % 4;
                }
                while (x == size && y == size && (direction == 2 || direction == 0)) {
                    direction = rand() % 4;
                }

                while (x == 0 && direction == 3) { //Same, but for the edge.
                    direction = rand() % 4;
                }
                while (x == size && direction == 2) {
                    direction = rand() % 4;
                }
                while (y == 0 && direction == 1) {
                    direction = rand() % 4;
                }
                while (y == size && direction == 0) {
                    direction = rand() % 4;
                }

                switch (direction) {
                    case 3: //Up
                        grid[x][y - 1]++;

                        break;

                    case 2: //Down
                        grid[x][y + 1]++;

                        break;

                    case 1: //Left
                        grid[x - 1][y]++;

                        break;

                    case 0: //Right
                        grid[x + 1][y]++;

                        break;
                }
            }
        }
    }
}

int empty = 0;

for (int x = 0; x < size; x++) { //Counting the empties.
    for (int y = 0; y < size; y++) {
        if(grid[x][y] == 0) {
            empty++;
        }
    }
}

printf("%d", empty);

return 0;
}

Answer 1

The reported symptom was that the value of the size variable sometimes changes. This does not mean that the grid array is changing size. What it means is that there's a bug in the program that results in the size variable being overwritten. This is the result of incorrect bounds checks when writing to grid.

The bounds checks to see if the direction would take the flea off of the grid aren't right. Each of the while loops tests a single condition, generating a new direction until the direction satisfies that condition.

However, after a condition is satisfied, it is never checked again. If a later condition fails, and a new direction is chosen, is may violate any of the previous conditions without being detected. As a result, it may write past the bounds of the grid, causing memory corruption.

In addition, some of the edge tests are incorrect (they are checking the wrong edge for a given direction). Also, it's comparing x and y to size instead of size - 1.

This can be simplified and corrected as follows: First, there is no reason for 8 separate tests. The corners do not need to be special cases. It just needs to check the edges. Second, there needs to be a single loop that executes until all conditions are met. It can look like this:

int direction;
while (true) {
    direction = rand() % 4;
    if (direction == 0 && x == size - 1) continue;
    if (direction == 1 && x == 0) continue;
    if (direction == 2 && y == size - 1) continue;
    if (direction == 3 && y == 0) continue;
    break;
}

That's all that's needed to handle all of the edge conditions. If any condition fails, a continue statement is executed, which causes the loop to resume at the top. The loop only exits if all conditions are met and the break statement is executed. The key point is that when a new random number is chosen, all of the conditions are checked.

An alternative approach would be to instead construct an array of the valid directions, then choose one of the directions from the array, knowing in advance that it's valid. This has the advantage that rand() never has to be called more than once. The array would have length 4, but there would be either 2, 3, or 4 valid entries per use (2 for corners, 3 for non-corner edges, and 4 for non-corner, non-edge cells).

Answer 2

You're accessing invalid memory. From address sanitizer:

==10604==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7ffc433d0f14 at pc 0x55c6134daa01 bp 0x7ffc433d0eb0 sp 0x7ffc433d0ea0
READ of size 4 at 0x7ffc433d0f14 thread T0
    #0 0x55c6134daa00 in main /tmp/so/as.cpp:74
    #1 0x7fb3beae9d0a in __libc_start_main ../csu/libc-start.c:308
    #2 0x55c6134da159 in _start (/tmp/so/as+0x1159)

Address 0x7ffc433d0f14 is located in stack of thread T0 at offset 20 in frame
    #0 0x55c6134da224 in main /tmp/so/as.cpp:5

Line 74 matches with your left case:

                    case 1: //Left
                        grid[x - 1][y]++;

                        break;

Since asan aborts on the first address issue, which in this case is access out of bounds memory. On the same line though, you try to write to an invalid address--at some point you'll end up trampling memory.

You have the right idea with your traps, but a few of them have buggy logic (in the case of left, you need to check for x == 0 and you're actually checking y == 0).

Answer 3

other posters have diagnosed the issue; I suggest it would be easier to understand if the direction validation code was embedded into the state update code:

for(;;) {
  switch(rand() % 4) {
    case 0:
      if (y == 0) continue;
      grid[x][y - 1]++;
      break;
    case 1:
      if (y == size - 1) continue;
      grid[x][y + 1]++;
      break;
    case 2:
      if (x == 0) continue;
      grid[x - 1][y]++;
      break;
    case 3:
      if (x == size - 1) continue;
      grid[x + 1][y]++;
      break;
    }
    break;
}

or a goto might make it more obvious what's going on!

I also note that you're only moving half the fleas. your loop does:

            for(int flea = 0; flea < grid[x][y]; flea++) { //Moving the fleas.
                grid[x][y]--; //Taking them off of their cell.

when it should probably do:

            while(grid[x][y] > 0) { //Moving the fleas.
                grid[x][y]--; //Taking them off of their cell.