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 grid, place it inside a ×ばつ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;
 }

• Douglas: I specifically asked about the return values and didn't handle to save time. I chose char for the read_matrix() because the file has either 'X' or 'O'. The underscored names is a convention I use to write static functions, which I didn't mark as such because of time pressure. The 9x9 without checks is a great idea. I also shouldn't have used flat arrays.
• chux: " " not needed in sscanf(temp, " %d", dest + i). sscanf(temp, "%d", dest + i) would function the same
• Loki Astari: @Douglas: That habit for global functions is one you are going to have to change. Those identifiers are reserved for use by the implementation. The C standard: See Section 7.1.3 Reserved identifiers => All identifiers that begin with an underscore are always reserved for use as identifiers with file scope in both the ordinary and tag name spaces.
• Loki Astari: I understand why you choose char I just think it is the wrong choice. As you are reading into a grid that is used to count numbers. So by using int rather than char you are imparting information to the next programmer about the intent of the grid. Unless this is a Minesweeper solver for an embedded device were memory is exceedingly limited and you want to squeeze out every byte).
• Douglas: @LokiAstari I don't use leading underscores for global functions, only for variables and functions which are only visible in the same file, isn't that exactly what they are reserved for?