TopCoder Problem Statement - BombSweeper
Predict the likelihood that you'll win a mine sweeper like game.
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: }
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