Codes

MineSweeper displaying bomb and its neighbor

MinwSweeper

Wading through the Programming Challenge book , I find this problem of Mine Sweeper interesting:

Given a text file of bomb information, output the bomb location(=’*’ symbol) and all the bomb neighborhood’s count.

Why? Because Minesweeper game is fund, and for the most part it is the only game you play back in the day(nostalgia)

For example, bomb.txt has the following input:

                                               4 4 #the dimension of the grid

.*..

.*..

….

….

The output should be like this:

2*2.

2*2.

111.

….

How do you solve this?

1. Naive Approach

A cell in the grid has 8 neighbors :

[top-left][top-mid][top-right]

[      -left][—ME—][     -right]

[bot-left][bot-mid][bot-right]

Everybody else outside of this frame is considered far-neighbor, and does not count.(In reality, can you not hear and see any notification of a bomb exploding if your house is next to the neighbor of the neighbor of the victim!!!!)

If we represent the grid as a nxn dimension arrays, then a really simple and naive approach to printing the bombs and their neighborhood is to check every cell, in every cell check every neighbor. Problem solved? No. This is terrible.Why?

Let’s take an example of a 4×4 matrix. You have to iterate the array, and check the bomb, and output.How many check were there?

a loop of 4×4 element = 16 and in each loop a 8-if statement or if you are smart you can the loop but it is basically the same. That is 16*8 = 128 check

Speaking of complexity, for an array of nxn, the complexity is: O(8n^2 ) = O(n^2).BADDDDDDDDDDDDDDD!!!!!

Can we do better?

2. Improved Approach

Checking everything, and every possibility is badly overkill. Can we reduce the number of check? Maybe

Notice, that in the naive approach, we check every cell, regardless of the number of bomb. Can we modify it so that it is bomb-focus, that is checking only the number of bomb? –> LinkList comes into help

As we scan the input file, we just store the location of the bomb into this list, then we can just iterate the list and update the neighbor. Note that, the neighbor count of bomb will automatically increase if the neighbor location is in between two bomb field, because as each bomb in each field check neighbor, the same neighbor would be increased the count.

We have just reduce the problem from O(n^2) to O(n), n is the number of bomb.

Can we do better? I don’t know

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s