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.