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.

Twain

Problem:

TopCoder Problem Statement - Twain
Single Round Match 169 Round 1 - Division II, Level Two

Overview:

Perform a series of manipulations to a String and return the result.

Java Source:
     1 public class Twain {
     2 
     3     public String getNewSpelling(int year, String phrase) {
     4 
     5         if (year >= 1)  {
     6             // If a word starts with x, replace it with a z
     7             phrase = phrase.replaceAll("\\bx","z");
     8 
     9             phrase = phrase.replaceAll("x","ks");
    10         }
    11 
    12         if (year >= 2)  {
    13             phrase = phrase.replaceAll("y", "i");
    14         }
    15 
    16         if (year >= 3)  {
    17             /*
    18             * If a 'c' is followed immediately by an 'e' or
    19             * an 'i', then replace the 'c' with an 's'.
    20             */
    21             phrase = phrase.replaceAll("c([ei])", "s$1");
    22         }
    23 
    24         if (year >= 4)  {
    25 
    26             /*
    27             * Remove repeating 'c's that end with a 'k'
    28             * with just a 'k'.
    29             */
    30             phrase = phrase.replaceAll("c+k", "k");
    31         }
    32 
    33         if (year >= 5)  {
    34 
    35             /*
    36             * Replace 'sch' at the beginning of a word with
    37             * 'sk'
    38             */
    39             phrase = phrase.replaceAll("\\bsch", "sk");
    40 
    41             phrase = phrase.replaceAll("chr", "kr");
    42 
    43             /*
    44             * Replace all 'c' s that are not followed immediately
    45             * by a 'h' with a 'k'
    46             */
    47             phrase = phrase.replaceAll("c(?!h)", "k");
    48 
    49         }
    50 
    51         if (year >= 6)  {
    52 
    53             /*
    54             * Replace all words that start with 'kn'
    55             * with just 'n'
    56             */
    57             phrase = phrase.replaceAll("\\bkn", "n");
    58         }
    59 
    60         if (year >= 7)  {
    61 
    62             /*
    63             * Replace all repeating consonants, with just the
    64             * single character.
    65             */
    66             phrase = phrase.replaceAll("([b-df-hj-np-tv-z])\\1+", "$1");
    67         }
    68 
    69         return phrase;
    70  }
    71 }
Notes:

It looks like a lot of coders had a tough time with this problem. The solution given here seems like a lot of work. Fortunately, if you're up on your regular expressions, you can knock this out easily. If you're rusty with regular expressions, this is a great opportunity to exercise these important skills.

The first rule under year one uses the \\b character which matches with the start of a word boundary. \\bx matches any x at the start of a word. The second rule trivially replaces all remaining occurrences of "x" with "ks".

Year two is also trivial. we simply replace all occurrences of letter "y" with an "i". Nothing difficult there.

The rule for year three is a little more difficult. We need to replace any "c" followed immediately by an "e" or "i" with an "s". The rule "c([ei])" matches on the "c" followed by either an "e" or an "i". By putting the parenthesis around "[ei]" the value it matches is stored in a variable. We access the variable with $1. The result "s$1" replaces the "c" with an "s" and then tacks on whatever the "[ei]" matched.

The rule for year four simply replaces 1 or more occurrences of the letter "c" ending with a "k" with just a "k".

We've already seen the first two rules for year 5. The final rule is a bit tricky. It matches a "c" that is not immediately followed by an "h" with a "k".

The rule for year six is basically the same as that the first rule of year 1.

The rule for year seven is probably the most difficult. All consonants are defined by the ranges contained within the square brackets. Note that the vowels are missing here. The group is also enclosed within parenthesis, so we can refer to what it matches later using the variable $1. The \\1+ means that we want to match any occurrence of 1 or more consonants. We then replace this with just the single consonant.

I hope this gives some idea of how simple the problem can be solved using regular expressions. My goal is not to give an precise definition for any of the constructs used above, but rather just to show you how they could be used in this example.

Swimmers

Problem:

TopCoder Problem Statement - Swimmers
Single Round Match 169 Round 1 - Division II, Level One

Overview:

Calculate the time it takes a swimmer to complete a round trip given their speed, the distance, and the current.

Java Source:
     1 public class Swimmers {
     2  
     3  public int[] getSwimTimes(int[] distances, int[] speeds, int current) {
     4 
     5         // Holds the values we're calculating and returning
     6         int[] times = new int[distances.length];
     7 
     8         // Iterate through each swimmer and calculate their time.
     9         for (int i = 0; i < distances.length; i++)  {
    10             times[i] = getTime(distances[i], speeds[i], current);
    11         }
    12 
    13         return times;
    14  }
    15 
    16     /*
    17      * Returns the time it takes the swimmer to complete the round trip
    18      * given the one-way distance, their speed, and the current.
    19      * If distance == 0, the trip takes 0 time.
    20      * If the speed is not > current, the upstream portion will be
    21      * impossible and -1 is returned.
    22      */
    23     private int getTime(int distance, int speed, int current)  {
    24 
    25         if (distance == 0) return 0;
    26 
    27         if (speed <= current) return -1;
    28 
    29         /*
    30          * Need to use floats here for the intermediate calculations
    31          * so that we don't introduce rounding errors.
    32          */
    33          
    34          // The downstream time.
    35         float time = (float) distance / (float)(speed + current);
    36 
    37         // The upstream time.
    38         time += (float) distance / (float)(speed - current);
    39 
    40         return (int) time;
    41 
    42     }
    43 }

Notes:

Just two things to be careful of here. First, be sure to check for a distance of zero, and a current equal to or greater than the swimmer's speed. Second be careful not to use ints when performing the division for the downstream and upstream times. This can lead to rounding errors. You want to keep everything as a float until the very end where you'll truncate it and return the int.

Monday, May 11, 2015

WindowWasher

Problem:

TopCoder Problem Statement - WindowWasher
Single Round Match 168 Round 1 - Division II, Level Three

Overview:

Determine the shortest amount of time needed for a team of window washers to wash all the windows of a building.

Java Source:
     1 public class WindowWasher {
     2  
     3  public int fastest(int width, int height, int[] washTimes) {
     4 
     5 
     6         /*
     7         * Holds which washer a column is assigned to.  The column
     8         * will be assigned to the washer that can complete it first
     9         * taking into consideration any previous columns that
    10         * the washer may have been assigned to.
    11         */
    12   int[] assignedColumns = new int[width];
    13 
    14         // Begin with all columns unassigned.
    15         for (int i = 0; i < assignedColumns.length; i++)  {
    16             assignedColumns[i] = -1;
    17         }
    18 
    19 
    20         for (int w = 0; w < width; w++)  {
    21 
    22             /*
    23             * Determine the time at which each washer could complete
    24             * the current column.
    25             */
    26             int[] completionTimes = calcCompletionTimes(assignedColumns, w, washTimes);
    27 
    28             /*
    29             * Assign the current column to whomever could complete
    30             * it the earliest.
    31             */
    32             int minCompletionTime = Integer.MAX_VALUE;
    33             int minCompletionTimeWasher = -1;
    34 
    35             for (int i = 0; i < completionTimes.length; i++)  {
    36                 if (completionTimes[i] < minCompletionTime)  {
    37                     minCompletionTime = completionTimes[i];
    38                     minCompletionTimeWasher = i;
    39                 }
    40             }
    41 
    42             assignedColumns[w] = minCompletionTimeWasher;
    43 
    44         }
    45 
    46         /*
    47         * Holds the time at which each washer will be done with their
    48         * last assigned column.
    49         */
    50         int[] completionTimes = new int[washTimes.length];
    51 
    52         // Holds the maximum of the finishing times.
    53         int maxCompletionTime = -1;
    54 
    55         for (int c = 0; c < assignedColumns.length; c++)  {
    56             int columnAssignedTo = assignedColumns[c];
    57 
    58             // Here's the first (and only) time that the height comes into play.
    59             completionTimes[columnAssignedTo] += (washTimes[columnAssignedTo] * height);
    60 
    61             // See if this pushes the maxCompletionTime out.
    62             if (completionTimes[columnAssignedTo] > maxCompletionTime)  {
    63                 maxCompletionTime = completionTimes[columnAssignedTo];
    64             }
    65         }
    66 
    67         return maxCompletionTime;
    68 
    69  }
    70 
    71     /*
    72     * Calculates the times at which each washer could complete the current column
    73     * taking into account all previous columns that have been assigned to the
    74     * washer.
    75     * Note that at this point, the height of the building does not matter.  If a
    76     * washer could complete a 1 story column before another washer could, then
    77     * they could complete an N story column before the other.  Therefore,
    78     * completion times assume a height of 1.
    79     */
    80     private int[] calcCompletionTimes(int[] assignedColumns, int currentColumn, int[] washTimes)  {
    81 
    82         int[] completionTimes = new int[washTimes.length];
    83 
    84 
    85         /*
    86         * Completion time is at least the time it would take the washer
    87         * to do one window.
    88         */
    89         for (int i = 0; i < completionTimes.length; i++)  {
    90             completionTimes[i] = washTimes[i];
    91         }
    92 
    93         /*
    94         * Now, add in time for previously assigned columns.
    95         */
    96         for (int i = 0; i < currentColumn; i++)  {
    97             completionTimes[assignedColumns[i]] += washTimes[assignedColumns[i]];
    98         }
    99 
   100         return completionTimes;
   101 
   102     }
   103 }

Notes:

The idea is to start with a building of width w == 1, and add columns until w == width. Each new column will be assigned to the washer that can complete it the earliest. The assignedColumns[] array will hold the index of the washer assigned to that column. Note that at this point, the height of the building doesn't matter, and we can ignore the constraint that the washers cannot cross each other, since we're really just trying to determine the number of columns that each washer will do.

The method calcCompletionTimes() determines the time the each washer could complete the next column, taking into consideration all columns that the washer already has assigned to them. For example, if a washer has no columns assigned, then it's just the time that it takes the washer to do a column. If there are other columns assigned, we sum the time it takes to complete those, and add that to the time it takes to complete the column.

For our purpose here, it's safe to assume that all columns have a height 1. That is, if a window washer could complete a column of of height 1 before another washer; then they could complete the column earlier if the height had any other value.

After calculating the completion times, the loop on line 35 simply identifies the washer that could complete the column the earliest, and assigns it to them.

Once we've worked up to the entire width of the building, we just need to look for the washer that would complete their work last. This part is pretty trivial. We just have an array that holds the completion times for each washer. Then work through each of the assignedColumns, and increment the washer's completion time by the time it takes them to complete the column - all the while keeping track of the maximum completion time.

NumberGuesser

Problem:

TopCoder Problem Statement - NumberGuesser
Single Round Match 168 Round 1 - Division I, Level One
Single Round Match 168 Round 1 - Division II, Level Two

Overview:

Determine the starting number given the output of a specified algorithm.

Java Source:
     1 public class NumberGuesser {
     2 
     3  public int guess(String leftOver) {
     4 
     5   /*
     6   * Loop through all positions in leftOver, inserting the digits
     7   * 1..9 at each position.
     8   */
     9   for (int position = 0; position <= leftOver.length(); position++) {
    10    for (int digitToInsert = 1; digitToInsert < 10; digitToInsert++) {
    11 
    12     // Add digit back into leftOver
    13     String beforeRemovingDigit =
    14       leftOver.substring(0, position) +
    15         digitToInsert +
    16         leftOver.substring(position, leftOver.length());
    17 
    18     // Larger number - Smaller number = z
    19     int z = Integer.parseInt(beforeRemovingDigit);
    20 
    21     /*
    22     * Call larger number y
    23     * Call smaller number x
    24     * y - x = z or y = x + z
    25     */
    26     for (int x = 1; x < 5000; x++) {
    27      int y = x + z;
    28 
    29      // See if x and y have the same set of digits
    30      Integer i = missingDigit(x, y);
    31 
    32      if (missingDigit(x,y) == null) {
    33       return missingDigit(z, Integer.parseInt(leftOver));
    34      }
    35     }
    36    }
    37   }
    38 
    39   return -1;
    40  }
    41 
    42  /*
    43  * Return the first digit found that is in x, but not in y;
    44  * or in y but not in x.
    45  * Returns null if all the digits in x are in y and vice-versa.
    46  * Does not consider the digit 0.
    47  */
    48  private Integer missingDigit(int x, int y)  {
    49 
    50 
    51   int[] digits = new int[10];
    52 
    53   // Add the digits found in x
    54   while (x > 0)  {
    55    int i = x % 10; // Get the last digit
    56    digits[i]++;
    57    x /= 10;
    58   }
    59 
    60   // Subtract the digits found in y
    61   while (y > 0)  {
    62    int i = y % 10;
    63    digits[i]--;
    64    y /= 10;
    65   }
    66 
    67   // Skip over the digit 0
    68   for (int i = 1; i < 10; i++)  {
    69    if (digits[i] != 0) return i;
    70   }
    71 
    72   // Numbers have the same combination of digits.
    73   return null;
    74 
    75  }
    76 
    77 }
Notes:

I found this 500 point question more challenging than the 1100 point problem. Apparently, if you know the "trick" to it (see here), you can solve this in just a few lines. This solution works through the problem for those that don't know the trick.

First, note that the algorithm calls for two numbers x and y, such that y - x = z. Or, more conveniently y = x + z. The loops on lines 9 and 10 will generate every possible value for z by inserting the digits 1 through 9 into each position of the given leftOver string. Then we loop through all possible values of x. With candidates for x and z, we also have a candidate for y.

Now, if x and y are composed of the same digits, we get our answer. z must have been the number before the digit was removed. So, we just need to determine what digit is in z that is not in leftOver.

The method missingDigit() is used for both of these cases. If x and y are composed of the same digits, it will return null, otherwise it will return a digit that exists in one number but not the other. It works by creating an array to hold a count of each digit encountered. It loops through the first number and increments the count for each digit. Then it loops through the second number, and decrements the count for each digit there. If the numbers use the same set of digits, then everything should end up back at zero. Otherwise, return the digit with the first non-zero tally.

StairClimb

Problem:

TopCoder Problem Statement - StairClimb
Single Round Match 168 Round 1 - Division II, Level One

Overview:

Count the number of strides it takes to get up several flights of stairs.

Java Source:
     1 public class StairClimb {
     2 
     3         public int stridesTaken(int[] flights, int stairsPerStride) {
     4 
     5         int totalStrides = 0;
     6 
     7         for (int f = 0; f < flights.length; f++)  {
     8 
     9             // Get the number of strides in this flight.
    10             totalStrides += flights[f] / stairsPerStride;
    11 
    12             /*
    13             * If the last stride does not end evenly at the landing,
    14             * then we'll need one more stride.
    15             */
    16             if (flights[f] % stairsPerStride != 0) totalStrides++;
    17 
    18             // Add the two steps to turn at the landing.
    19             totalStrides += 2;
    20         }
    21 
    22         // We don't need to count the turn at the top.  Remove those strides.
    23         totalStrides -= 2;
    24 
    25         return (totalStrides < 0) ? 0 : totalStrides;
    26     }
    27 }
Notes:

Start with totalStrides equal to zero. Then for each flight of stairs, do the following:

  1. Get the whole number of strides that fits into this flight of stairs.
  2. If there are any remaining stairs, add one more stride to cover those.
  3. Add two strides to make the turn at the landing.

Next, remove two strides because we don't need to count the strides on the last landing.

Finally, make sure that we don't return less than 0. This could happen if the length of the flights array was 0.

Friday, May 8, 2015

Orchard

Problem:

TopCoder Problem Statement - Orchard
Single Round Match 167 Round 1 - Division II, Level Three

Overview:

Determine the position in an NxN array that is furthest from the edges, and from any tree.

Java Source:
     1 public class Orchard {
     2 
     3     int size;
     4     int[][] distances;
     5 
     6     public int[] nextTree(String[] orchard) {
     7 
     8         size = orchard.length;
     9 
    10         distances = new int[size][size];
    11 
    12         /*
    13         * Mark distances from the edges.
    14         * This create concentric squares with the distance
    15         * at the edges = 1, and the value increasing by
    16         * 1 as the squares move inward.
    17         */
    18         for (int i = 0; i < (size + 1) / 2; i++) {
    19             for (int j = i; j < (size - i); j++) {
    20                 distances[i][j] = i + 1;                // Top Row
    21                 distances[size - 1 - i][j] = i + 1;     // Bottom Row
    22                 distances[j][i] = i + 1;                // Left Column
    23                 distances[j][size - 1 - i] = i + 1;     // Right Column
    24             }
    25         }
    26 
    27         /*
    28         * Add trees into the mix
    29         * Updates the values in the distance matrix.
    30         */
    31         for (int row = 0; row < size; row++)  {
    32             for (int col = 0; col < size; col++)  {
    33                 if ('T' == orchard[row].charAt(col))  {
    34                     placeTree(row,col);
    35                 }
    36             }
    37         }
    38 
    39         /*
    40         * Find and return the greatest distance
    41         */
    42         int maxDistance = 0;
    43         int[] retValues = new int[] {1, 1};
    44 
    45         for (int y = 0; y < size; y++)  {
    46             for (int x = 0; x < size; x++)  {
    47                 if (distances[y][x] > maxDistance)  {
    48                     maxDistance = distances[y][x];
    49                     retValues[0] = y + 1;
    50                     retValues[1] = x + 1;
    51                 }
    52             }
    53         }
    54 
    55         return retValues;
    56     }
    57 
    58 
    59     /*
    60     * Places a tree at the given coordinate.  Then works outward from the
    61     * tree's location reducing the distances of it's neighboring squares.
    62     * Here's where all the work of updating the distances matrix is done.
    63     */
    64     private void placeTree(int row, int col)  {
    65 
    66         // Work the area above the tree.
    67         for (int dy = 0; row - dy >= 0; dy++)  {
    68 
    69             // Reduce neighbors above and to the left.
    70             for (int dx = 0; col - dx >= 0; dx++)  {
    71                 distances[row - dy][col - dx] =
    72                       Math.min(distances[row - dy][col - dx], dx + dy);
    73             }
    74 
    75             // Reduce neighbors above and to the right.
    76             for (int dx = 0; col + dx < size; dx++)  {
    77                 distances[row - dy][col + dx] =
    78                       Math.min(distances[row - dy][col +dx], dx + dy);
    79             }
    80         }
    81 
    82         // Works the area below the tree
    83         for (int dy = 0; row + dy < size; dy++)  {
    84 
    85             // Reduce neighbors below and to the left.
    86             for (int dx = 0; col - dx >= 0; dx++)  {
    87                 distances[row + dy][col - dx] =
    88                       Math.min(distances[row + dy][col - dx], dx + dy);
    89             }
    90 
    91             // Reduce neighbors below and to the right.
    92             for (int dx = 0; col + dx < size; dx++)  {
    93                 distances[row + dy][col + dx] =
    94                       Math.min(distances[row + dy][col +dx], dx + dy);
    95             }
    96         }
    97     }
    98 
    99 }

Notes:

There are several way to go about solving this problem. I've seen it solved using breadth-first search from every point in the grid. But, I believe this solution takes a far easier approach.

The idea is to create an NxN array that holds the distances from each point to and edge or a tree, then we can just scan through the distances array looking for the largest value. The loops on lines 18 - 25 initialize the array so that all elements on the outer edge have a value of 1. Then each concentric square moving inward gets increasing values. A 5x5 square, would look like this:

11111
12221
12321
12221
11111

Next, each tree is dropped into the matrix. The placeTree() method handles reducing the distance values in the matrix based on their proximity to the new tree. The method begins at the tree's location and then works by going upward one row at a time, first working to the left and then right. At each new location it determines if that distance should be reduced to the distance back to the tree, or left alone because its value was already smaller. After reaching the top of the matrix, the method starts over from the tree's location and works down to the bottom. Using the above example, a tree placed at location 2,1 would update the matrix to be:

11111
11221
10121
11221
11111

After all the trees have been placed, then it's a simple matter of looping through the distances array, and finding the largest value.