Sunday, November 22, 2015

SimpleCalculator

Problem:

TopCoder Problem Statement - SimpleCalculator
Single Round Match 178 Round 1 - Division II, Level One

Overview:

Implement a simple calculator that can handle addition, subtraction, multiplications, and division.

Java Source:
     1 public class SimpleCalculator {
     2
     3  public int calculate(String input) {
     4
     5   String[] ints = input.split("[+\\-\\*\\/]");
     6
     7   char op = input.charAt(ints[0].length());
     8
     9   int i1 = Integer.parseInt(ints[0]);
    10   int i2 = Integer.parseInt(ints[1]);
    11
    12   if ('+' == op) return i1 + i2;
    13   if ('-' == op) return i1 - i2;
    14   if ('*' == op) return i1 * i2;
    15   return i1 / i2;
    16
    17  }
    18
    19 }
Notes:

The only tricky part here is parsing the input to obtain the two integers and the operand. We can use the regular expression on line 5 for this. This will look for any of the characters (+, -, *, or /) and split the input into the integer that comes before and after the operator. When constructing the regular expression, you'll need to use \\ to escape some of the characters.

int[0] will hold the first number. Thus, we can obtain the operator buy using the length of int[0]. This is done on line 7. We can use Integer.parseInt() to get the integer values from the strings.

Then it's a simple matter of checking the value of the operator and performing the correct operation.

Tuesday, October 20, 2015

BirthdayOdds

Problem:

TopCoder Problem Statement - BirthdayOdds
Single Round Match 174 Round 1 - Division I, Level One
Single Round Match 174 Round 1 - Division II, Level Two

Overview:

Calculate the mininum number of people required to assure that the probability of two people sharing a birthday meets the given threshold. The number of days in a year may vary.

Java Source:
     1
     2
     3 public class BirthdayOdds {
     4
     5  public int minPeople(int minOdds, int daysInYear) {
     6
     7   double pA = 1.0;
     8   double days = (double) daysInYear;
     9   double cutOff = 1.0 - (minOdds / 100.0);
    10
    11   int numPeople = 1;
    12
    13   while (pA > cutOff)  {
    14    pA *= ((double) (daysInYear - numPeople) / days);
    15    numPeople++;
    16   }
    17
    18   return numPeople;
    19
    20  }
    21 }
Notes:

For a detailed discussion of the Birthday Problem, see the wikipedia entry here. This solution is based on the formula given in the "Calculating the probability" section.

Essentially we're calculating the probability that there is not a match, and then adding more and more people thus reducing that probability until a certain threshold is met. That threshold is (1 - minOdds) since we're calculating the probability of not matching whereas minOdds is the probability of a match.

pA begins at 1 (i.e. daysInYear / daysInYear), then is multiplied by (daysInYear - 1 / daysInYear), (daysInYear - 2 / daysInYear), (daysInYear - 3 / daysInYear), ... With each multiplication pA gets smaller until it falls under the cutoff.

RGBColor

Problem:

TopCoder Problem Statement - RGBColor
Single Round Match 176 Round 1 - Division II, Level One

Overview:

Compute the compliment of the given RGB color.

Java Source:
     1 import java.util.*;
     2 import java.math.*;
     3 import static java.lang.Math.*;
     4
     5 public class RGBColor {
     6
     7     private static final int RGB_MAX = 255;
     8     private static final int GREY_TOLERANCE = 32;
     9
    10  public int[] getComplement(int[] rgb) {
    11
    12   int[] compliment = new int[rgb.length];
    13
    14         boolean isGrey = true;
    15
    16         for (int i = 0; i < rgb.length; i++)  {
    17             compliment[i] = RGB_MAX - rgb[i];
    18             if (Math.abs(rgb[i] - compliment[i]) > GREY_TOLERANCE) isGrey = false;
    19         }
    20
    21         if (isGrey)  {
    22             for (int i = 0; i < rgb.length; i++)  {
    23                 compliment[i] = (rgb[i] >= 128) ? rgb[i] - 128 : rgb[i] + 128;
    24             }
    25         }
    26
    27         return compliment;
    28
    29  }
    30 }
Notes:

We need to deal with two separate cases here: the color may meet the given definition of grey, or it may not. The trouble is, we won't know if it's considered grey or not until we've examined all three colors. We'll start by assuming that the color is grey, and then flip the isGrey flag to false if we find a red, green, or blue value whose compliment exceeds GREY_TOLERANCE.

We start by creating the output array named compliment. Then for each value in rgb, we calculate the corresponding compliment by subtracting the color in the current position of rgb from RGB_MAX. If the difference between a color and its compliment exceeds GREY_TOLERANCE, then we'll set isGrey to false.

After red, green, and blue have all been evaluated, if isGrey is still true then we need to handle it according to the instructions for a grey color. For each position in rgb, if the value is greater than or equal to 128, we subtract 128, otherwise add 128. This value will overwrite the value in compliment[] that was stored earlier.

Saturday, October 10, 2015

Removal

Problem:

TopCoder Problem Statement - Removal
Single Round Match 177 Round 1 - Division I, Level Two
Single Round Match 177 Round 1 - Division II, Level Three

Overview:

Remove items from a list filling in the space by shifting all following elements up one. Return the item at the given position after all the removals.

Java Source:
     1 public class Removal {
     2
     3  public int finalPos(int n, int k, String[] remove) {
     4
     5   for (int i = remove.length - 1; i >= 0; i--)  {
     6
     7    String[] hilo = remove[i].split("-");
     8    int lo = Integer.parseInt(hilo[0]);
     9    int hi = Integer.parseInt(hilo[1]);
    10
    11    if (k >= lo)  {
    12     k += (hi - lo + 1);
    13    }
    14
    15    // If k < 0, then we've overflowed, return a -1.
    16    if ((k > n) || (k < 0)) return -1;
    17   }
    18
    19   return k;
    20  }
    21
    22 }
Notes:

You might assume that you could use a built-in data structure, such as a linked list to solve the problem. Just initialize the list, and then let it do the removals for you. However, it pays to take a look at the constraints first. The number of elements can be up to 2,000,000,000 which is way too much to fit into the allotted 64MB.

The solution is to think about how k's position changes as elements in front of it are removed. Elements that are greater than k don't matter when they're removed since these won't affect k's position.

We start at the end work backwards through each String in remove. First, parse out the lo and hi elements of the string. Then, if lo is less than k, we'll adjust k's position accordingly. The number of elements removed is given by (hi - lo + 1). So, we increase k's value by that amount to get it's position before the removals.

After working backward through all the elements in remove, the value of k will be it's original starting position which is the value we want to return.

Be careful to check the value of k after each addition. If it's ever greater than n, we'll return -1. The addition could also cause an overflow. You could convert k to a long to prevent this, or just check the value to see if it becomes negative. Since the value of hi will be 2 billion or less, it will fit into an int. Adding 2 billion to a positive int and causing an overflow will always result in a negative number.

Thursday, October 8, 2015

Matching

Problem:

TopCoder Problem Statement - Matching
Single Round Match 176 Round 1 - Division I, Level One
Single Round Match 176 Round 1 - Division II, Level Two

Overview:

Find the card which completes the pattern. For each group of characteristics, the matching card must either share the trait with the other two cards, or all three cards must have a different value.

Java Source:
     1 public class Matching {
     2
     3  private static final String[][] TRAITS = {
     4    {"CIRCLE", "SQUIGGLE", "DIAMOND"},
     5    {"BLUE", "RED", "GREEN"},
     6    {"SOLID", "STRIPED", "EMPTY"},
     7    {"ONE", "TWO", "THREE"}
     8  };
     9
    10  public String[] findMatch(String[] first, String[] second) {
    11
    12   String[] result = new String[4];
    13
    14   for (int i = 0; i < TRAITS.length; i++)  {
    15    result[i] = getMatch(first[i], second[i], TRAITS[i]);
    16   }
    17
    18   return result;
    19
    20  }
    21
    22  private static String getMatch(String s1, String s2, String[] traits)  {
    23
    24   /*
    25   * If the two strings are equal, then return that string.
    26   */
    27   if (s1.equals(s2)) return s1;
    28
    29   /*
    30   * Otherwise, return the string that is not s1 or s2
    31   */
    32   for (int i = 0; i < traits.length; i++)  {
    33    if (!traits[i].equals(s1) && !traits[i].equals(s2))
    34     return traits[i];
    35   }
    36
    37   return null;
    38
    39  }
    40 }
Notes:

This is one of those problems where reading the description makes you think it's going to be much more difficult than the problem actually is. All we need to do is for each of the four traits (shape, color, fill pattern, and count) give the value of the string if the first and second card have the same value. Or, if the first and second cards have different values, then we give the third (or odd man out) value.

The for loop in the findMatch() method just walks through each of the four traits, and calls getMatch() to insert the correct value into the result array.

getMatch() compares the two strings, and if they're equal returns that value. Otherwise, it looks through the values given in traits for a string that does not match s1 and does not match s2. Note that we should never reach the return null statement on line 37, but it needs to be there to satisfy the compiler.

Nothing difficult here. Getting through the description actually took longer than writing the code.

Tuesday, October 6, 2015

Stairs

Problem:

TopCoder Problem Statement - Stairs
Single Round Match 177 Round 1 - Division II, Level One>

Overview:

Count the number of combinations of risers and treads that can lead to a staircase of the given dimensions.

Java Source:
     1 public class Stairs {
     2
     3     public int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
     4
     5         int count = 0;
     6
     7         for (int riserHeight = 1; (riserHeight <= maxHeight); riserHeight++) {
     8             if ((totalHeight % riserHeight) != 0) continue;
     9
    10             int numTreads = (totalHeight / riserHeight) - 1;
    11
    12             if ((numTreads == 0) ||
    13                     ((totalWidth % numTreads) != 0) ||
    14                     ((totalWidth / numTreads) < minWidth)) continue;
    15             count++;
    16         }
    17
    18         return count;
    19     }
    20 }
Notes:

Note that the size of both the risers and treads must be integers, and that they are at most 1,000. This means that a brute force search is certainly possible. We'll loop through all possible heights and count the number of configurations that are possible.

For each riser height, we first check to see if it evenly divides the total height. If not, then we can continue on with the next height. If so, then we'll look at the treads.

The number of treads will be one less than the number of risers. We can compute the number of risers with (totalHeight / riserHeight). Then just subtract one from that result to get the number of treads.

Next, we look for ways to discount the current number of risers and treads. The problem statement says that their must be at least one tread (and riser), so we can throw out any cases where the number of treads is 0. Again, just like with the risers, the total width must be evenly divided by the number of treads, so we can skip any case where that isn't true. And finally, any case where the width of each tread (totalWidth / numTreads) is smaller than the minimum allowed can also be skipped.

Passing each of those tests, leaves us with a valid configuration, so increment the counter. After looping throug all possibilities, return the value in the counter.

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.

Thursday, July 30, 2015

WordForm

Problem:

TopCoder Problem Statement - WordForm
Single Round Match 173 Round 1 - Division I, Level One
Single Round Match 173 Round 1 - Division II, Level Two

Overview:

Detect vowels and consonants in a word.

Java Source:
     1 public class WordForm {
     2
     3  public String getSequence(String word) {
     4
     5         char[] cvArray = new char[word.length()];
     6
     7         boolean prevIsVowel = true;
     8
     9         for (int i = 0; i < word.length(); i++)  {
    10             cvArray[i] = (prevIsVowel = isVowel(word.charAt(i), prevIsVowel)) ? 'V' : 'C';
    11         }
    12
    13         // Remove duplicate characters
    14         return new String(cvArray).replaceAll("([CV])\\1+", "$1");
    15  }
    16
    17     private static boolean isVowel(Character c, boolean prevIsVowel)  {
    18
    19         c = Character.toUpperCase(c);
    20
    21         if ((c.equals('A')) || (c.equals('E')) ||
    22                 (c.equals('I')) || (c.equals('O')) ||
    23                 (c.equals('U'))) return true;
    24
    25         if (!c.equals('Y')) return false;
    26
    27         return !prevIsVowel;
    28     }
    29 }
Notes:

The problem can be solved by breaking it up into two pieces. First, obviously we're going to need a method to determine if a character is a consonant or vowel. This is handled by isVowel(). isVowel() first converts the character to upper-case, and then compares it to the standard vowels A, E, I, O, and U. If it matches one of these, or if it doesn't and also is not a 'Y' then we're done. 'Y's are the only tricky letter.

To determine if 'Y' is a vowel or not, isVowel() requires a boolean denoting whether the previous character was a vowel or not. We can set prevIsVowel's initial value to true since the behavior of a 'Y' at the beginning of a string is the same as a 'Y' following a vowel.

With a reliable method of determining consonants and vowels, we just need to construct the return String, and the only challenge there is eliminating duplicates. One way to do this would be to keep track of the last character, and only append the next character if it differed. An easier way is to just add all the characters, and then use a regular expression to remove the duplicates. This is done in the replaceAll() method of the return statement.

If you're not familiar with the assignment on line 10, all this does is assign the result of isVowel() to both prevIsVowel and cvArray[i] in one line. First, isVowel() is evaluated and the result is assigned to prevIsVowel. The result of this assignment, which is either true or false, is then assigned to cvArray[i]. With that, we've put the correct character (either a 'V' or a 'C') into the array, and set prevIsVowel to the correct value for the next call into isVowel().

Wednesday, July 29, 2015

ProgressBar

Problem:

TopCoder Problem Statement - ProgressBar
Single Round Match 173 Round 1 - Division II, Level One

Overview:

Fill in a progress bar to show the fraction of completed time vs. total time estimated to complete a task.

Java Source:
     1 public class ProgressBar {
     2
     3  public static final int NUM_MARKERS = 20;
     4  private static final char FILL_CHAR = '#';
     5  private static final char EMPTY_CHAR = '.';
     6
     7
     8  public String showProgress(int[] taskTimes, int tasksCompleted) {
     9
    10   int totalTime = 0;
    11   int completedTime = 0;
    12
    13   /*
    14   * Count the time for all completed tasks and the
    15   * overall total time.
    16   */
    17   for (int i = 0; i < taskTimes.length; i++)  {
    18    totalTime += taskTimes[i];
    19
    20    if (tasksCompleted > i)  {
    21     completedTime = totalTime;
    22    }
    23   }
    24
    25   int numberToFill = NUM_MARKERS * completedTime / totalTime;
    26
    27   /*
    28   * Create our return array.  Fill in the characters that should
    29   * be filled in, then mark the rest as empty.
    30   */
    31   char[] chars = new char[NUM_MARKERS];
    32
    33   for (int i = 0; i < numberToFill; i++)  {
    34    chars[i] = FILL_CHAR;
    35   }
    36
    37   for (int i = numberToFill; i < NUM_MARKERS; i++)  {
    38    chars[i] = EMPTY_CHAR;
    39   }
    40
    41   return new String(chars);
    42  }
    43 }
Notes:

The first step is to sum the time taken so far and the total time. This can be done in one pass of the given taskTimes array.

With these, we can determine the number of characters that must be filled in using the formula:

NUM_MARKERS * completedTime / totalTime

Note that this is using integer division, so the result will automatically be rounded down for us.

Then it's just a matter of filling in the first numberToFill characters, and setting the rest to empty.

Wednesday, July 22, 2015

Cubism

Problem:

TopCoder Problem Statement - Cubism
Single Round Match 172 Round 1 - Division II, Level Three

Overview:

Count the number of lines that can be formed in a cube where the line's length equals the length of a side of the cure, and all location along the line match a given color.

Java Source:
     1
     2
     3 public class Cubism {
     4
     5  public int lines(String[] lattice, String color) {
     6
     7   int size = lattice.length;
     8         char c = "black".equals(color) ? 'B' : 'W';
     9
    10         /*
    11         * The problem becomes much easier if we transform the
    12         * given String[] into a 3-Dimensional array
    13         * of chars.
    14         */
    15   char[][][] cube = new char[size][size][size];
    16
    17         for (int x = 0; x < size; x++)  {
    18             for (int y = 0; y < size; y++)  {
    19                 for (int z = 0; z < size; z++)  {
    20                     cube[x][y][z] = lattice[x].charAt((y * size) + z);
    21                 }
    22             }
    23         }
    24
    25         int numLines = 0;
    26
    27         /*
    28         * Count the number of lines that begin at each location.
    29         */
    30         for (int x = 0; x < size; x++)  {
    31             for (int y = 0; y < size; y++)  {
    32                 for (int z = 0; z < size; z++)  {
    33                     numLines += countLinesStartingAt(cube, x, y, z, c);
    34                 }
    35             }
    36         }
    37
    38         /*
    39         * Each line will be counted twice, once starting from
    40         * each end point, so divide the result in half.
    41         */
    42         return numLines / 2;
    43  }
    44
    45     /*
    46     * Count the number of lines starting from the given coordinate.  The line
    47     * must be of the given color c.
    48     */
    49     private static int countLinesStartingAt(char[][][] cube,
    50                                             int x, int y, int z,
    51                                             char c)  {
    52
    53         int numLines = 0;
    54
    55         /*
    56         * We'll generate the 27 directions that the row could stretch out in
    57         * by using deltaX, deltaY, and deltaZ.
    58         */
    59         for (int deltaX = -1; deltaX < 2; deltaX++)  {
    60             for (int deltaY = -1; deltaY < 2; deltaY++)  {
    61                 for (int deltaZ = -1; deltaZ < 2; deltaZ++)  {
    62                     if (isLine(cube, x, y, z, deltaX, deltaY, deltaZ, c))  {
    63                         numLines++;
    64                     }
    65                 }
    66             }
    67         }
    68         return numLines;
    69     }
    70
    71     /*
    72     * Returns true if a line originating at (x,y,z) of size cube.length and moving
    73     * in the direction given by deltaX, deltaY, and deltaZ can be formed.
    74     * All position along the line must match color c.
    75     */
    76     private static boolean isLine(char[][][] cube,
    77                                   int x, int y, int z,
    78                                   int deltaX, int deltaY, int deltaZ,
    79                                   char c)  {
    80
    81         // It's not a line if we never move from the origin.
    82         if ((deltaX == 0) && (deltaY == 0) && (deltaZ == 0)) return false;
    83
    84         for (int i = 0; i < cube.length; i++)  {
    85
    86             // Check that we stay within bounds.
    87             if ((x < 0) || (x >= cube.length)) return false;
    88             if ((y < 0) || (y >= cube.length)) return false;
    89             if ((z < 0) || (z >= cube.length)) return false;
    90
    91             // Check the color matches.
    92             if (cube[x][y][z] != c) return false;
    93
    94             // Move to the next location.
    95             x += deltaX;
    96             y += deltaY;
    97             z += deltaZ;
    98         }
    99
   100         return true;
   101     }
   102 }
Notes:

This problem becomes very easy once you break it down into smaller steps. The first task is to take the unwieldly String[] and convert it into an easy to use 3 dimensional array of chars. This is handled on lines 15-23. Nothing trick here, except for a little bit of math to get the right character out of the String.

With our 3-D array, we can now loop through each position and count the number of lines starting at that position. Note that we'll count each row twice. Once starting from each end and going to the other.

The countLinesStartingAt() method does just that. Given a 3-D coordinate, it returns the number of lines starting from that position. Rather than writing out the 27 directions that we could move out from for any given position, I have three nested loops and the variables deltaX, deltaY, and deltaZ. Each of these variables moves from -1 to 1.

With that, we call isLine() providing the staring point, direction, and color. isLine() just checks that we stay within the confines of the cube and stay on the correct color as we move along the line.

Nothing really difficult here. It could probably have been a Division 2 Level 2.

BadClock

Problem:

TopCoder Problem Statement - BadClock
Single Round Match 172 Round 1 - Division I, Level One
Single Round Match 172 Round 1 - Division II, Level Two

Overview:

Determine how many hours it will take a clock to show the correct time given how far off it is initially and how many seconds it gains/loses per hour.

Java Source:
     1
     2
     3 public class BadClock {
     4
     5     public double nextAgreement(
     6             String trueTime, String skewTime, int hourlyGain) {
     7
     8         String[] trueString = trueTime.split(":");
     9         String[] skewString = skewTime.split(":");
    10
    11         /*
    12         * Number of seconds that skewTime is behind trueTime.
    13         * If skewSeconds is negative, then skewTime is ahead
    14         * of trueTime.
    15         */
    16         int skewSeconds = 0;
    17
    18         skewSeconds =
    19                 (Integer.parseInt(trueString[0]) -
    20                         Integer.parseInt(skewString[0])) * 60 * 60;
    21
    22         skewSeconds +=
    23                 (Integer.parseInt(trueString[1]) -
    24                         Integer.parseInt(skewString[1])) * 60;
    25
    26         skewSeconds += Integer.parseInt(trueString[2]) -
    27                 Integer.parseInt(skewString[2]);
    28
    29         if (skewSeconds == 0) return 0.0;
    30
    31         if ((skewSeconds > 0) && (hourlyGain < 0)) {
    32             // Clock is behind, and losing.
    33             skewSeconds -= 12 * 60 * 60;  // Move skewTime ahead 12 hours
    34
    35         } else if ((skewSeconds < 0) && (hourlyGain > 0)) {
    36             // Clock is ahead, and gaining
    37             skewSeconds += 12 * 60 * 60;  // Move skewTime behind 12 hours
    38         }
    39
    40         return (double) skewSeconds / (double) hourlyGain;
    41
    42     }
    43 }
Notes:

The first step is to determine how many seconds the skewed clock is away from the true time. This is calculated on lines 18-27 and is stored in skewSeconds. Note that if skewSeconds is positive then the skewed clock is behind true time. If skewSeconds is negative, then the skewed clock is ahead of the true time.

If skewSeconds is 0, then we can simply return 0. Otherwise, we'll want to divide the number of seconds the two clocks are off by the hourlyGain. This is fine if the skewed clock is ahead and hourlyGain is negative; or if the skewed clock is behin and hourlyGain is positive. But we must account for two other cases as well.

If the skewed clock is ahead, and the hourlyGain is positive, then it's distance ahead will keep increasing. To fix this, we can just set the skewed clock back 12 hours. Similary, if the skewed clock is behind, and the hourlyGain is negative, we can adjust the skewed clock ahead 12 hours. Be careful with the signs here, it can get a little confusing.

Tuesday, July 21, 2015

SkipRope

Problem:

TopCoder Problem Statement - SkipRope
Single Round Match 172 Round 1 - Division II, Level One

Overview:

Find the two numbers in an array that are closest to the given number.

Java Source:
     1 import java.util.Arrays;
     2
     3 public class SkipRope {
     4
     5     public int[] partners(int[] candidates, int height) {
     6
     7         int[] heights = {Integer.MAX_VALUE, Integer.MAX_VALUE};
     8
     9         for (int c : candidates) {
    10             if (isCloser(c, heights[0], height)) {
    11
    12     /*
    13     * If closer that the closest, then bump the closest
    14     * into 2nd place, and set the candidate to be
    15     * the new closest.
    16     */
    17                 heights[1] = heights[0];
    18                 heights[0] = c;
    19
    20             } else if (isCloser(c, heights[1], height)) {
    21
    22                 // Set 2nd place to be the candidate.
    23                 heights[1] = c;
    24             }
    25         }
    26
    27         Arrays.sort(heights);
    28
    29         return heights;
    30     }
    31
    32     /*
    33     * Returns true if the candidate is closer in height than the current
    34     * person.  If the two are the same distance apart, then ties go
    35     * to the taller person.
    36     */
    37     private static boolean isCloser(int candidate, int current, int height) {
    38
    39         int diffCandidate = Math.abs(height - candidate);
    40         int diffCurrent = Math.abs(height - current);
    41
    42         if (diffCandidate < diffCurrent) return true;
    43
    44         if (diffCandidate > diffCurrent) return false;
    45
    46         // Ties go to the taller person.
    47         return candidate > current;
    48
    49     }
    50 }
Notes:

The solution starts by creating an array (heights) to store the two closest numbers. It sets their initial values to Integer.MAX_VALUE to ensure they're far enough away from our height that the first two numbers seen are guaranteed to be closers.

Then we make one pass through the list of candidate heights. If the height is closer than the value in position 0, we move the closest into the second closest position, and insert our candidate in position 0 as the next closest height.

If the height is not the closest, but it is closer than the second closest, then we simply replace the the height in position 1 with our current candidate's height.

The method isCloser determines if the value is candidate is closer to height than the value of current. Note that we must take the absolute value of the difference. In the event of a tie closer is determined by if candidate is greater than current.

Sunday, July 19, 2015

TextEditor

Problem:

TopCoder Problem Statement - TextEditor
Single Round Match 171 Round 1 - Division II, Level Three

Overview:

Format text into 2 columns.

Java Source:
     1 import java.util.ArrayList;
     2 import java.util.List;
     3 
     4 public class TextEditor {
     5 
     6     public String[] twoColumn(String[] text, int width) {
     7 
     8         List allWords = new ArrayList<>();
     9 
    10         /*
    11         * Put all words together into one long list.
    12         */
    13         for (String line : text) {
    14             String[] wordsOnLine = line.trim().split("\\s+");
    15             for (String word : wordsOnLine) {
    16                 allWords.add(word);
    17             }
    18         }
    19 
    20         /*
    21         * Break the words up into lines so that no
    22         * line is longer than the given width.
    23         */
    24         List oneColumn = new ArrayList<>();
    25 
    26         StringBuilder sb = new StringBuilder(width);
    27 
    28         for (String word : allWords) {
    29 
    30             /*
    31             * Nothing we can do if a word by itself cannot
    32             * fit onto a line with the given width.
    33             */
    34             if (word.length() > width) {
    35                 throw new IllegalArgumentException(
    36                         "Word is too long to fit into column: " + word);
    37             }
    38 
    39             /*
    40             * If it's the first word, then always add it to
    41             * the current line.
    42             */
    43             if (sb.length() == 0) {
    44                 sb.append(word);
    45 
    46             /*
    47             * If a space plus the word would fit on the current
    48             * line, then add it.
    49             */
    50             } else if (sb.length() + word.length() < width) {
    51                 sb.append(" ");
    52                 sb.append(word);
    53 
    54             /*
    55             * Otherwise, start a new line.
    56             */
    57             } else {
    58                 oneColumn.add(sb.toString());
    59                 sb = new StringBuilder(width);
    60                 sb.append(word);
    61             }
    62         }
    63 
    64         /*
    65         * If there's anything left over, add it to
    66         * the final line.
    67         */
    68         if (sb.length() != 0) {
    69             oneColumn.add(sb.toString());
    70         }
    71 
    72         int i = 0;
    73 
    74         String[] result = new String[oneColumn.size()];
    75 
    76         /*
    77         * Fill in the even numbered positions first, when
    78         * the end is reached, come back and fill in the odds.
    79         */
    80         for (String s : oneColumn) {
    81             result[i] = s;
    82             i += 2;
    83             if (i >= oneColumn.size()) i = 1;
    84         }
    85 
    86         return result;
    87     }
    88 }
Notes:

A pretty easy problem for a Division 2 - Level 3. There's just two tricky things to take care of. First, we need to divide the input into columns that are no wider than the given width. To do this, I create a single list that contained all of the words. Note that the lines may have trailing and/or leading whitespace which we want to remove. Combining trim() with .split("\\s+") gives us the individual words nicely.

Next, I divide the words by line into one column, such that the length of each line is less than or equal to width. This is done easily enough by the loop on lines 28 - 62. We just test the length of the current line plus a space plus the length of the next word. If that is greater than width, cut the line off and put the word at the beginning of the next line.

Finally, we need to split the one column up into two columns with the lines interleaved. The easiest way to do this is to assign all the even numbered positions first. Then upon reaching the end of the list, come back to position 1, and start filling in the odd positions.

Wednesday, July 15, 2015

CrossCountry

Problem:

TopCoder Problem Statement - CrossCountry
Single Round Match 171 Round 1 - Division I, Level One
Single Round Match 171 Round 1 - Division II, Level Two

Overview:

Determine the order that teams place in a cross country meet given the finishing positions of each runner.

Java Source:
     1 import java.util.ArrayList;
     2 import java.util.Collections;
     3 import java.util.List;
     4
     5 public class CrossCountry {
     6
     7     private static final int MIN_FINISHERS = 5;
     8     private static final int TIE_BREAKER_PLACE = MIN_FINISHERS + 1;
     9
    10     /*
    11     * The Team class represents a team and contains methods for calculating
    12     * it's score and comparing it to other teams.
    13     */
    14     class Team implements Comparable {
    15
    16         char name;
    17         int score;
    18         int numFinishers;
    19         int tieBreaker;
    20
    21         public Team(char name) {
    22             this.name = name;
    23         }
    24
    25         public void addFinisher(int score) {
    26
    27             // Only the top 5 runner contribute to the score.
    28             if (numFinishers < MIN_FINISHERS) {
    29                 this.score += score;
    30
    31                 // Store the 6th finisher's position in tieBreaker.
    32             } else if (numFinishers == MIN_FINISHERS) {
    33                 tieBreaker = score;
    34             }
    35
    36             numFinishers++;
    37         }
    38
    39         // Assumes that both Teams have at least five finishers.
    40         @Override
    41         public int compareTo(Team o) {
    42
    43             if (this.score != o.score) return new Integer(score).compareTo(o.score);
    44
    45             // This team does not have a 6th place finisher, but the other does.
    46             if ((numFinishers < TIE_BREAKER_PLACE) && (o.numFinishers >= TIE_BREAKER_PLACE)) return 1;
    47
    48             // This team has a 6th place finisher, but the other team does not.
    49             if ((numFinishers >= TIE_BREAKER_PLACE) && (o.numFinishers < TIE_BREAKER_PLACE)) return -1;
    50
    51             // Both teams have a 6th place finisher.
    52             if ((numFinishers >= TIE_BREAKER_PLACE) && (o.numFinishers >= TIE_BREAKER_PLACE))
    53                 return new Integer(tieBreaker).compareTo(o.tieBreaker);
    54
    55             // Neither team has a 6th place finisher.
    56             return new Character(name).compareTo(o.name);
    57
    58         }
    59     }
    60
    61
    62     public String scoreMeet(int numTeams, String finishOrder) {
    63
    64         Team[] teams = new Team[numTeams];
    65
    66         // Initialize an ArrayList with a Team object for each team.
    67         char name = 'A';
    68         for (int i = 0; i < numTeams; i++) {
    69             teams[i] = (new Team(name++));
    70         }
    71
    72         int score = 1;
    73
    74         /*
    75         * Work left to right through the finishOrder string.  For each
    76         * character, determine corresponding team by subtracting the value
    77         * of 'A' from the character to get it's index in the teams list.
    78         */
    79         for (int i = 0; i < finishOrder.length(); i++) {
    80             char c = finishOrder.charAt(i);
    81             teams[c - 'A'].addFinisher(score++);
    82         }
    83
    84         // Holds only those teams with 5 or more finishers.
    85         List qualifyingTeams = new ArrayList<>();
    86
    87         for (int i = 0; i < teams.length; i++)  {
    88             if (teams[i].numFinishers >= MIN_FINISHERS) {
    89                 qualifyingTeams.add(teams[i]);
    90             }
    91         }
    92
    93         // Use the Team.compareTo() method to sort the teams out.
    94         Collections.sort(qualifyingTeams);
    95
    96         /*
    97         * Build our return string by going through the sorted list
    98         * and adding the team names.
    99         */
    100         StringBuilder sb = new StringBuilder(qualifyingTeams.size());
    101
    102         for (Team t : qualifyingTeams) {
    103             sb.append(t.name);
    104         }
    105
    106         return sb.toString();
    107     }
    108 }
Notes:

I've created a class Team the implements Comparable so that we can use Java's built-in sort capabilities. All the logic necessary for sorting the teams is contained in the Team.compareTo() method.

With that, it's just a matter of creating the team objects, and adding their finishing places. Lines 67-70 create an array of teams and assign each one it's name. Then the loop on lines 79-82 works through each of the letters in finishOrder and calls addFinisher() on the corresponding team. We can get the correct team by subtracting 'A' from the current letter. For example, if the letter is 'C', the 'C' - 'A' = 2, which is the position in the teams array of team C.

The addFinisher() method handles the logic of determining if this runner's score counts toward the team's score (it's a top 5 runner), or if we should store this score in tieBreaker (if it's the 6th runner for that team).

Once all the team data is populated, we add only those teams with 5 or more runners to the qualifyingTeams list, sort the list, and then add each team's name in order to the string that we return.

RPG

Problem:

TopCoder Problem Statement - RPG
Single Round Match 171 Round 1 - Division II, Level One

Overview:

Determine the minimum, maximum, and average for a set of dice rolls.

Java Source:
     1 public class RPG {
     2
     3  public int[] dieRolls(String[] dice) {
     4
     5         int min = 0;
     6         int max = 0;
     7
     8         for (int d = 0; d < dice.length; d++)  {
     9
    10             /*
    11             * Splits the string into the parts before and after the 'd'
    12             */
    13             String[] s = dice[d].split("d");
    14
    15             int rolls = Integer.parseInt(s[0]);
    16             int die = Integer.parseInt(s[1]);
    17
    18             min += rolls;
    19             max += (rolls * die);
    20         }
    21
    22         int average = ((max - min) / 2) + min;
    23
    24         return new int[] {min, max, average};
    25     }
    26
    27
    28 }
Notes:

The first task is to parse each string in the array to get the size of the die and the number of rolls. This is easy enough using String.split(). By splitting on the "d" character, we'll get the number of rolls in position 0, and the size of the die in position 1 or the resulting array.

To get the minimum value, we just assume that the die always comes up one. So, minimum is just equal to the number of die rolls.

To get the maximum value, we assume that die always comes up with it's largest possible value. Here, we just multiple the number of rolls by the size of the die.

Then, we compute the average using the formula on line 22.

We these three values calculate, we just create an int[] to hold them, and return it.

Friday, May 22, 2015

MutaliskEasy

Problem:

TopCoder Problem Statement - MutaliskEasy
Single Round Match 658 Round 1 - Division II, Level Two

Overview:

Given attacks that do 9,3, and 1 point of damage, determine the fewest number of rounds needed to take out an opponent.

Java Source:
     1 public class MutaliskEasy {
     2
     3     private static final int[] ATTACKS = {9, 3, 1};
     4     private static final int MAX_HP = 60;
     5
     6     int[][][] results = new int[MAX_HP + 1][MAX_HP + 1][MAX_HP + 1];
     7
     8  public int minimalAttacks(int[] x) {
     9
    10         // Nothing to do.
    11         if (x.length == 0) return 0;
    12
    13         // Just divide by the maximum attack value.
    14         if (x.length == 1)  {
    15             if (x[0] % ATTACKS[0] == 0)  {
    16                 return x[0] / ATTACKS[0];
    17             } else  {
    18                 return x[0] / ATTACKS[0] + 1;
    19             }
    20         }
    21
    22         /*
    23         * The problem does not fall into one of the easy cases,
    24         * so we'll have to do some work...
    25         */
    26
    27         // Initialize results.
    28         for (int i = 0; i <= MAX_HP; i++)  {
    29             for (int j = 0; j <= MAX_HP; j++)  {
    30                 for (int k = 0; k <= MAX_HP; k++)  {
    31                     results[i][j][k] = -1;
    32                 }
    33             }
    34         }
    35         results[0][0][0] = 0;
    36
    37         /*
    38         * We'll treat a length of 2 the same as if it had 3.  Just
    39         * give the 3rd element a value of 0.
    40         */
    41         if (x.length == 2) return minimalAttacks(x[0], x[1], 0);
    42         if (x.length == 3) return minimalAttacks(x[0], x[1], x[2]);
    43
    44         return -1;  // Length of x must be >= 0 and <= 3
    45
    46     }
    47
    48     private int minimalAttacks(int x, int y, int z)  {
    49
    50         // Don't allow values to go below 0.
    51         if (x < 0) x = 0;
    52         if (y < 0) y = 0;
    53         if (z < 0) z = 0;
    54
    55
    56         // If we've already calculated this result, just return it.
    57         if (results[x][y][z] >= 0) return results[x][y][z];
    58
    59         int minAttacks = Integer.MAX_VALUE;
    60
    61         // Try all possible combinations.
    62         for (int i = 0; i < ATTACKS.length; i++)  {
    63
    64             for (int j = 0; j < ATTACKS.length; j++)  {
    65                 if (j == i) continue;
    66
    67                 for (int k = 0; k < ATTACKS.length; k++)  {
    68                     if ((k == i) || (k == j))  continue;
    69
    70                     minAttacks = Math.min(minAttacks,
    71                             minimalAttacks(
    72                                     x - ATTACKS[i],
    73                                     y - ATTACKS[j],
    74                                     z - ATTACKS[k]));
    75                 }
    76             }
    77         }
    78
    79         results[x][y][z] = minAttacks + 1;
    80         return minAttacks + 1;
    81
    82     }
    83
    84 }
Notes:

My first approach was a simple greedy algorithm. I sorted the opponents according to the amount of hit points they had remaining, and then assigned the biggest attack to the opponent with most hit points remaining, the next biggest attack to the next strongest opponent, and the last attack to the third strongest opponent. Then I re-sorted the opponents, and repeated. As the first test shows, this approach does not work.

Instead, we'll need to try every possible combination.

The minimalAttacks(int,int,int) method begins by ensuring we don't allow the hit point values to go below 0. Then it checks to see if we've already solved for this combination of x, y, and z. If so, then we can just return that value This technique is called memoization, and allows up to skip the calculations that follow if they've already been carried out.

If we don't already have a result, then the loops on lines 62-77 will recursively call minimalAttacks with every possible combination of assigning attacks to the various opponents. We keep track of the best result in the minAttacks variable, and then store this in the results matrix before returning it.

The minimalAttacks(int[]) method checks for a few easy cases (length of x is 0 or 1), and failing that initializes the results matrix, and then uses minimalAttacks(int, int, int) to calculate the result.

InfiniteString

Problem:

TopCoder Problem Statement - InfiniteString
Single Round Match 658 Round 1 - Division II, Level One

Overview:

Determine if two strings, when repeated infinitely, are equal.

Java Source:
     1 public class InfiniteString {
     2
     3  public String equal(String s, String t) {
     4
     5   int ptrS = 0;
     6   int ptrT = 0;
     7
     8   /*
     9   * Continue looping one character at a time until
    10   * we reach both the end of String s and the end
    11   * of String t at the same time.
    12   */
    13   while ((ptrS < s.length()) || (ptrT < t.length()))  {
    14
    15    /*
    16    * If at the end of a String, start over at
    17    * the beginning.
    18    */
    19    ptrS %= s.length();
    20    ptrT %= t.length();
    21
    22    // Return "Not Equal" if characters do not match
    23    if (s.charAt(ptrS) != t.charAt(ptrT)) return "Not equal";
    24
    25    ptrS++;
    26    ptrT++;
    27   }
    28
    29   return "Equal";
    30  }
    31 }
Notes:

Imagine creating two Strings s1 and t1 such that s1 = s + s + s ... and t1 = t + t + t + t + ... and the length of both s1 and t1 is equal to the least common multiple of the lengths of s and t.

For example if s = "ababab" and t = "abab", then the length of s is 6, the length of t is 4, and their least common multiple is 12. Therefore, s1 = s + s = "abababababab" and t1 = t + t + t = "abababababab". Since s1 == t1 we should return "Equal"

The important point is that if we step through the Strings s and t one character at a time, and loop back to the beginning of the String when we reach the end; then we can stop when we reach the end of both s and t at the same time. That's the condition that is checked for in the while loop.

The rest is just a matter of checking that the characters match at each position, and incrementing and resetting the pointer to the current character.

Saturday, May 16, 2015

Poetry

Problem:

TopCoder Problem Statement - Poetry
Single Round Match 170 Round 1 - Division II, Level Three

Overview:

Determine the rhyme scheme of a poem.

Java Source:
     1 import java.util.HashMap;
     2 import java.util.Map;
     3
     4 public class Poetry {
     5
     6  public String rhymeScheme(String[] poem) {
     7
     8         // The label we'll assign to the next rhyme.
     9         char nextRhymeLabel = 'a';
    10
    11         /*
    12         * We'll fill in this array as we go, and ultimately
    13         * return it.
    14         */
    15         char[] result = new char[poem.length];
    16
    17         // Maps and ending sound to a label.
    18         Map endings = new HashMap<>();
    19
    20
    21         for (int line = 0; line < poem.length; line++)  {
    22
    23             // Split the line on whitespace characters
    24             String[] words = poem[line].trim().split("\\s+");
    25
    26             /*
    27             * If the line was empty (or just spaces), words will
    28             * have a length of 1, and the only entry will have
    29             * a length of 0.
    30             */
    31             if ((words.length == 1) && (words[0].length() == 0))  {
    32                 result[line] = ' ';
    33
    34             } else  {
    35
    36                 String lastWord = words[words.length - 1];
    37                 String ending = getWordEnding(lastWord.toLowerCase());
    38
    39                 if (endings.containsKey(ending))  {
    40
    41                     /*
    42                     * We've already seen this ending, so just
    43                     * look up the label.
    44                     */
    45                     result[line] = endings.get(ending);
    46
    47                 } else  {
    48
    49                     /*
    50                     * This is a new ending, so store
    51                     * it, and increment to the next label.
    52                     */
    53                     endings.put(ending, nextRhymeLabel);
    54                     result[line] = nextRhymeLabel;
    55
    56                     if (nextRhymeLabel == 'z') {
    57                         nextRhymeLabel = 'A';
    58                     } else  {
    59                         nextRhymeLabel += 1;
    60                     }
    61                 }
    62             }
    63         }
    64
    65         return new String(result);
    66
    67  }
    68
    69     private String getWordEnding(String word)  {
    70
    71         int i = word.length() - 1;
    72
    73         // Work backward until we reach the first vowel.
    74         while ((i >= 0) && (!isVowel(word.charAt(i), i, word.length())))  {
    75             i--;
    76         }
    77
    78         /*
    79         * Continue so long as it remains a vowel.  Don't
    80         * go past the beginning of the word.
    81         */
    82         while ((i >= 0) && (isVowel(word.charAt(i), i, word.length())))  {
    83             i--;
    84         }
    85
    86         // Return the ending of word starting at position i+1
    87         return word.substring(i+1);
    88
    89
    90     }
    91
    92     /*
    93     * Returns true if c is one of: a, e, i, o, or u.
    94     * Also returns true if c is y and not the first or last
    95     * letter of the word.  Otherwise, returns false.
    96     */
    97     private boolean isVowel(char c, int position, int wordLength)  {
    98
    99         if ((c == 'a') ||
   100                 (c == 'e') ||
   101                 (c == 'i') ||
   102                 (c == 'o') ||
   103                 (c == 'u')) return true;
   104
   105         if ((c == 'y') &&
   106                 ((position != 0) && (position != (wordLength - 1)))) return true;
   107
   108         return false;
   109
   110     }
   111 }
Notes:

Easier than the 500 point solution RecurrenceRelation, Poetry is pretty straight forward. There's just three things to take care of:

First, we need to split each line of the input up into words, and then examine the last word of the line. Splitting it up is easy with the String.split() method, using the "\\s+" regular expression. Then we need to check to make sure it wasn't an empty line. The word we're interested in is the last element of the result of the split.

Next we need to determine the ending of the word. For this, we start at the end of the word and work backward until we reach the first vowel. Then we continue backward so long as we continue getting vowels, and we don't run past the beginning of the String.

Finally, we need a method to determine if a character is a vowel. This is trivial for characters other than 'y'. 'y' is a vowel unless it is the first or last character of the word.

With that in place, the rest is just housekeeping. We create a char[] named result to hold the label for each line. nextRhymeLabel holds the character we'll use for the next previously unseen word ending. When a new ending is encountered, we assign it the value in nextRhymeLabel, and then increment nextRhymeLabel, or set it to 'A' if it has reached 'z'. We use a HashMap to map endings that we've seen to the labels that were assigned to them.

There's really nothing difficult about this problem. I'm really surprised that it was not just Division 2 - 500 points.

RecurrenceRelation

Problem:

TopCoder Problem Statement - RecurrenceRelation
Single Round Match 170 Round 1 - Division I, Level One
Single Round Match 170 Round 1 - Division II, Level Two

Overview:

Solve for the value of X[n] where X[n] is based on X[n-1], X[n-2], ...

Java Source:
     1 public class RecurrenceRelation {
     2
     3  public int moduloTen(int[] coefficients, int[] initial, int N) {
     4
     5         int K = coefficients.length;
     6
     7         /*
     8         * Stores the solution to the previous K problems.
     9         */
    10   int[] X = new int[K];
    11
    12         /*
    13         * Initialize X to contain the values given
    14         * in initial.  We need to mod these first.
    15         */
    16         for (int i = 0; i < X.length; i++)  {
    17             X[i] = myMod(initial[i], 10);
    18         }
    19
    20         // If we already have the answer, just return it.
    21         if (N < K)  return X[N];
    22
    23         int n = K;
    24
    25         while (n <= N)  {
    26
    27             /*
    28             * Add up the previous K solutions.
    29             */
    30             int sum = 0;
    31
    32             for (int k = 0; k < K; k++)  {
    33                 sum += coefficients[k] * X[k];
    34             }
    35
    36             sum = myMod(sum, 10);
    37
    38             /*
    39             * We have our answer, so shuffle everything down to
    40             * make room for it - dropping the olds solution off
    41             * since we won't need it any more.
    42             */
    43
    44             for (int i = 0; i < (K - 1); i++)  {
    45                 X[i] = X[i + 1];
    46             }
    47
    48             // Insert the current solution into the end of the array.
    49             X[K - 1] = sum;
    50
    51             // Start working on the next solution.
    52             n++;
    53         }
    54
    55         // Return the most recently solved.
    56         return X[K - 1];
    57    }
    58
    59     /*
    60     * This handles mod'ing negative numbers, and is taken
    61     * straight out of the problem definition.
    62     */
    63     private static int myMod(int i, int m)  {
    64
    65         if (i >= 0) return i % m;
    66
    67         return ((m - ((-1 * i) % m)) % m);
    68     }
    69 }

Notes:

The wording of this problem makes it sound much more difficult than it actually is. You may need to read the description several times in order to understand what it's getting at. Basically, you're asked to solve for the value of X[n], where X[n] is based on the values of X[n-1], X[n-2], etc. The number of previous elements that combine to create the value of X[n] is K, where K is the length of both the coefficients and initial arrays.

Start by creating an array of ints, X[], to hold these values. Then we initialize X[] using the values from initial[]. Note that we need to perform the mod operation as described int the problem statement before inserting any value into X[]. Also note that if the number we're being asked to solve for (N) is less than, or equal to, the length of the initial[] array (N <= K), then we already have our answer. We can just return the the value in X[N].

Otherwise, we need to solve for each value of X[n] up to n = N. To get the next value we multiply each value in X[] by it's corresponding value in coefficients[] and note their sum. Then we shift all elements in X[] down by 1 (dropping off the value in X[0]) and insert our new value into the right-most position - after running it through the mod operation.

Once n == N, we have solved for the number that was asked for. The value we need is the most recent solution found which is stored in the greatest element of X.

The method myMod() simply implements the mod function as described in the problem statement. It is the normal % function, modified to handle negative numbers.

Again, the toughest part of the problem is just reading through the problem statement making sense of it. I actually thought this was harder than the 1000 point problem Poetry.

LevelUp

Problem:

TopCoder Problem Statement - LevelUp
Single Round Match 170 Round 1 - Division II, Level One

Overview:

Determine the number of experience point a character needs in order to reach the next level.

Java Source:
     1 public class LevelUp {
     2
     3  public int toNextLevel(int[] expNeeded, int received) {
     4
     5   int i = 0;
     6
     7         /*
     8         * Find the first expNeeded element that is greater
     9         * than received.
    10         */
    11         while (expNeeded[i] <= received) i++;
    12
    13         /*
    14         * Return the difference between the next level, and
    15         * the amount received.
    16         */
    17         return (expNeeded[i] - received);
    18
    19  }
    20 }
Notes:

Certainly one of the easiest problems to solve. Just loop through the values in expNeeded until you find one that is greater than received. Then just return that next value minus the amount of received.

Really the only thing to be careful of is the case where the amount received exactly equals the amount needed for a level. In this case, return the amount needed to reach the next level, and not 0.

Tuesday, May 12, 2015

FairWorkload

Problem:

TopCoder Problem Statement - FairWorkload
Single Round Match 169 Round 1 - Division I, Level Two
Single Round Match 169 Round 1 - Division II, Level Three

Overview:

Determine the minimum time needed to search through a set of folders given a number of workers. The workers must search a contiguous set of folders, and each folder may take a varying amount of time to process.

Java Source:
     1 public class FairWorkload {
     2
     3  public int getMostWork(int[] folders, int workers) {
     4
     5         /*
     6         * Stores the best time that we can complete a given
     7         * number of folders with a given number workers.
     8         */
     9   int[][] times = new int[workers][folders.length];
    10
    11         /*
    12         * With just 1 worker, the completion time
    13         * of folder f will be the sum of the times
    14         * it takes to process each folder up to and
    15         * including f.
    16         */
    17         for (int f = 0; f < folders.length; f++)  {
    18             times[0][f] = sumSections(0, f+1, folders);
    19         }
    20
    21         for (int w = 1; w < workers; w++)  {
    22             for (int f = 0; f < folders.length; f++)  {
    23
    24                 // Cannot have less folders than workers
    25                 if (f < w)  {
    26                     times[w][f] = -1;
    27
    28                 } else  {
    29
    30                     int minCompletionTime = Integer.MAX_VALUE;
    31
    32                     /*
    33                     * Try all combinations of splitting the
    34                     * folders between previous workers and
    35                     * the current worker.  d - marks
    36                     * the division point, where the current
    37                     * worker begins.
    38                     */
    39                     for (int d = w; d <= f; d++)  {
    40
    41                         int completionTime = Math.max(
    42                                 times[w-1][d-1],
    43                                 sumSections(d, f+1, folders));
    44
    45                         minCompletionTime = Math.min(
    46                                 minCompletionTime,
    47                                 completionTime);
    48                     }
    49
    50                     times[w][f] = minCompletionTime;
    51                 }
    52             }
    53         }
    54
    55         return times[workers - 1][folders.length - 1];
    56  }
    57
    58     /*
    59     * Return the sum of the elements in the nums array
    60     * starting at s and stopping just before e.
    61     */
    62     private int sumSections(int s, int e, int[] nums)  {
    63         int sum = 0;
    64
    65         for (int x = s; x < e; x++)  {
    66             sum += nums[x];
    67         }
    68
    69         return sum;
    70     }
    71
    72 }
Notes:

FairWorkload is a problem that begs for a dynamic programming solution. To solve this, we'll build up a table that holds the best finishing time we can achieve given a number of workers and a number of folders. We'll start with the trivial case of just one worker. Using that information, we'll add additional workers and folders until we've completed the table. The result will be the table shown below. With that, we can just return the value of the cell in the bottom right corner.

Don't be confused by the number of workers; I've labeled the table using its indexes, so "Workers 0" is the case with one worker. Same goes for folders across the top.

The table is initialized by filling in the top row. With just one worker, the number of sections searched is just the sum of the sections in all previous folders, plus the number of sections in the current folder. This could have been done more efficiently by keeping a running total of the number of sections, but since I needed a sumSections() method anyway, I chose to rely on that here.

Note that we cannot satisfy the constraints of the problem if there are fewer folders than their are workers. These cases are noted with a -1, although that never really comes into play.

Things begin to get interesting with the second worker. With 2 workers and 2 folders, we know that 1 worker must look through 10 sections to complete 1 folder, and that worker 2 must look through 20 sections to complete the next folder. Therefore the minimum number of sections is 20.

With 2 workers and three folders we have a choice in how to complete the task. We can either assign the first 2 folders to worker 1, and the third to worker 2 (scenario 1)- or we can assign just the first folder to worker 1, and the remaining two to worker 2 (scenario 2). We need to check both cases and see with gives the better result. Scenario 1 gives 10 + 20 = 30 sections to worker 1 and 30 sections to worker 2. Scenario 2 gives 10 sections to worker 1 and 20 + 30 = 50 sections to worker 2. The max of 30 in scenario 1 is better than the max of 50 in scenario 2, so 30 is our value here.

The loop on line 39 works through each scenario. In general, we want to minimize the maximum value of sections as we move the dividing line across the range of folders. The dividing line separates the work done by previous workers on one side (which can be pulled right out of the table), and the work done by the latest worker, which is the sum of the number of sections remaining.

Folder / Number of Sections
0/10 1/20 2/30 3/40 4/50 5/60 6/70 7/80 8/90
Workers
0
10 30 60 100 150 210 280 360 450
1 -1 20 30 60 90 110 150 210 240
2 -1 -1 30 40 60 90 110 150 170
3 -1 -1 -1 40 50 60 90 110 150
4 -1 -1 -1 -1 50 60 70 90 110

This is a great problem to hone you dynamic programming skills. Please take the time to make sure that you understand what's going on. It's a great tool to have for many TopCoder problems.

To help make it as clear as I can, let me walk through the final cell. Imagine that the bottom right cell was not yet filled in. From the previous row, we know the best solutions for each number of folders with one less worker. Since each worker must have at least one folder, we can divide the 9 folders up as follows:

Folders 0 - 3 processed by workers 0 - 3 / Folders 4 - 8 processed by Worker 4. From the table, we know the previous workers would have a max of 40 sections. But this leaves 50 + 60 + 70 + 80 + 90 = 350 sections for the last worker.

We then try...

Folders 0 - 4 processed by workers 0 - 3 / Folders 5 - 8 processed by Worker 4. Again from the table, the previous workers can do folders 0 - 4 with a max of 50. Worker 4 has 60 + 70 + 80 + 90 = 300 sections. Better than before, but still not the best we can do.

Folders 0 - 5 processed by workers 0 - 3 / Folders 6 - 8 processed by Worker 4. The previous workers have a max of 60, and Worker 4 has 70 + 80 + 90 = 240. Better still.

Folders 0 - 6 processed by workers 0 - 3 / Folders 7 - 8 processed by Worker 4. The previous workers now have a max of 90, and Worker 5 has 80 + 90 = 170.

It turns out the best solution is to have Folders 0 - 7 processed by workers 0 - 3 / and just Folder 8 processed by worker 4. The previous workers have a max of 110 sections, and Worker 4 has just 90 sections. The max of 110 is the best we can do, so that's what goes into the bottom right cell.