## Sunday, August 3, 2014

### BombSweeper

Problem:
Overview:

Predict the likelihood that you'll win a mine sweeper like game.

Java Source:
```001: /*
002: TopCoder
003: Single Round Match: 156
004: Division: 2 / 1
005: Level: 2 / 1
006: Points: 600 / 300
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1778
008:  */
009:
010: public class BombSweeper {
011:
012:     /*
013:      * Converts the array of Strings into a 2-Dimensional array of
014:      * characters.  This will simplify working with the board.
015:      */
016:     private static char[][] generateBoard(String[] strs) {
017:
018:         char[][] charArray = new char[strs.length][strs.length()];
019:
020:         for (int row = 0; row < strs.length; row++) {
021:             for (int col = 0; col < strs.length(); col++) {
022:                 charArray[row][col] = strs[row].charAt(col);
023:             }
024:         }
025:
026:         return charArray;
027:     }
028:
029:     /*
030:      * Checks each of the 8 surrounding squares looking for bombs.  If a bomb
031:      * is found, returns true - otherwise returns false
032:      */
033:     private static boolean hasBombNeighbor(char[][] field, int row, int col) {
034:
035:         // Check row above
036:         if (row > 0) {
037:
038:             // Above and to the left
039:             if (col > 0) {
040:                 if (field[row - 1][col - 1] == 'B') { return true; }
041:             }
042:
043:             // Directly above
044:             if (field[row - 1][col] == 'B') { return true; }
045:
046:             // Above and to the right
047:             if (col < field.length - 1) {
048:                 if (field[row - 1][col + 1] == 'B') { return true; }
049:             }
050:         }
051:
052:         // Same row - To the left
053:         if (col > 0) {
054:             if (field[row][col - 1] == 'B') { return true; }
055:         }
056:
057:         // Same row - To the right
058:         if (col < field.length - 1) {
059:             if (field[row][col + 1] == 'B') { return true; }
060:         }
061:
062:         // Check row below
063:         if (row < field.length - 1) {
064:
065:             // Below and to the left
066:             if (col > 0) {
067:                 if (field[row + 1][col - 1] == 'B') { return true; }
068:             }
069:
070:             // Directly below
071:             if (field[row + 1][col] == 'B') { return true; }
072:
073:             // Below and to the right
074:             if (col < field.length - 1) {
075:                 if (field[row + 1][col + 1] == 'B') { return true; }
076:             }
077:         }
078:
079:         return false;
080:     }
081:
082:     public double winPercentage(String[] board) {
083:
084:         int numBombs = 0;
085:         int numWins = 0;
086:
087:         char[][] mineField = generateBoard(board);
088:
089:         /*
090:          * Loop through each position of the board.  For each position,
091:          * determine if it is a bomb, or has any neighbors that are bombs.
092:          */
093:         for (int row = 0; row < mineField.length; row++) {
094:             for (int col = 0; col < mineField.length; col++) {
095:                 if (mineField[row][col] == 'B') {
096:                     numBombs++;
097:                 } else if (hasBombNeighbor(mineField, row, col)) {
098:                     // doNothing
099:                 } else {
100:                     numWins++;
101:                 }
102:             }
103:         }
104:
105:         // This equation is given in the problem statement.
106:         return ((double) numWins / (double) (numWins + numBombs)) * 100.0;
107:     }
108: }```
Notes:

The equation for determining the likelihood of winning is given in the problem statement as (wins / (wins + losses)) where wins are the number of squares that are not bombs and do not have any neighbors that are bombs; and losses are squares that are bombs. Be sure to multiply by 100 to get this number as a percentage.

Quite often, I find it easier to work with a 2-Dimensional array of characters rather than the given String array. The method generateBoard() performs this simple conversion. With the 2-Dimensional char array, we can refer to each square using just its indices, and not have to mix an index with a String.charAt(). It's a personal preference, but I think board[row][col] is cleaner than board[row].charAt(col)

With the mineField created, lines 94-104 loop through each row and column testing to see if that position is a bomb, or if any of it's neighbors are bombs. If the position is a bomb, numBombs is incremented. If it's not a bomb, but a neighbor is, then nothing happens. And if it's not a bomb, and none of it's neighbors are either, then numWins is incremented.

hasBombNeighbor() determines if a given position has a bomb in any of the 8 positions surrounding it. Just be careful here to avoid checking a neighbor that falls outside the bounds of the board.

Once numBombs, and numWins are known, we can plug those into the given equation and return the result.