Sunday, August 30, 2015

InstantRunoff

Problem:

TopCoder Problem Statement - InstantRunoff
Single Round Match 175 Round 1 - Division I, Level One
Single Round Match 175 Round 1 - Division II, Level Two

Overview:

Determine the winner of a run off election by following the given rules.

Java Source:
     1
     1 import java.util.HashMap;
     2 import java.util.HashSet;
     3 import java.util.Map;
     4 import java.util.Set;
     5
     6 public class InstantRunoff {
     7
     8     public String outcome(String candidates, String[] ballots) {
     9
    10         Set activeCandidates = new HashSet<>();
    11
    12         for (Character c : candidates.toCharArray()) {
    13             activeCandidates.add(c);
    14         }
    15
    16         while (true) {
    17
    18             // Count the number of first place votes for each candidate.
    19             Map firstPlaceVotes = new HashMap<>();
    20
    21             for (Character c : activeCandidates) {
    22                 firstPlaceVotes.put(c, 0);
    23             }
    24
    25             for (String b : ballots) {
    26                 Character c;
    27
    28                 c = b.charAt(0);
    29                 firstPlaceVotes.put(c, firstPlaceVotes.get(c) + 1);
    30             }
    31
    32             // Do we have a clear winner?
    33             for (Character c : activeCandidates) {
    34                 if (firstPlaceVotes.get(c) >=
    35                         ((ballots.length / 2) + 1)) {
    36                     return "" + c;
    37                 }
    38             }
    39
    40             // Get the least first place votes
    41             int minFirstPlaceVotes = Integer.MAX_VALUE;
    42
    43             for (Character c : activeCandidates) {
    44                 minFirstPlaceVotes = Math.min(minFirstPlaceVotes,
    45                         firstPlaceVotes.get(c));
    46             }
    47
    48             // Remove all candidates with the most last place votes
    49             Set toRemove = new HashSet<>();
    50             for (Character c : activeCandidates) {
    51                 if (firstPlaceVotes.get(c) == minFirstPlaceVotes)
    52                     toRemove.add(c);
    53             }
    54
    55             for (Character c : toRemove) {
    56                 activeCandidates.remove(c);
    57                 for (int i = 0; i < ballots.length; i++) {
    58                     ballots[i] = ballots[i].replaceFirst("" + c, "");
    59                 }
    60             }
    61
    62             if (activeCandidates.size() == 0) return "";
    63         }
    64
    65     }
    66
    67 }
Notes:

This solution basically just follows the rules for the election as given in the problem statement. First, it creates a set of remaining candidates, then it enters a while loop which will not terminate until either a winner is found, or the set of remaining candidates becomes empty.

For each iteration of the loop, we count up the number of first place votes that each active candidate has received. If any of the candidates receives more than half of the possible votes, then they are declared the winner. Be careful in checking for a majority, the equation on lines 34 and 35 is easy to get wrong.

If there is no clear winner, then we look for the least number of first place votes, and remove any candidate that has that number of first place votes. Here, we remove those candidates from both the active candidates set, as well as from all the ballots. The easiest, although perhaps not the most efficient way is to do the replacement on line 58.

Finally, if there are no more active candidates, then we return the empty string.

ClockWalk

Problem:

TopCoder Problem Statement - ClockWalk
Single Round Match 175 Round 1 - Division II, Level One

Overview:

Determine the ending time after a series of jumps forward and back.

Java Source:
     1 public class ClockWalk {
     2
     3  public int finalPosition(String flips) {
     4   int result = 0;
     5
     6   for (int i = 0; i < flips.length(); i++)  {
     7    if (flips.charAt(i) == 'h')  result += i + 1;
     8    else result -= i + 1;
     9   }
    10
    11   result %= 12;
    12
    13   return (result <= 0) ? (result + 12) : result;
    14  }
    15
    16 }
Notes:

For each character in flips we want to either move forward or backward around a clock face. The number of steps is 1 plus the index of the current character. 1 for position 0, 2 for position 1, etc.

If the character is 'h', we use += to advance forward. Otherwise -= to move backward.

After all the moves have been made, we mod the result by 12, and if the result is less than or equal to 0, we add 12.

Monday, August 10, 2015

MineField

Problem:

TopCoder Problem Statement - MineField
Single Round Match 169 Round 1 - Division I, Level One

Overview:

Given a set of coordinates representing bombs, generate a board suitable for playing MineField.

Java Source:
     1 import java.util.*;
     2 import java.math.*;
     3 import static java.lang.Math.*;
     4
     5 public class MineField {
     6
     7  private static final int SIZE = 9;
     8  private static final char MINE_CHAR = 'M';
     9
    10  char[][] mineField = new char[SIZE][SIZE];
    11
    12  public String[] getMineField(String mineLocations) {
    13
    14   // Initialize the mine Field
    15   for (int row = 0; row < SIZE; row++)  {
    16    for (int col = 0; col < SIZE; col++)  {
    17     mineField[row][col] = '0';
    18    }
    19   }
    20
    21   // Converts all parenthesis and commas to spaces.
    22   String input = mineLocations
    23       .replaceAll("\\(", " ")
    24       .replaceAll("\\)", " ")
    25       .replaceAll(",", " ");
    26
    27   // A scanner that uses spaces as the delimiter
    28   Scanner sc = new Scanner(input);
    29   sc.useDelimiter("\\s+");
    30
    31   // Read all the coordinates and add the mines.
    32   while (sc.hasNextInt())  {
    33    int row = sc.nextInt();
    34    int col = sc.nextInt();
    35    addMine(row,col);
    36   }
    37
    38   // Create the return value.
    39   String[] result = new String[SIZE];
    40
    41   for (int i = 0; i < SIZE; i++)  {
    42    result[i] = new String(mineField[i]);
    43   }
    44
    45   return result;
    46  }
    47
    48  private void addMine(int row, int col)  {
    49
    50   mineField[row][col] = MINE_CHAR;
    51
    52   /*
    53   * Increment the value in all surrounding squares
    54   * checking to ensure that we stay within the bounds
    55   * of the board, and that the other square is not
    56   * already marked as a mine.
    57   */
    58   for (int r = row - 1; r <= row + 1; r++)  {
    59    for (int c = col - 1; c <= col + 1; c++)  {
    60
    61     if ((r >= 0) && (r < SIZE) &&
    62       (c >= 0) && (c < SIZE) &&
    63       (mineField[r][c] != MINE_CHAR))  {
    64
    65      // Increase the value of the neighbor.
    66      mineField[r][c]++;
    67     }
    68    }
    69   }
    70
    71  }
    72 }
      
Notes:

This is a pretty easy Divison 1 problem, with just a few tricks to overcome. First, I'll begin by saying I was tripped up by the ordering of the coordinates. I assumed that the numbers were in the form (x, y). They're not. The description says they're given as (row, col). In other words (y, x). After seeing my output sideways, I tracked the error down and fixed it.

The first problem to solve is parsing the input. For this, first I replaced all parenthesis and commas with spaces. Then I created a scanner that uses whitespace as the delimeter. With that, I can just use a pair of nextInt() calls to get the coordinates until they run out.

I find these problems much easier to work with using char arrays. I'll often convert the given String[] into a char[][] just to simplify. In this case, I represent the mineField as a char[][] and then convert it to a String[] when returning the result.

With the coordinates, and the mineField, the next problem is to add the mine to the current board. That's just a matter of setting that location to 'M', and then updating all the neighbors. I use a nested for loop to visit all the neighbors of the given location working top to bottom and left to right. For each location, check to ensure that we're not outside the boundaries of the array, and that the square is not already marked as a mine. If that test passes, then increment the value stored there. Since we can treat chars as ints here, mineField[r][c]++ will work nicely.

Saturday, August 8, 2015

CrossWord

Problem:

TopCoder Problem Statement - CrossWord
Single Round Match 174 Round 1 - Division II, Level One

Overview:

Determine how many slots of a given length appear horizontally in a given crossword puzzle.

Java Source:
     1 public class CrossWord {
     2
     3     public int countWords(String[] board, int size) {
     4
     5         int total = 0;
     6
     7         /*
     8         * Sum up the number of horizontal slots in each
     9         * of the rows in the board.
    10         */
    11         for (String s : board) {
    12             total += countHorizontalSlots(s, size);
    13         }
    14
    15         return total;
    16     }
    17
    18     /*
    19     * Count the number of horizontal slots in a
    20     * single row of the board.
    21     */
    22     private static int countHorizontalSlots(String s, int size) {
    23
    24         // Number of horizontal slots found.
    25         int num = 0;
    26
    27         // Number of continuous spaces found.
    28         int spaces = 0;
    29
    30         // Loop through each character in the given string.
    31         for (int i = 0; i < s.length(); i++) {
    32
    33             /*
    34             * An 'X' marks the end of a slot.  So when an
    35             * 'X' is encountered, if the number of spaces
    36             * matches the size we're looking for, then
    37             * increase the count.
    38             * Set spaces to 0 whenever an 'X' is found.
    39             */
    40             if (s.charAt(i) == 'X') {
    41                 if (spaces == size) {
    42                     num++;
    43                 }
    44                 spaces = 0;
    45
    46             } else {
    47
    48                 /*
    49                 * If it's not an 'X', then increment the number
    50                 * of open spaces found.
    51                 */
    52                 spaces++;
    53             }
    54
    55         }
    56
    57         /*
    58         * This condition is met when the slot leads up to the
    59         * right edge of the board.
    60         */
    61         if (spaces == size) {
    62             num++;
    63         }
    64
    65         return num;
    66     }
    67 }
Notes:

The first step is to divide the crossword up into individual rows. For each row, we'll add up the number of slots, and then return the sum.

The count the slots in an single row we'll step through each character of the given string looking for 'X's since the 'X' character terminates a slot. If any character other than an 'X' is encountered, we simply increase the number of spaces seen. When an 'X' appears, we check to see if the number of spaces matches what we're looking for. If so, increment the count for this line.

Be careful to include the case where the slot ends at the end of the string. The last check - "if (spaces == size)" takes care of this.