Sunday, August 3, 2014

BombSweeper

Problem:

TopCoder Problem Statement - BombSweeper

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[0].length()];
019: 
020:         for (int row = 0; row < strs.length; row++) {
021:             for (int col = 0; col < strs[0].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[0].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[0].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[0].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[0].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.

No comments:

Post a Comment