## 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()) {
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) {
23             }
24
25             for (String b : ballots) {
26                 Character c;
27
28                 c = b.charAt(0);
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) {
46             }
47
48             // Remove all candidates with the most last place votes
49             Set toRemove = new HashSet<>();
50             for (Character c : activeCandidates) {
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();
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
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.