Technical Interview Questions, Answers, and Tips: August 2010

Question: The interviewer first discussed the game of minesweeper and the gave a reverse minesweeper problem where the specifications were as follows:
1. A block of M rows by N columns is given
2. Each item can either be a mine or not a mine
3. The location of the mines in the block is given by the character *
4. Normal/safe squares are marked by '.' (dots)

See the below table and write a program to print the number of mines adjacent to the safe blocks.

Update: This problem is from the book "Programming Challenges - The Programming Contest Training Manual - Skiena".

Example:

input	output
4 4	Field #1:
*...	*100
....	2210
.*..	1*10
....	1110
3 5	Field #2:
**...	**100
.....	33200
.*...	1*100
6 5	Field #3:
...	232
..*	33*
.....	35453
*****	*****
...	353
.....	11211
1 1	Field #4:
.	0
1 1	Field #5:
*	*
2 2	Field #6:
*.	*2
.*	2*
0 0

Program:

#include <stdio.h>
#include <malloc.h>
#define MINE -1

void Read_Arrays();
void FillNumbers(int * array, int rows, int cols);
void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col);
void print_array(int *array, int rows, int cols);

int get_val(int *array, int row_index, int col_index, int cols);
// increment the value at the specified array location
int inc_val(int *array, int row_index, int col_index, int cols);

int main(void)
{
        Read_Arrays();
}
void Read_Arrays()
{
        int rows = 0;
        int cols = 0;

        int cur_row_index;

        int *array;

        char line[256];
        int field_num = 0;

        while(fgets(line, 256, stdin) != NULL)
        {
                int i=0;
                if(rows == 0 && cols == 0)
                {
                        sscanf(line, "%d %d", &rows, &cols);
                        array = (int *)malloc(rows*cols*sizeof(int));

                        if(array == NULL)
                        {
                                printf("failed to allocate memory\n");
                                return;
                        }
                        if(rows == 0 || cols == 0)
                        {
                                return;
                        }
                        cur_row_index = 0;
                        continue;
                }

                for(i= 0; i<cols; i++)
                {
                        char c = line[i];
                        if(c == '*')
                                c = MINE;
                        else
                                c = 0;
                        *(array + (cur_row_index*cols)+i) = c;
                }

                //if we scanned the specified number of rows lets process the array
                if(cur_row_index == rows - 1)
                {
                        FillNumbers(array, rows, cols);
                        printf("Field #%d:\n", ++field_num);
                        print_array(array, rows, cols);
                        free(array);
                        rows = 0;
                        cols = 0;
                }
                else
                {
                        cur_row_index++;
                }

        }
}

/* fill numbers in the array instead of dots */
void FillNumbers(int *array, int rows, int cols)
{
        int i, j;
        for(i=0; i<rows; i++)
        {
                for(j=0; j < cols; j++)
                {
                        if(*(array + (i*cols) + j) == MINE)
                        {
                                UpdateNeighbors(array, i, j, rows, cols);
                        }
                }
        }
}

/* this function will increment mine count for the neighbors of the mine */
void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col)
{
        if(row_index-1 >= 0)
        {
                if(col_index - 1 >= 0)
                        inc_val(array, row_index - 1, col_index -1, max_col);
                inc_val(array, row_index -1, col_index, max_col);
                if(col_index + 1 < max_col)
                        inc_val(array, row_index -1, col_index + 1, max_col);
        }

        if(col_index - 1 >= 0)
                inc_val(array, row_index, col_index - 1, max_col);
        if(col_index + 1 < max_col)
                inc_val(array, row_index, col_index + 1, max_col);

        if(row_index + 1 < max_row)
        {
                if(col_index - 1 >= 0)
                        inc_val(array, row_index + 1, col_index -1, max_col);
                inc_val(array, row_index + 1, col_index, max_col);
                if(col_index + 1 < max_col)
                        inc_val(array, row_index + 1, col_index+1, max_col);
        }
}

int get_val(int *array, int row_index, int col_index, int cols)
{
        return  *(array + (row_index * cols) + col_index);
}
/* we increment only if there is no mine present at the specified location */
int inc_val(int *array, int row_index, int col_index, int cols)
{
        int val = get_val(array, row_index, col_index, cols);
        if(val == MINE) return;
        *(array + (row_index * cols) + col_index) += 1;
}

void print_array(int *array, int rows, int cols)
{
        int i, j;
        for(i = 0; i < rows; i++)
        {
                for(j = 0; j < cols; j++)
                {
                        int val = get_val(array, i, j, cols);
                        if(val != MINE)
                                printf("%d", val);
                        else
                                printf("%c", '*');
                }
                printf("\n");
        }
}

Reverse Minesweeper