Minesweeper field marking

Question

I just did an interview where the last challenge was to write a function that reads a minesweeper matrix from a file and marks how many bombs there are around each cell. I had 20 min and had a < comparison that should have been <=. My main question is how I could have done it faster since it only took me 5 min to locate the bug and fix it. The other thing I would like to know is what a reviewer probably would think about it.

Here's my hacky code (the only requirement was to produce the correct output):

#include <stdio.h>
#include <string.h>

void read_matrix(char* dest, char const* file)
{
  FILE* input = fopen(file, "r");
  char temp[128];
  int d= 0;

  fread(temp, 1, sizeof temp, input);

  for(int i = 0; i < 128; ++i){
    if(' ' != temp[i] && '\n' != temp[i]){
      dest[d++] = temp[i];
    }
  }
  fclose(input);
}

char _grid_at(char const* grid, int x, int y)
{
  return grid[y * 8 + x];
}

int _surround_count(char const* grid, int x, int y)
{
  int count = 0;
  int x0 = x;
  int x1 = x;
  int y0 = y;
  int y1 = y;

  if(x > 0){
    x0 = x - 1;
  }
  if(x < 7){
    x1 = x + 1;
  }
  if(y > 0){
    y0 = y - 1;
  }
  if(y < 7){
    y1 = y + 1;
  }

  // here's where the problem was
  for(x = x0; x <= x1; ++x){
    for(y = y0; y <= y1; ++y){
      if('X' == _grid_at(grid, x, y)){
        count += 1;
      }
    }
  }

  return count;
} 

void mark_field(char* dest, char const* src)
{  
  for(int x = 0; x < 8; ++x){
    for(int y = 0; y < 8; ++y){
      if('X' != src[y*8+x]){      
        dest[y*8 + x] = '0' + _surround_count(src, x, y);
      }
      else {
        dest[y*8 + x] = 'X';
      }
    }
  }
}

void print_field(char const* field)
{
  for(int i = 0; i < 64; ++i){
    putchar(field[i]);
    if((i & 7) == 7){
      putchar('\n');
    }
  }

}

int main(int argc, char* argv[])
{
  char matrix[64];

  read_matrix(matrix, argv[1]);
  print_field(matrix);
  puts("------------");

  char count[64];
  mark_field(count, matrix);
  print_field(count);

  return 0;
}

Input:

X O O X X X O O
O O O O X O X X
X X O X X O O O
O X O O O X X X
O O X X X X O X
X O X X X O X O
O O O X O X O X
X O X X O X O X

Output:

X 1 1 X X X 3 2
3 3 3 5 X 5 X X
X X 3 X X 5 5 4
3 X 5 5 6 X X X
2 4 X X X X 6 X
X 3 X X X 5 X 3
2 4 5 X 6 X 5 X
X 2 X X 4 X 4 X

Answer 1

Interview Notices

Check the result of system calls

FILE* input = fopen(file, "r");      // Can return null
fread(temp, 1, sizeof temp, input);  // returns the number read (which may not be sizeof temp
fclose(input);                       // Can fail

Style

Personally don't like:

' ' != temp[i] && '\n' != temp[i]

Reads way too much like Yoda conditionals (which went out of style ten years ago). Its not the natural way to expresses a test in your brain.

temp[i] != ' ' && temp[i] != '\n'

Reads much more naturally (at least to an English speaker). Though in an interview I would not knock points off for this. If I hired you I would re-train you to do it the other way though.

Is this the correct/good interface?

void read_matrix(char* dest, char const* file)

I don't like that dest is an array of char. Are you optimizing for space? Where you asked to optimize for space? I would change that to an array of int, as that expresses intent much more clearly.

void read_matrix(int* dest, char const* file)

I think manually checking for space is making this complex. I would have used the scanf library function to do that work for me.

  for(int i = 0; i < 128; ++i){
    if(' ' != temp[i] && '\n' != temp[i]){
       dest[d++] = temp[i];
    }
 }


// note: I would have made the `dest` array integers
for(int i = 0; i < 128; ++i){
    if (sscanf(temp, " %d", dest + i) != 1) {
        // ERROR
    }
}

Functions beginning with an underscore and a lowercase letter are reserved in the global scope.

char _grid_at(char const* grid, int x, int y)
int  _surround_count(char const* grid, int x, int y)
//   ^^^ reserved identifier.

Don't change the first letter to upper case as an underscore followed by an upper case letter is reserved in all contexts.

I can see why you had an issue (all those tests).

A simple optimization for this is to place your grid inside a grid that is one square larger vertically and horizontally. So if you have an 8×8 grid, place it inside a 10×10 grid. Then mark all the cells around the side as having zero in them.

Then when you call surround_count() you can add the cost of all the squares around the cell:

int surround_count(char const* grid, int x, int y)
{
     assert ( 1 <= x && x <= 8 && 1 <= y && y <= 8);

     int count = 0;
     for(int h = -1; h <= 1; ++h) {
         for(int v = -1; v <= 1; ++v) {
             count += isBombAt(grid, x + h, y + v);
         }
     }
     return 0;
 }