Monday, February 23, 2015

ParallelSpeedup

Problem:

TopCoder Problem Statement - ParallelSpeedup
Single Round Match 165 Round 1 - Division I, Level One
Single Round Match 165 Round 1 - Division II, Level Two

Overview:

Determine the number of processors that will finish a job in the shortest amount of time. Additional processors will help divide the load, but incur an exponential communication cost.

Java Source:
01: public class ParallelSpeedup {
02: 
03:     private static final int MAX_PROCESSORS = 1_000_000;
04: 
05:  public int numProcessors(int k, int overhead) {
06: 
07:         // Time it takes for 1 processor.
08:         long fastest = k;
09: 
10:         for (int processors = 2; processors <= MAX_PROCESSORS; processors++)  {
11: 
12:             // Calculate the communications overhead
13:             long o = ((processors * (processors - 1)) / 2) * overhead;
14: 
15:             /*
16:              * Total time is the overhead, plus the number of tasks divided
17:              * by the number of processors.
18:              */
19:             long time = o + (k / processors);
20: 
21:             /*
22:             * If the number of tasks does not divide evenly by the number
23:             * of processors, then we'll need 1 extra ms to finish the remaining
24:             * tasks.
25:             */
26:             if (k % processors != 0) time += 1;
27: 
28:             /*
29:             * As soon as time levels out or begins increasing, stop
30:             * and return the previous number of processors.  From here
31:             * on, time will keep increasing.
32:             */
33:             if (time >= fastest) return processors - 1;
34: 
35:             // record our new fastest time.
36:             fastest = time;
37: 
38:         }
39: 
40:         // Should never reach here.
41:         return -1;
42: 
43:  }
44: }
Notes:

The approach taken here is to calculate the time it takes to solve the problem using one processor, and then add additional processors until the time stops decreasing. There are two forces at work here. Each additional processor helps us by spreading the load. Whenever the number of processors doubles, the amount of time it takes to process the job is cut in half. As the number of processors grows, the gains diminish.

On the other hand, with additional processors, the communication overhead increases at an exponential rate. ((p * (p-1) / 2) * overhead Eventually, the cost of the communication overhead must overcome the benefit of additional processors. From that point on, additional processors will only slow the task down. Therefore, we can quit as soon as the time levels out or starts to become larger.

The time it takes to process the job is the communication overhead, plus the number of tasks divided by the number of processors. If the number of tasks does not divide evenly by the number of processors, then one extra round will be needed to complete those remainders.

Note that if the number of processors gets very large, it is likely that the values of o and time will overflow. By returning as soon as time begins increasing, this problem is avoided. Also note, that we can set the initial upper limit for the fastest time to k - that is the amount of time it would take 1 processor to handle k tasks.

BritishCoins

Problem:

TopCoder Problem Statement - BritishCoins
Single Round Match 165 Round 1 - Division II, Level One
Single Round Match 232 Round 1 - Division II, Level One

Overview:

Convert the given number of pence into pounds, shillings, and pennies.

Java Source:
01: public class BritishCoins {
02: 
03:     private static final int SHILLINGS_PER_POUND = 20;
04:     private static final int PENNIES_PER_SHILLING = 12;
05: 
06:     private static final int PENNIES_PER_POUND =
07:             PENNIES_PER_SHILLING * SHILLINGS_PER_POUND;
08: 
09:     public int[] coins(int pence)  {
10: 
11:         int[] ret = new int[3];
12: 
13:         ret[0] = pence / PENNIES_PER_POUND;
14:         ret[1] = (pence % PENNIES_PER_POUND) / PENNIES_PER_SHILLING;
15:         ret[2] = pence % PENNIES_PER_SHILLING;
16: 
17:         return ret;
18:     }
19: }
Notes:

Start by declaring constants to hold the number of shillings in a pound and the number of pennies in a shillings. Using that, we can calculate the number of pennies in a shilling (20 * 12 = 240). From here we can use simple math to derive our answer.

Remember that in Java, integer division chops off the remainder. so 10 / 3 = 3. Therefore, the number of pounds, is simply the number of pence / PENNIES_PER_POUND.

The moduls operator % gives us the remainder. To calculate the number of shillings, we first get the remainder of after taking out as many pounds as possible (pence % PENNIES_PER_POUND). Then, just as before, we divide that by PENNIES_PER_SHILLING to get the number of shillings.

The number of pennies remaining is just pence % PENNIES_PER_SHILLING.

Just store each of those values in the correct location of an int[] and the problem is solved.

Friday, February 20, 2015

Table

Problem:

TopCoder Problem Statement - Table
Single Round Match 157 Round 1 - Division I, Level Two

Overview:

Build a table given a number of cells which may span multiple rows and columns.

Java Source:
001: import java.util.ArrayList;
002: import java.util.List;
003: 
004: public class Table {
005: 
006:     private class Cell {
007:         private int colSpan;
008:         private int rowSpan;
009:         private char value;
010: 
011:         public Cell(String s) {
012: 
013:             if ((s == null) || (s.length() == 0)) {
014:                 this.colSpan = 0;
015:                 this.rowSpan = 0;
016:                 this.value = 0;
017:             } else {
018:                 s = s.replaceAll("[()]", "");  // Remove parentheses
019:                 String[] elements = s.split(",");
020:                 this.colSpan = Integer.parseInt(elements[0]);
021:                 this.rowSpan = Integer.parseInt(elements[1]);
022:                 this.value = elements[2].charAt(0);
023:             }
024:         }
025:     }
026: 
027:     int tableWidth;
028:     List table = new ArrayList<>();
029: 
030:     public String[] layout(String[] tbl) {
031: 
032:         tableWidth = calcTableWidth(tbl);
033: 
034:         for (int row = 0; row < tbl.length; row++) {
035: 
036:             // Add new row if necessary.
037:             while (table.size() <= row) {
038:                 table.add(row, new char[tableWidth]);
039:             }
040: 
041:             // Skip over any empty rows.
042:             if (isRowEmpty(tbl[row])) continue;
043: 
044:             int col = 0;
045: 
046:             Cell[] cells = parseCells(tbl[row]);
047: 
048:             for (int i = 0; i < cells.length; i++) {
049: 
050:                 // Skip over any columns that are already occupied.
051:                 col = getNextOpenCol(row, col);
052: 
053:                 // Write the cell's value into all locations that it occupies.
054:                 for (int r = 0; r < cells[i].rowSpan; r++) {
055:                     for (int c = 0; c < cells[i].colSpan; c++) {
056:                         tableInsert(row + r, col + c, cells[i].value);
057:                     }
058:                 }
059:             }
060:         }
061: 
062:         return tableToArray();
063:     }
064: 
065:     private int calcTableWidth(String[] s) {
066: 
067:         for (int i = 0; i < s.length; i++) {
068: 
069:             if (isRowEmpty(s[i])) {
070:                 continue;
071: 
072:             } else {
073: 
074:                 // Add up all the colSpans and return the sum.
075:                 Cell[] cells = parseCells(s[i]);
076: 
077:                 int width = 0;
078: 
079:                 for (Cell c : cells) {
080:                     width += c.colSpan;
081:                 }
082: 
083:                 return width;
084:             }
085:         }
086: 
087:         return 0;
088:     }
089: 
090:     private void tableInsert(int row, int col, char value) {
091: 
092:         // Add additional rows if necessary.
093:         while (table.size() <= row) {
094:             table.add(row, new char[tableWidth]);
095:         }
096: 
097:         table.get(row)[col] = value;
098:     }
099: 
100:     private int getNextOpenCol(int row, int col) {
101: 
102:         while (table.get(row)[col] != 0) {
103:             col++;
104:         }
105: 
106:         return col;
107:     }
108: 
109:     private String[] tableToArray() {
110: 
111:         String[] ret = new String[table.size()];
112: 
113:         for (int i = 0; i < table.size(); i++) {
114:             ret[i] = new String(table.get(i));
115:         }
116: 
117:         return ret;
118:     }
119: 
120:     private Cell[] parseCells(String s) {
121: 
122:         // Split on )(
123:         String[] elements = s.split("\\)\\(");
124: 
125:         Cell[] cells = new Cell[elements.length];
126: 
127:         for (int i = 0; i < elements.length; i++) {
128:             cells[i] = new Cell(elements[i]);
129:         }
130: 
131:         return cells;
132: 
133:     }
134: 
135:     // Consider a row empty if it does not contain any parenthesis.
136:     private boolean isRowEmpty(String s) {
137:         return !s.contains("(");
138:     }
139: }
Notes:

The solution presented here is perhaps more difficult than it needs to be. The problem's constraints limit the table's size to 50x50. This solution, however, works for an arbitrary sized table. Not knowing the table's maximum dimensions makes things more complicated.

The first step is to determine the width of the table. Since each row must be the same width, we can simply look for the first non-empty row, and add up all of the colspan values. This is handled in the calcTableWidth() method.

Now, the table can be represented as a List of arrays of chars, where each array of chars is sized to the table's width.

Then, we loop through each row, parse out the cell information and insert the cell's values into the appropriate rows and columns in the table. If a cell dips down into a row that doesn't yet exist in the table, we'll need to ensure that a new row is created first.

After each cell is inserted, getNextOpenCol() is called to advance to the next available column. This will allow us to skip over any cells that have already been added, especially cells that may have dipped down into the current row from earlier rows.

Thursday, February 19, 2015

CartInSupermarketEasy

Problem:

TopCoder Problem Statement - CartInSupermarketEasy
Single Round Match 649 Round 1 - Division I, Level Three

Overview:

Calculate the shortest time to remove a chain of shopping carts. In each unit of time, a chain of carts can either be split, or have a cart removed from the segment.

Java Source:
01: public class CartInSupermarketEasy {
02: 
03:  int[][] knownTimes;
04: 
05:  public int calc(int numCarts, int numSplits)  {
06: 
07:   knownTimes = new int[numCarts + 1][numSplits + 1];
08: 
09:   for (int i = 0; i <= numCarts; i++)  {
10:    for (int j = 0; j <= numSplits; j++)  {
11: 
12:     /*
13:     * It's clear that:
14:     * 0 carts will take 0 minutes
15:     * 1 cart will take 1 minute
16:     * 2 carts will take 2 minutes.
17:     */
18:     knownTimes[i][j] = (i <= 2) ? i : -1;
19: 
20:     /*
21:     * If there are no splits, the solution
22:     * is just the number of carts.
23:     */
24:     if (j == 0)  knownTimes[i][j] = i;
25:    }
26:   }
27: 
28:   int result = solve(numCarts, numSplits);
29: 
30:   return result;
31:  }
32: 
33:  private int solve(int numCarts, int numSplits)  {
34: 
35: 
36:   if (knownTimes[numCarts][numSplits] != -1)  {
37:    return knownTimes[numCarts][numSplits];
38:   }
39: 
40:   /*
41:   * In the worst case, we can solve this by removing 1 cart.
42:   * This will take 1 additional minute.
43:   */
44:   int time = solve(numCarts - 1, numSplits) + 1;
45: 
46:   /*
47:   * Try all combinations of splitting the carts and of dividing
48:   * up the number of splits remaining.  The time to handle
49:   * the whole segment will be the larger of the times it takes
50:   * to handle the two resulting split segments.
51:   */
52:   for (int x = 1; x < numCarts; x++)  {
53:    for (int y = 0; y < numSplits; y++)  {
54:     int timeSeg1 = solve(x, y);
55:     int timeSeg2 = solve(numCarts - x, numSplits - y - 1);
56:     int timeToProcessSegments = Math.max(timeSeg1, timeSeg2) + 1;
57:     time = Math.min(time, timeToProcessSegments);
58:    }
59:   }
60: 
61:   knownTimes[numCarts][numSplits] = time;
62:   return time;
63:  }
64: }
Notes:

This solution is a great example of Dynamic Programming. We'll begin with the minimum amount of time required to process a simple chain of carts (0, 1, or 2 cart chains), and then use that to calculate the time for longer chains. We continue using what we've already calculated to build up longer chains until we've reached our goal.

We start by declaring an int[][] knownTimes. The first dimension holds a number of carts, the second dimension is the number of splits allowed, and the value is the best time that we can achieve under those constraints. The array is initialized as follows:

  1. If the number of carts is 0, 1, or 2; then we can trivially remove all carts in 1 minute per cart.
  2. If there are 0 splits, then all we can do is remove 1 cart per minute.
  3. In all other cases, we set the value to -1 to denote that we'll need to calculate the value.

The real work is done in the solve() method. First, check to see if we already know the solution for the given number of carts and splits. If so, just return that. Otherwise, we'll need to calculate it. Note that at this point, the number of splits must be at least one, because we've initialized knownTimes with values for whenever the number of splits is 0.

We now have two options - we can either remove a cart, or try to split the chain. If we choose to remove a cart, our time will be solve(numCarts - 1, numSplits) plus 1 additional minute. This is the longest we could possibly need.

If we choose to split the carts, we can do so in many different ways. For a chain of x carts, the splits could result in segments of size (1, x-1), (2, x-2), ... (x-1, 1). And for each of these combinations, the number of splits can be divided up in numerous ways between the two resulting segments. The nested for loops work through all possibled combinations.

For each split that is considered, our time to solve will be the maximum of the time it takes to solve the two child segments, plus one additional minute (to perform the split). As each solution is calculated, we compare it to what we already have and keep the minimum. When done, we store the minimum time in knownTimes for future use, and then return it.

DecipherabilityEasy

Problem:

TopCoder Problem Statement - DecipherabilityEasy
Single Round Match 649 Round 1 - Division II, Level One

Overview:

Determine if a string can be formed from another, by dropping a single character.

Java Source:
01: public class DecipherabilityEasy {
02: 
03:     public String check(String s, String t) {
04: 
05:         // Make sure s has one character more than t
06:         if (s.length() != t.length() + 1) return "Impossible";
07: 
08:         int sIdx = 0;
09:         int tIdx = 0;
10: 
11:         // Walk through each letter in t.
12:         while (tIdx < t.length()) {
13:             if (s.charAt(sIdx) != t.charAt(tIdx)) {
14: 
15:                 /*
16:                 * If the characters don't match up, it's ok the first time.
17:                 * Skip a letter in s and move on.  If it happens again,
18:                 * return Impossible.
19:                 */
20:                 if (sIdx == tIdx) {
21:                     sIdx++;
22:                 } else {
23:                     return "Impossible";
24:                 }
25: 
26:             } else {
27:                 sIdx++;
28:                 tIdx++;
29:             }
30:         }
31: 
32:         return "Possible";
33: 
34:     }
35: }
Notes:

To solve this problem, we'll use two indexes sIdx and tIdx to walk through the Strings s and t. The indexes both start at position 0. So long as the characters are equal, the indexes increment together. If the character in s does not match the corresponding position in t, we'll advance sIdx - so long as sIdx and tIdx were previously equal. If the indexes were not equal, then we've found a second mismatch, so return "Impossible".

If we make it all the way to tIdx == t.length(), then return possible.

A check at the beginning of the method ensures that the length of s is exactly one character longer than t.

Monday, February 16, 2015

SpecialStrings

Problem:

TopCoder Problem Statement - SpecialStrings
Single Round Match 634 Round 1 - Division II, Level Three

Overview:

Find the next string in lexicographical order that meets a given condition.

Java Source:
01: public class SpecialStrings {
02: 
03:     public String findNext(String current) {
04: 
05:         // Work from right to left looking for the next '0'
06:         for (int i = current.length() - 1; i >= 0; i--) {
07:             if (current.charAt(i) == '0') {
08: 
09:                 /*
10:                 * Create a copy of the currentArray.  Each position
11:                 * less than i will match the corresponding position in
12:                 * currentArray, each position greater than i will equal '1'
13:                 */
14:                 char[] copyOfCurrent = new char[current.length()];
15:                 for (int j = 0; j < current.length(); j++) {
16:                     copyOfCurrent[j] = (j < i) ? current.charAt(j) : '1';
17:                 }
18: 
19:                 /*
20:                 * We've found a special string.  Let's see if we can do
21:                 * better by changing some characters to the right from
22:                 * 1's to 0's.
23:                 */
24:                 if (isSpecial(new String(copyOfCurrent))) {
25:                     
26:                     for (int j = i + 1; j < copyOfCurrent.length; j++) {
27:                         copyOfCurrent[j] = '0';
28: 
29:                         // If not special, change it back.
30:                         if (!isSpecial(new String(copyOfCurrent))) {
31:                             copyOfCurrent[j] = '1';
32:                         }
33:                     }
34: 
35:                     return new String(copyOfCurrent);
36:                 }
37:             }
38:         }
39: 
40:         return "";
41:     }
42: 
43:     private static final boolean isSpecial(String s) {
44: 
45:         for (int i = 1; i < s.length(); i++) {
46:             if (s.substring(0, i).compareTo(s.substring(i)) >= 0) return false;
47:         }
48:         return true;
49:     }
50: }
Notes:

Since we're looking for the next special string that follows current, it makes sense to work from right to left replacing 0's with 1's to find our next candidate. When we encounter a 0, we'll replace it with a 1, and then test to see if this new string is special. If is not, we move on to the next zero. If it is, we keep everything to the left, and set everything to the right to a 1. This gives us an upper bound on what the next special string could be.

With that upper bound, we then begin setting each position to the right to a 0, and then testing to see if that results in a special string. If it does, good, we'll leave it at 0 and carry on. If setting it to zero does not result in a special string, then we must change it back to a 1. When we reach the end of copyOfCurrent, we'll have the next special string ready to be returned.

ShoppingSurveyDiv2

Problem:

TopCoder Problem Statement - ShoppingSurveyDiv2
Single Round Match 634 Round 1 - Division II, Level Two

Overview:

Given a count of how many of each item was purchased, and the number of customers, determine the smallest number of customers that could have purchased one of each item.

Java Source:
01: public class ShoppingSurveyDiv2 {
02: 
03:     public int minValue(int N, int[] s) {
04: 
05:         int numItemsPurchased = 0;
06: 
07:         for (int i : s) {
08:             numItemsPurchased += i;
09:         }
10: 
11:         int maxItemsPurchasedWithNoBigShoppers = (s.length - 1) * N;
12: 
13:         int numBigShoppers =
14:                 numItemsPurchased - maxItemsPurchasedWithNoBigShoppers;
15: 
16:         return (numBigShoppers < 0) ? 0 : numBigShoppers;
17: 
18:     }
19: }
Notes:

First, we'll count the total number of items that have been purchased. This is stored in the variable numItemsPurchased.

Next, we calculate the number of items that could be purchased if every customer stopped just short of buying one of each. That is each customer, buys (s.length -1) items. We'll call that maxItemsPurchasedWithNoBigShoppers.

The number of BigShoppers that we'll need is now just the difference between numItemsPurchased and maxItemsPurchasedWithNoBigShoppers. This value may be negative, in which case we'll return zero.

This problem is a bit difficult to understand, but once you get it, the code is really easy.

MountainRanges

Problem:

TopCoder Problem Statement - MountainRanges
Single Round Match 634 Round 1 - Division II, Level One

Overview:

Count the number of peaks in a series of integers.

Java Source:
01: public class MountainRanges {
02: 
03:     public int countPeaks(int[] heights) {
04: 
05:         int peaks = 0;
06: 
07:         // If there are no elements, there can be no peaks.
08:         if (heights.length == 0)  return 0;
09: 
10:         /*
11:          * If there is just one element, it is bigger than it's (non-existent)
12:          * neighbors; and therefore a peak.
13:          */
14:         if (heights.length == 1) return 1;
15: 
16:         // Lengths must be at least 2 if we've reached this point.
17: 
18:         // Check left edge.
19:         if (heights[0] > heights[1]) peaks++;
20: 
21:         // Check right edge.
22:         if (heights[heights.length - 1] > heights[heights.length - 2]) peaks++;
23: 
24: 
25:         // Check everything in between
26:         for (int i = 1; i < heights.length - 1; i++) {
27:             if ((heights[i] > heights[i - 1]) && (heights[i] > heights[i + 1]))
28:                 peaks++;
29:         }
30: 
31:         return peaks;
32:     }
33: }
Notes:

First, check the special cases where the length of heights is either 0 or 1. Now that we know the length of heights must be at least 2, we having to check that our index is in bounds.

We check to see if the left edge is a peak, and then check the right edge.

Finally, we loop through each of the values in between. Not much to this problem.

Sunday, February 8, 2015

UserId

Problem:

TopCoder Problem Statement - UserId
Single Round Match 164 Round 1 - Division I, Level One

Overview:

Create a userId based on first, middle, and last names. Ensure there are no duplicates.

Java Source:
001: import java.util.Arrays;
002: import java.util.List;
003: 
004: public class UserId {
005: 
006:     private static final String BAD_DATA = "BAD DATA";
007:     private static final int ID_MAX_LENGTH = 8;
008: 
009:     public String id(String[] inUse, String first, String middle, String last) {
010: 
011:         // Check for invalid characters.
012:         String fullName = first + middle + last;
013:         for (int i = 0; i < fullName.length(); i++) {
014:             if (!isValidChar(fullName.charAt(i))) return BAD_DATA;
015:         }
016: 
017:         // Check for short first and last name;
018:         if (numLetters(first) < 2) return BAD_DATA;
019:         if (numLetters(last) < 2) return BAD_DATA;
020: 
021:         // Remove spaces, apostrophes, and convert to lowercase.
022:         first = normalizeName(first);
023:         middle = normalizeName(middle);
024:         last = normalizeName(last);
025: 
026:         // This will make it easier to see if the id is already in use.
027:         List inUseList = Arrays.asList(inUse);
028: 
029:         String userId;
030: 
031:         // Contains truncated last name, so the entire ID is <= than 8 chars.
032:         String shortLast;
033: 
034:         // Try [first initial][last name]
035:         if (last.length() > (ID_MAX_LENGTH - 1)) {
036:             shortLast = last.substring(0, ID_MAX_LENGTH - 1);
037:         } else {
038:             shortLast = last;
039:         }
040: 
041:         userId = first.substring(0, 1) + shortLast;
042:         if (!inUseList.contains(userId)) return userId;
043: 
044:         // Try [first initial][middle initial][last name];
045:         if ((middle != null) && (middle.length() >= 1)) {
046: 
047:             if (last.length() > (ID_MAX_LENGTH - 2)) {
048:                 shortLast = last.substring(0, ID_MAX_LENGTH - 2);
049:             } else {
050:                 shortLast = last;
051:             }
052: 
053:             userId = first.charAt(0) + (middle.charAt(0) + shortLast);
054: 
055: //            userId = first.substring(0, 1) + middle.substring(0, 1) + shortLast;
056:             if (!inUseList.contains(userId)) return userId;
057:         }
058: 
059:         // Try [first initial][last name][digit][digit]
060:         if (last.length() > (ID_MAX_LENGTH - 3)) {
061:             shortLast = last.substring(0, ID_MAX_LENGTH - 3);
062:         } else {
063:             shortLast = last;
064:         }
065: 
066:         int x = 1;
067:         while (x < 100) {
068:             String digits = String.format("%02d", x);
069:             userId = first.substring(0, 1) + shortLast + digits;
070:             if (!inUseList.contains(userId)) return userId;
071:             x++;
072:         }
073: 
074:         return null;
075:     }
076: 
077:     /*
078:     * Removes apostrophes and spaces, and converts upper-case
079:     * letters to lower case.
080:     */
081:     private static String normalizeName(String s) {
082: 
083:         if (s == null) return null;
084: 
085:         StringBuilder sb = new StringBuilder(s.length());
086: 
087:         for (int i = 0; i < s.length(); i++) {
088:             char c = s.charAt(i);
089: 
090:             if (c == ' ') continue;
091:             if (c == '\'') continue;
092:             if ((c >= 'A') && (c <= 'Z')) {
093:                 c = (char)(c + 'a' - 'A');
094:             }
095:             sb.append(c);
096:         }
097: 
098:         return sb.toString();
099:     }
100: 
101:     // Counts the number of characters in the String.
102:     private static int numLetters(String s) {
103: 
104:         int count = 0;
105: 
106:         for (int i = 0; i < s.length(); i++) {
107:             char c = s.charAt(i);
108:             if ((c >= 'a') && (c <= 'z')) count++;
109:             else if ((c >= 'A') && (c <= 'Z')) count++;
110:         }
111: 
112:         return count;
113: 
114:     }
115: 
116:     /*
117:     * Valid characters are a-z, A-Z, apostrophe, and space.
118:     */
119:     private static boolean isValidChar(char c) {
120: 
121:         if ((c >= 'a') && (c <= 'z')) return true;
122:         if ((c >= 'A') && (c <= 'Z')) return true;
123:         if (c == ' ') return true;
124:         if (c == '\'') return true;
125:         return false;
126: 
127:     }
128: }
Notes:

We'll start by validating the input against invalid characters. first, middle, and last are concatenated into one fullName String. Then we step through each character in fullName calling isValidChar().

Next, verify that first and last contain at least two letters. Be careful here, you can't just use String.length(). The problem specifically states that the name must have two letters - so "A' " would not be valid.

Note that Java's Character and String classes have methods for determining if a character is a letter and for converting to lower case. However, these get a bit tricky with non-ASCII characters, and different Locales. To avoid any surprises, I chose to write these out.

The method normalizeName() converts all letters to lower case, and removes all spaces and apostrophes. The conversion to lower case is easy, if it's an upper case letter (between 'A' and 'Z') we can add 'a' and then subtract 'A'. Note that we need to cast this back to a character, because the compiler will treat the expression as an int.

At this point, we're ready to begin building the userId. This is just a matter of following the rules given in the problem statement. Just two things to be aware of. First, make sure that the last name is truncated to a size that will make the userId no more than 8 characters. The variable shortLast is used here to store the first 5, 6, or 7 characters depending on the case.

Second, in the second case ([first initial][middle initial][last name]) you may be tempted to write something like this:

first.charAt(0) + middle.charAt(0) + shortLast

With this, you'll get something like "202jones" instead of the expected "bhjones". The reason is that the first two arguments are characters and are being added as if they are ints. The result of the addition is 202, which then gets added to the last name String. You can avoid this by putting parenthesis around the last two arguments, or use the String.substring() method to get a String type instead of a character.