Paternity Test

Problem:

TopCoder Problem Statement - PaternityTest

Overview:

Determine possible fathers given a DNA sequence from a child, mother, and array of potential fatehrs.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 155
04: Division: 2 / 1
05: Level: 3 / 1
06: Points: 1000 / 300
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1669
08:  */
09:
10: import java.util.ArrayList;
11: import java.util.List;
12:
13: public class PaternityTest {
14:
15:     public int[] possibleFathers(String child, String mother, String[] men) {
16:
17:         // Contains a list of fathers that cannot be ruled out
18:         List possibleList = new ArrayList<>();
19:
20:         for (int i = 0; i < men.length; i++) {
21:
22:             // Number of characters that match the father.
23:             int matches = 0;
24:
25:             // Is current father still possible?
26:             boolean isCurrentFatherPossible = true;
27:
28:             // Loop through each character in the sequence
29:             for (int j = 0; j < child.length(); j++) {
30:
31:                 String father = men[i];
32:
33:                 /*
34:                  * If the current character did not come from the mother,
35:                  * then it must come from the father.  If it did not come
36:                  * from the father, we can rule him out.
37:                  */
38:                 if ((child.charAt(j) != mother.charAt(j)) &&
39:                         ((father.charAt(j)) != (child.charAt(j)))) {
40:                     isCurrentFatherPossible = false;
41:                     break;
42:                 }
43:
44:                 // Count the number of matching characters.
45:                 if (father.charAt(j) == child.charAt(j)) {
46:                     matches++;
47:                 }
48:             }
49:
50:             /*
51:              * If the father has not been ruled out previously,
52:              * and the number of matches is >= half the length of the
53:              * sequence, then add the current father to the list of possible
54:              * fathers.
55:              */
56:             if (isCurrentFatherPossible && (matches >= (child.length() / 2))) {
57:                 possibleList.add(i);
58:             }
59:         }
60:
61:         // Convert the possibleList to an array, and return it
62:         int[] ret = new int[possibleList.size()];
63:
64:         for (int i = 0; i < ret.length; i++) {
65:             ret[i] = possibleList.get(i);
66:         }
67:
68:         return ret;
69:     }
70:
71: }

Notes:

There's just two checks needed to determine if the father can be ruled out or not. First, any character that did not come from the mother must come from the father. If the character at position x in the child's sequence is not equal to the character at position x in the mother's sequence, then it must match the character at position x in the father's sequence. If it does not, then we can eliminate the man from the list of potential fathers. This is tested for by the if statemet at line 38.

Second, the number of matches must be greater than or equal to half the length of the sequence. For this, we simply count the number of matches on lines 45-47.

If both conditions are met, the the man is added to the list of possible fathers. After looping through all the men, the possible fathers list is converted into an an array, and returned.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

BenfordsLaw

Problem:

TopCoder Problem Statement - BenfordsLaw

Overview:

Determine if any numbers in a set of data do not conform to Benford's law. That is the number of itmes that start with a 1 should fall within an expected range. The same goes for numbers starting with 2, 3, ... 9.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 155
04: Division: 2
05: Level: 2
06: Points: 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1348
08:  */
09:
10: public class BenfordsLaw {
11:
12:     /*
13:      * Given the number of transactions, returns an array of doubles that
14:      * represents the expected number of items for each starting digit.  The
15:      * index of the array corresponds to the starting digit.
16:      */
17:     private static double[] calculateExpectedArray(int numTransactions) {
18:
19:         /*
20:          * Make the array of length 10, and set the 0 position to 0.0.  0
21:          * will never be used, but this avoids having to adjust everything by
22:          * 1.
23:          */
24:         double[] exp = new double[10];
25:         exp[0] = 0.0;
26:
27:         /*
28:          * The probabibility for each position is given by the equation
29:          * log(base 10) of (1 + 1/D)
30:          * Multiply this by the number of tranactions to get the expected
31:          * number.
32:          */
33:         for (int i = 1; i < 10; i++) {
34:             exp[i] = (double) numTransactions *
35:                     Math.log10(1.0 + ((1.0 / (double) i)));
36:         }
37:
38:         return exp;
39:
40:     }
41:
42:     public int questionableDigit(int[] transactions, int threshold) {
43:
44:         int[] actual = new int[10];
45:         double[] expected = calculateExpectedArray(transactions.length);
46:
47:         // count the number of items that begin with each digit.
48:         for (int i : transactions) {
49:             actual[getFirstDigit(i)]++;
50:         }
51:
52:         // Look for digits that fall out of their expected range.
53:         for (int i = 1; i < 10; i++) {
54:             if (outOfRange((double) actual[i], expected[i], threshold)) {
55:                 return i;
56:             }
57:         }
58:
59:         return -1;
60:     }
61:
62:     // Returns the first digit of an integer.
63:     private int getFirstDigit(int i) {
64:
65:         while (i >= 10) {
66:             i /= 10;
67:         }
68:
69:         return i;
70:     }
71:
72:     // Returns true if the count is outside the expected range.
73:     private boolean outOfRange(double i, double e, int threshold) {
74:
75:         double lowerBound = e / (double) threshold;
76:         double upperBound = e * (double) threshold;
77:
78:         return ((i < lowerBound) || (i > upperBound));
79:     }
80: }

Notes:

There's just two parts to this solution, neigher of which is very challenging. First we need to determine the number of items we expect to begin with each digit using Benford's law. calculateExpectedArray() handles this part. Using the number of transactions, it calculates the number of items we should expect to see for each starting digit. These expected amounts are returned in an array where position 1 is the number we expect to see starting with the digit 1. position 2 is the number we expect to see starting with the digit 2, and so on up to 9. We should not get any items starting with 0, but we'll fill that in anyway just as a place holder to avoid having to shift all of our indexes by 1.

After determining the expected amounts, we count the number items that actually start with each digit. This is done by the loop starting at line 48. The method getFirstDigit() just divides by 10 until the number is less than 10, and then returns it. Another approach to getting the first digit might be converting the number to a String, and grabbing the character at position 0. It helps that all numbers are positive, but this wouldn't be too difficult to deal with were it not the case.

Finally, we check the amounts and determine if they fall between ((expected amount) / threshold) and ((expected amount) * threshold). The first number that falls outside this range is returned. If they all fall within the range, -1 is returned.

Just two things to be careful of. First, make sure that your equation for Benford's Law is correct - Line 34 (use log10 instead just log); and second make sure that you don't lose any precision when mixing doubles and integers.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

Quipu

Problem:

TopCoder Problem Statement - NAME

Overview:

Decode a rope with knots in it that represent an integer.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 155
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1686
08:  */
09:
10: public class Quipu {
11:
12:     public int readKnots(String knots) {
13:
14:         int value = 0;
15:         int current = 0;
16:
17:         for (int i = 1; i < knots.length(); i++) {
18:
19:             if (knots.charAt(i) == 'X') {
20:                 current += 1;
21:
22:             } else {
23:                 value *= 10;
24:                 value += current;
25:                 current = 0;
26:             }
27:
28:         }
29:
30:         return value;
31:     }
32: }

Notes:

The problem may seem difficult at first, but the solution is actually very simple. value holds the number that we're going to eventually return. current holds the count at the current tens place. For each X that we encounter, increment current. When a space is encountered, multiply value by ten, add current, and then reset current back to zero. That's all there is to it.

Just one more thing. Notice that the for loop at line 17 starts at 1 instead of 0. This skips over the first '-'. Every String is guaranteed to start with a dash, so we just just skip over it.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

FormatAmt

Problem:

TopCoder Problem Statement - FormatAmt

Overview:

Format a dollar amount according to a set of rules.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 149
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1313
08:  */
09: 
10: public class FormatAmt {
11: 
12:     /*
13:      * Formats the dollars portion of the string
14:      */
15:     private static String formatDollars(int d) {
16: 
17:         String s = String.valueOf(d);
18: 
19:         StringBuilder sb = new StringBuilder();
20: 
21:         /*
22:          * Starts from the digit neares the decimal point and works left
23:          * toward the most significant digit.  Inserts a comma after three
24:          * characters, unless it's the final character.
25:          */
26:         int count = 0;
27:         for (int i = s.length() - 1; i >= 0; i--) {
28: 
29:             // Copies the current character to the front of the StringBuilder
30:             sb.insert(0, s.charAt(i));
31:             count++;
32: 
33:             /*
34:              * After 3 characters, insert a comma.  But only if we're not now
35:              * at the left-most position.
36:              */
37:             if ((count == 3) && (i != 0)) {
38:                 sb.insert(0, ",");
39:                 count = 0;
40:             }
41:         }
42:         return sb.toString();
43:     }
44: 
45:     /*
46:      * Inserts leading 0's until the length is at least 2.
47:      */
48:     private static String formatCents(int c) {
49: 
50:         String s = String.valueOf(c);
51:         while (s.length() < 2) {
52:             s = "0" + s;
53:         }
54: 
55:         return s;
56:     }
57: 
58:     /*
59:      * Formats the dollars (to the left of the decimal point) and the cents
60:      * separately, then combines them to make the return value.
61:      */
62:     public String amount(int dollars, int cents) {
63: 
64:         return "$" + formatDollars(dollars) + "." + formatCents(cents);
65:     }
66: }

Notes:

The solution formats the dollars and cents portions separately, and then combines the together to form the return value.

Really the only tricky part is inserting the commas into the proper place in the dollars portion. This is handled by the for loop beginning at line 27. First, the variable count is initialized to 0. Then, the for loop works from right to left counting and inserting characters into a StringBuilder. When three characters have been seen, a comma is inserted, and count is set back to 0. If we're at the left-most position in the string, then the comma insertion is skipped.

Formatting the cents portion is even easier. There's a while loop that adds 0's on the beginning of the number until it's at least 2 wide.

Finally, the main method amount() combines the two, adding a "." between them, and prefixing the entire string with a "$"

Thank you for taking the time to read this solution. I welcome any feedback you may have.

BracketExpressions

Problem:

SRM 628 DIV 2 - 500 Points

Overview:

Parse opening and closing parenthesis, brackets, etc. Determine if the string is valid.

Java Source:

001: /*
002: TopCoder
003: Single Round Match: 638
004: Division: 2
005: Level: 2
006: Points: 500
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13243
008:  */
009: 
010: import java.util.HashMap;
011: import java.util.Map;
012: import java.util.Stack;
013: 
014: public class BracketExpressions {
015: 
016:     /*
017:      * A map that holds closing characters and their corresponding opening
018:      * characters.
019:      */
020:     Map openCloseMap = new HashMap<>();
021: 
022:     public String ifPossible(String expression) {
023: 
024:         openCloseMap.put(')', '(');
025:         openCloseMap.put(']', '[');
026:         openCloseMap.put('}', '{');
027: 
028:         Stack st = new Stack<>();
029: 
030:         return (isValid(expression, st) ? "possible" : "impossible");
031:     }
032: 
033:     private boolean isValid(String expression, Stack st) {
034: 
035:         /*
036:          * If we've reached the end of the input string,
037:          * return True only if the stack is empty.
038:          */
039:         if (expression.length() == 0) { return st.isEmpty(); }
040: 
041:         char c = expression.charAt(0);
042:         String s = expression.substring(1);  // Takes the first letter off.
043: 
044:         /*
045:          * If we encounter an opening character, push it on the stack,
046:          * and recursively call isValid() with the remaingins string
047:          */
048:         if (openCloseMap.containsValue(c)) {
049: 
050:             st.push(c);
051:             return isValid(s, st);
052: 
053:         /*
054:          * If we encounter a closing character, then the top item on the
055:          * stack had better be it's matching opening character.
056:          */
057:         } else if (openCloseMap.containsKey(c)) {
058: 
059:             Character expectedClosingChar = openCloseMap.get(c);
060: 
061:             if (st.isEmpty() || (st.pop() != expectedClosingChar)) {
062:                 return false;
063:             } else {
064:                 return isValid(s, st);
065:             }
066: 
067:             // We've encountered an 'X'
068:         } else {
069: 
070:             // Try replacing X with all characters.
071:             boolean canPush =
072:                     isValid(")" + s, copyStack(st)) ||
073:                             isValid("}" + s, copyStack(st)) ||
074:                             isValid("]" + s, copyStack(st)) ||
075:                             isValid("(" + s, copyStack(st)) ||
076:                             isValid("{" + s, copyStack(st)) ||
077:                             isValid("[" + s, copyStack(st));
078: 
079:             if (canPush) {
080:                 return true;
081: 
082:             /*
083:              * If using X to add a character to the stack doesn't seem to
084:              * work, see if it can be used to take the top character off
085:              */
086:             } else {
087:                 if (st.isEmpty()) { return false; }
088: 
089:                 if (openCloseMap.containsKey(st.pop())) {
090:                     return isValid(s, st);
091:                 }
092:             }
093: 
094:             return false;
095:         }
096:     }
097: 
098:     /*
099:      * To preseve the state of the stack we're working with,
100:      * create a copy of it before trying possible substitutions for X
101:      */
102:     private Stack copyStack(Stack st) {
103: 
104:         Stack newStack = new Stack<>();
105:         Stack tempStack = new Stack<>();
106: 
107:         while (!st.isEmpty()) {
108:             tempStack.push(st.pop());
109:         }
110: 
111:         while (!tempStack.isEmpty()) {
112:             char c = tempStack.pop();
113:             st.push(c);
114:             newStack.push(c);
115:         }
116: 
117:         return newStack;
118:     }
119: }

Notes:

The constraints tell us that there are at most 50 characters, and no more than 5 wildcards. Therefore, a brute force solution is entirely feasible.

First, a map is created to map each closing character ')', '}', and ']' to it's corresponding opening character '(', '{', and '['. This comes in handy, because we can call containsValue() to determine if we're looking at an opening character, and containsKey() for closing characters.

The solution uses a stack and pushes opening characters while popping off closing characters - each time shortening the lenght of the input string. If at any time, we encounter a closing character, and it's corresponding opening character is not the next item on the stack, then we have an invalid string - return false.

If we encounter a wildcard (an 'X'), then we'll try replacing it with all possible substitutions. Lines 63-69 append each opening and closing characters to the current string, make a copy of the current stack so it remains in tact, and then determines if the new string is valid.

If that fails to generate a valid string, then it's possible that the X takes the place of a closing bracket. The block starting at line 79 assumes that the X takes the place of a closing character that is ready to come off the stack and calls isValid() with the remaining string and stack elements.

If both the scenarios fail, then return false declaring the input to be impossible.

One possible optimization is to examine the length of the input string, it must be even. You could return false immediately if it's not. However, this may make your solution appear to be working correctly, when in fact it's not. A proper solution runs almost instantaneously, so it's worthwhile to allow itself to work through this case as it may uncover hidden bugs.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

Also, for updates, requests, further discussion, etc. please join our google+ page at http://google.com/+TopCodingSolutionsNet_GP

BigBurger

Problem:

TopCoder Problem Statement - BigBurder

Overview:

Simulate how long customers wait in line at a burger joint.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 149
04: Division: 2 / 1
05: Level: 2 / 1
06: Points: 500 / 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1648
08:  */
09: 
10: public class BigBurger {
11: 
12:     public int maxWait(int[] arrival, int[] service) {
13: 
14:         int maxWaitTime = 0;
15: 
16:         // Holds the time at which the customer's order is fullfulled.
17:         int[] orderFinishTime = new int[arrival.length];
18: 
19:         // Loop through all the customers.
20:         for (int i = 0; i < arrival.length; i++) {
21: 
22:             int startTime;
23: 
24:             if (i == 0) {
25:                 startTime = arrival[0];
26: 
27:             /*
28:              * At the earliest, the customer's start time is when they've
29:              * arrived.  If the previous order hasn't finished yet,
30:              * then they must wait until then.
31:              */
32:             } else {
33:                 startTime = Math.max(arrival[i], orderFinishTime[i - 1]);
34:             }
35: 
36:             orderFinishTime[i] = startTime + service[i];
37: 
38:             // Determine how long this customer had to wait.
39:             int waitTime = orderFinishTime[i] - service[i] - arrival[i];
40: 
41:             if (waitTime > maxWaitTime) {
42:                 maxWaitTime = waitTime;
43:             }
44:         }
45: 
46:         return maxWaitTime;
47:     }
48: }

Notes:

For each customer, we calculate the finish time for their order. For the first customer, that's just their arrival time plus the service time. For each remaining customer, it will either be their arrival time, or the finishing time of the customer ahead of them, plus the service time.

The first customer must be handled separately to avoid through an array index out of bounds exception on line 31.

Once we have the finish time for the customer, we calculate their wait time by subtracting off their arrival and service times. If this wait time is longer than any we've seen so far, save it in maxWaitTime.

As a side note, I found this to be pretty easy for a Division 2 - 500 Point problem. Compare it against BracketExpression which has the same point value.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

WidgetRepairs

Problem:

TopCoder Problem Statement - WidgetRepairs

Overview:

Determine the number of days it will take a repair shop to work through the incoming items.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 150
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1346
08:  */
09:
10: public class WidgetRepairs {
11:
12:     public int days(int[] arrivals, int numPerDay) {
13:
14:         // Holds the number of items available to work on.
15:         int queue = 0;
16:
17:         // Counts the number of days worked.
18:         int workingDays = 0;
19:
20:         // Loop through each of the days.
21:         for (int arrival : arrivals) {
22:
23:             /*
24:              * Increment the queue by the number of items that arrived that
25:              * day.  If the queue is > 0, count it as a working day.
26:              * */
27:             queue += arrival;
28:             if (queue > 0) { workingDays++; }
29:
30:             // Remove from the queue the number of items processed in a day.
31:             queue -= numPerDay;
32:             if (queue < 0) { queue = 0; } // But dont' go below 0.
33:         }
34:
35:         // Work through the remaining items.
36:         while (queue > 0) {
37:             workingDays++;
38:             queue -= numPerDay;
39:         }
40:
41:         return workingDays;
42:     }
43: }

Notes:

Each day, the repair shop takes in a number of items, and works through some other number of items. This solution uses the variable queue to store any left over items that built up from previous days.

Any day that had items to work on (either from a previous day, or that arrived that day) are counted as a working day.

There's just two things to be careful of. First, when subtracting off the number of items that are processed in a day, make sure the queue doesn't go below zero - Line 32. And second, after items have stopped arriving, be sure to count the remaining days to work through the backlog - Lines 36-39

Thank you for taking the time to read this solution. I welcome any feedback you may have.

BishopMove

Problem:

TopCoder Problem Statement - BishopMove

Overview:

Count the number of moves it takes for a bishop to move from one square to another on a chess board.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 628
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13280
08:  */
09: 
10: public class BishopMove {
11: 
12:  public int howManyMoves(int r1, int c1, int r2, int c2) {
13: 
14:         // Get the number of rows and columns that the bishop must move.
15:         int rowDiff = Math.abs(r2 - r1);
16:         int colDiff = Math.abs(c2 - c1);
17: 
18:         //  Check for no moves necessary
19:         if ((rowDiff == 0) && (colDiff == 0)) return 0;
20: 
21:         /*
22:          * If the number of rows that change is the same as the number of
23:          * columns that change, we can reach it in one move.
24:          */
25:         if (rowDiff == colDiff) return 1;
26: 
27:         /*
28:          * If the difference is not a multiple of 2 (i.e. up 1 row,
29:          * and over 2) then the square cannot be reached.
30:          */
31:         if (((rowDiff - colDiff) % 2) != 0) return -1;
32: 
33:         // In any other case, the square can be reached in 2.
34:         return 2;
35: 
36:  }
37: }

Notes:

It helps to think in terms of the basic properties of how a Bishop moves. The following three rules are all you need to solve this problem:

1. If the change in the number of rows from the starting square to the destination is the same as the change in the number of columns; then the Bishop can reach that square in 1 move.
2. From it's starting position, the Bishop can reach any square where the difference in rows minus the difference in columns is an even multiple of 2.
3. Any square that can be reached by the Bishop will take at most 2 moves.

This logic is implemented on lines 25, 31, and 34, and respectively.

Add to that a quick check at line 19 to see if any move is even necessary, and you're done.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

ManySquares

Problem:

TopCoder Problem Statement - ManySquares

Overview:

Determine how many squares can be made from a collection of sticks.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 627
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13277
08:  */
09:
10: import java.util.HashMap;
11: import java.util.Map;
12:
13: public class ManySquares {
14:
15:  public int howManySquares(int[] sticks) {
16:
17:         /*
18:          * Holds a mapping between the lenght of a stick,
19:          * and the number of sticks found of that length.
20:          */
21:         Map sticksOfLength = new HashMap<>();
22:
23:         for (int i : sticks)  {
24:
25:             /*
26:              * If a stick of this length has already been seen,
27:              * increment the count.  Otherwise initialize the count for this
28:              * size to 1.
29:              */
30:             if (sticksOfLength.containsKey(i))  {
31:                 sticksOfLength.put(i, sticksOfLength.get(i) +  1);
32:             } else  {
33:                 sticksOfLength.put(i,1);
34:             }
35:
36:         }
37:
38:         int count = 0;
39:
40:         /*
41:          * For each length of stick in the map, divide it's count by 4 to get
42:          * the number of squares that can be made of that length.  Increase
43:          * the total count by that amount.
44:          */
45:         for (int i : sticksOfLength.keySet())  {
46:             count += sticksOfLength.get(i) / 4;  // Rounds down, no fractions.
47:         }
48:
49:         return count;
50:  }
51: }

Notes:

When I began reading the problem description, I thought this was going to be a whole lot harder than it turned out to be. I envisioned having to combine sticks toghether to form each side. Maybe one 3 + 1 side, a size 4 stick on another side, and two 2 + 2 on the remaining sides. That would make an interesting problem, but it would be way beyond division 2 - 250 points.

Luckily, the problem states that the square can only be made up of 4 sticks.

I chose to use a HashMap to map a stick size, to the number of sticks found that are of that size. The Map's key is a size, and the value is the count. The for loop at line 23 iterates through the input array, and either sets or increments the count for each stick.

Then, it iterates through all the map's keys (the stick sizes), and divides the count by 4. This is integer division, so only the whole number of divisors is returned. (i.e. 3 / 4 = 0, 5 / 4 = 1). It increments the count by that amount, and finally returns the result.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

BrickByBrick

Problem:

TopCoder Problem Statement - BrickByBrick

Overview:

Simulate a BreakOut type game, where a ball bounces around destroying bricks.

Java Source:

001: /*
002: TopCoder
003: Single Round Match: 150
004: Division: 2
005: Level: 3
006: Points: 1100
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1751
008:  */
009:
010: import java.util.HashSet;
011: import java.util.Set;
012:
013: public class BrickByBrick {
014:
015:     /*
016:      * Prints out the current state of the board and ball.  The ball is
017:      * represented as an 'o'.
018:      */
019:     private static void printState(int[][] board, Ball ball) {
020:
021:         System.out.println(ball.toString());
022:
023:         for (int y = 0; y < board.length; y++) {
024:             for (int x = 0; x < board[0].length; x++) {
025:                 if ((y == ball.y) && (x == ball.x)) {
026:                     System.out.print('o');
027:                 } else if (board[y][x] < 0) {
028:                     System.out.print('#');
029:                 } else {
030:                     System.out.print(board[y][x]);
031:                 }
032:             }
033:             System.out.println();
034:         }
035:         System.out.println();
036:     }
037:
038:     public int timeToClear(String[] map) {
039:
040:         int numBricks = 0;
041:
042:         int sizeX = (map[0].length() * 2) + 1;
043:         int sizeY = (map.length * 2) + 1;
044:
045:         int[][] board = new int[sizeY][sizeX];
046:
047:         /*
048:          * Create an indestructible boarder around the board.  Indestructible
049:          * bricks are represented by a -1.
050:          */
051:
052:         // Top and bottom borders
053:         for (int x = 0; x < sizeX; x++) {
054:             board[0][x] = -1;
055:             board[sizeY - 1][x] = -1;
056:         }
057:
058:         // Right and left borders
059:         for (int y = 0; y < sizeY; y++) {
060:             board[y][0] = -1;
061:             board[y][sizeX - 1] = -1;
062:         }
063:
064:         // Load the board.
065:         int y = 1;
066:         for (String s : map) {
067:             int x = 1;
068:             for (char c : s.toCharArray()) {
069:                 switch (c) {
070:                     case '.':
071:                         break;
072:
073:                     case 'B':
074:                         numBricks++;
075:
076:                         /*
077:                          * Increase the count on all it's edges.  If the edge
078:                          * is shared with an indestructible neighbor,
079:                          * leave it alone
080:                          */
081:                         if (board[y - 1][x] >= 0) {
082:                             board[y - 1][x] += 1;
083:                         }
084:                         if (board[y + 1][x] >= 0) {
085:                             board[y + 1][x] += 1;
086:                         }
087:                         if (board[y][x - 1] >= 0) {
088:                             board[y][x - 1] += 1;
089:                         }
090:                         if (board[y][x + 1] >= 0) {
091:                             board[y][x + 1] += 1;
092:                         }
093:                         break;
094:
095:                     // Set the edges for an indestructible brick.
096:                     case '#':
097:                         board[y - 1][x] = -1;
098:                         board[y + 1][x] = -1;
099:                         board[y][x - 1] = -1;
100:                         board[y][x + 1] = -1;
101:                 }
102:                 x += 2;
103:             }
104:             y += 2;
105:         }
106:
107:         Ball ball = new Ball();
108:
109:         /*
110:          * Holds a set of integers representing the state of the ball.  If we
111:          * see the same state again, then declare an infinite loop.
112:          * The set is cleared whenever a brick is broken.
113:          */
114:         final Set loopDetector = new HashSet<>();
115:
116:         int moves = 0;
117:
118:         // Quit if we've seen this state before.
119:         while (!loopDetector.contains(ball.getState())) {
120:
121:             moves++;
122:
123:             loopDetector.add(ball.getState());
124:
125:             // May not pass timing tests if this is enabled.
126: //            printState(board, ball);
127:
128:             ball.move();
129:
130:             // Space is empty
131:             if (board[ball.y][ball.x] == 0) {
132:                 continue;
133:
134:                 // An indestructible brick, just change directions.
135:             } else if (board[ball.y][ball.x] < 0) {
136:                 ball.changeDir();
137:
138:                 // Found a brick to break
139:             } else {
140:
141:                 numBricks--;
142:                 if (numBricks == 0) { return moves; }
143:
144:                 loopDetector.clear();  // Reset the infinite loop detector.
145:
146:                 int brokenBrick_x;
147:                 int brokenBrick_y;
148:
149:                 /*
150:                  * Determine if we hit a side of the brick, or the top/bottom.
151:                  * Use this to get the position of the middle of the brick.
152:                  */
153:                 if (ball.isSide) {
154:                     brokenBrick_x = ball.x + ball.deltaX;
155:                     brokenBrick_y = ball.y;
156:                 } else {
157:                     brokenBrick_x = ball.x;
158:                     brokenBrick_y = ball.y + ball.deltaY;
159:                 }
160:
161:                 /*
162:                  * Decrement the count for all the edges of this brick,
163:                  * unless the edge is shared with an indestructible brick.
164:                  */
165:                 if (board[brokenBrick_y][brokenBrick_x + 1] > 0) {
166:                     board[brokenBrick_y][brokenBrick_x + 1] -= 1;
167:                 }
168:                 if (board[brokenBrick_y][brokenBrick_x - 1] > 0) {
169:                     board[brokenBrick_y][brokenBrick_x - 1] -= 1;
170:                 }
171:                 if (board[brokenBrick_y - 1][brokenBrick_x] > 0) {
172:                     board[brokenBrick_y - 1][brokenBrick_x] -= 1;
173:                 }
174:                 if (board[brokenBrick_y + 1][brokenBrick_x] > 0) {
175:                     board[brokenBrick_y + 1][brokenBrick_x] -= 1;
176:                 }
177:
178:                 ball.changeDir();
179:             }
180:         }
181:
182:         return -1;  // Infinit loop detected.
183:     }
184:
185:     private class Ball {
186:
187:         int x;
188:         int y;
189:         short deltaX;
190:         short deltaY;
191:
192:         /*
193:          * On every move, the ball alternates between passing through
194:          * aTop/Bottom, or a Side
195:          */
196:         boolean isSide = false;
197:
198:         // Ball always starts in Top Left square going down and to the right.
199:         Ball() {
200:             this.x = 1;
201:             this.y = 0;
202:             this.deltaX = 1;
203:             this.deltaY = 1;
204:         }
205:
206:         void move() {
207:             x += deltaX;
208:             y += deltaY;
209:             isSide = !isSide;
210:         }
211:
212:         void changeDir() {
213:             if (isSide) {
214:                 deltaX *= -1;
215:             } else {
216:                 deltaY *= -1;
217:             }
218:         }
219:
220:         /*
221:          * Returns a unique int based on the position and movement of the
222:          * ball.  This will be used to determine if we've entered an infinite
223:          * loop.  If no bricks have been broken since the last time this
224:          * state was seen, then it's time to quit.
225:          */
226:         int getState() {
227:             int state = 1;
228:             state = (state * 100) + x;
229:             state = (state * 100) + y;
230:             state = (state * 10) + deltaX + 1;
231:             state = (state * 10) + deltaY + 1;
232:             return state;
233:         }
234:
235:         public String toString() {
236:             return "X=" + x + " Y=" + y + " deltaX=" + deltaX + " deltaY=" +
237:                     deltaY +
238:                     " isSide=" + isSide + " state=" + getState();
239:         }
240:     }
241:

Notes:

This was a fun little problem to solve. I've left the printState() method in the source above so you can see the ball bouncing around. Just un-comment line 126 to enable it.

The first problem was in determining how to represent the board. I choose to use a 2-dimensional array, roughly twice as large (in each dimension) as the input array. First, the board is surrounded with indestructible bricks. This avoids the trouble of detecting when the ball reaches the edge of the plaing area. The two loops at lines 53, and 59 create this border.

The loop beginning at line 65 sets up the interior of the playing area. Each brick in the input maps to four surrounding edges in the board. The edges are represented as an integer which is a count of the number of bricks that share that edge. Any edge shared with an indestructible brick has a count of -1. The following example helps to illustrate:

    Inuput:
    .B
    BB

    board:
    -1  o -1 -1 -1
    -1  .  1  B -1
    -1  1     2 -1
    -1  B  2  B -1
    -1 -1 -1 -1 -1

    o - The ball, at it's starting position.

    (Note: the .'s and B's in board are only present for illustration,
    they are not stored in the array.)
   

The next problem is how to model the ball's movement. The details of this are captured within the Ball class. There are two variables, x and y, that keep track of it's position. deltaX, and deltaY track how the position changes from move to move. deltaX and deltaY both initially have a value of 1. When the ball bumps into a brick, either deltaX or deltaY is multiplied by -1 to change it's direction.

An important insight is that on every move, the ball will alternate between passing through a top/bottom and a left/right edge. This state is stored in the Ball class's isSide boolean variable. So, if the ball hits a brick, and isSide is true, then we negate deltaX. If isSide is false, then deltaY is negated.

Collisions are detected by comparing the ball's position to the matching position in the board. If the board contains a -1, then the brick is indestructible, and we simple call changeDir(). If the board contains a number > 0, then a breakable brick has been hit. First, we decrement the brick count and check to see if all bricks have been destroyed. Failing that, we find the center of the brick that was hit using the ball's position, whether it's hitting a side or top/bottom, and the direction the ball was moving. This logic is done on lines 153-159. From the center, we decrement the edge count on all surrounding, non-indestructible, bricks. Note, that the edge the ball struck must now be 0.

In the illustration above, the ball will move down and right and encounters a 1. isSide will be true, so we know the center of the brick that was struck will either be one spot to the left or one to the right of the ball's current position. By looking at deltaX, we see the ball was moving left-to-right, and therefore, the center is the B on 2nd row from the top. On the next move, the ball will be moving right to left, and will strike the edge while isSide = false. The center of the brick will be the B in the second column from the left.

So far, we have a ball that will bounce around the arena destroying bricks until there are none left. The final step is to detect when there are un-reachable bricks. For this, I created a Set called loopDetector and the Ball class's getState() methods. On each move, getState() is called and the value is stored in the loopDetector. If the ball ever returns to the same position, and is moving in the same direction, then getState() will return a value that already exists in the loopDetector set. Declare an infinity loop, and return -1 to quit.. Whenever a brick is broken, the loopDetector set is cleared.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

CircleGame

Problem:

TopCoder Problem Statement - CircleGame

Overview:

Simulate a simple card game.

Java Source:

01: /*
02: TopCoder
03: Single Round Match: 148
04: Division: 1
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1735
08:  */
09: public class CircleGame {
10:
11:     // Use this value to represent cards that have been removed.
12:     private static final int REMOVED = -1;
13:
14:     /*
15:       Given an index into deck, returns the next card that hasn't been removed.
16:       Handles looping around the end of the array by using the mod operator.
17:       If we return to the given index without finding a valid card,
18:       then return -1.
19:      */
20:     private static int getNextCardIndex(int start, int[] deck) {
21:
22:         int next = (start + 1) % deck.length;
23:
24:         while (next != start) {
25:             if (deck[next] != REMOVED) { return next; }
26:             next = (next + 1) % deck.length;
27:         }
28:
29:         return -1; // No valid cards found.
30:     }
31:
32:     public int cardsLeft(String deck) {
33:
34:         // We'll use an array to represent the deck of cards.
35:         int[] deckArray = new int[deck.length()];
36:
37:         // Convert the characters in deck to an integer array
38:         for (int i = 0; i < deck.length(); i++) {
39:             char c = deck.charAt(i);
40:
41:             switch (c) {
42:                 case 'A':
43:                     deckArray[i] = 1;
44:                     break;
45:                 case 'T':
46:                     deckArray[i] = 10;
47:                     break;
48:                 case 'J':
49:                     deckArray[i] = 11;
50:                     break;
51:                 case 'Q':
52:                     deckArray[i] = 12;
53:                     break;
54:                 case 'K':
55:                     deckArray[i] = REMOVED;  // Don't bother even adding them.
56:                     break;
57:                 default:
58:                     deckArray[i] = c - '0';
59:             }
60:         }
61:
62:         boolean madeMove = true;
63:
64:         /*
65:         Each time we remove a card, we'll start back from the beginning of
66:         the deck.  The loop exits when the end of the deck is reached,
67:         and no moves have been made.
68:          */
69:         while (madeMove) {
70:             madeMove = false;
71:
72:             for (int i = 0; i < deckArray.length; i++) {
73:
74:                 // Skip past any cards that have been removed.
75:                 if (deckArray[i] == REMOVED) { continue; }
76:
77:                 // -1 if there is no next card.
78:                 int nextCardIndex = getNextCardIndex(i, deckArray);
79:
80:                 if ((nextCardIndex >= 0) &&
81:                         ((deckArray[i] + deckArray[nextCardIndex]) == 13)) {
82:                     deckArray[i] = REMOVED;
83:                     deckArray[nextCardIndex] = REMOVED;
84:                     madeMove = true;
85:                     break;  // Start back from the beginning of the deck.
86:                 }
87:             }
88:         }
89:
90:         // Count the number of cards remaining.
91:         int count = 0;
92:         for (int aDeckArray : deckArray) {
93:             if (aDeckArray != REMOVED) {
94:                 count++;
95:             }
96:         }
97:         return count;
98:     }
99: }

Notes:

The deck is represented as an array of integers. To initialize the array, we just loop through all the characters in deck and assign them a value using the switch statement. Two things to note here: First, cards that have been removed are represented as a -1. This allows us to easily skip over those cards. No need to use an ArrayList, LinkedList or any other structure where you actually remove elements. Second, since the first action is to remove all Kings, we'll just take care of that up front. Lines 54 and 55 set all K's to -1.

Next we enter a loop that will terminate only when we go through the entire deck without making a move. The loops always starts from the beginning of the deck skipping any cards that have been removed. When it gets to the first valid card, it then calls getNextCardIndex() get the next card in the deck. getNextCardIndex() handles skipping over removed cards as wells as looping from the end back to the beginning of the deck. If the two cards add up to 13, they're both marked as removed.

Finally, when no moves could be made, the while loop exits, and we count up the number of cards that have not been marked as removed.

Perhaps the most difficult part is the logic in getNextCardIndex(). Just be thoughtful about using the mod division operator, test for removed cards, and stop if you've looped all the way throught the deck.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

MasterBrain

Problem:

TopCoder Problem Statement - Masterbrain

Overview:

Simulate a classic board game with a slight twist.

Java Source:

    001: /*
    002: TopCoder
    003: Single Round Match: 146
    004: Division: 1
    005: Level: 2
    006: Points: 600
    007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1541
    008:  */
    009:
    010: public class Masterbrain {
    011:
    012:     /*
    013:     A good solution is one in which all the results match the corresponding
    014:     guesses - except for 1.
    015:     Loop through each of the guess/result pairs for the solution checking to
    016:     see if one, and only one, does not match up.
    017:      */
    018:     private static boolean goodSolution(String solution, String[] guesses,
    019:                                         String[] results) {
    020:
    021:         boolean lied = false;
    022:
    023:         for (int i = 0; i < guesses.length; i++) {
    024:
    025:             // Always a single digit, and always in the same spot.
    026:             int numBlack = Integer.parseInt("" + results[i].charAt(0));
    027:             int numWhite = Integer.parseInt("" + results[i].charAt(3));
    028:
    029:             if (!resultMatches(guesses[i], solution, numBlack, numWhite)) {
    030:                 if (lied) {
    031:                     return false;  // That's two lies - return false.
    032:                 } else {
    033:                     lied = true; // First lie.
    034:                 }
    035:             }
    036:         }
    037:
    038:         return lied;
    039:     }
    040:
    041:     /*
    042:     Compares the guess with the solutions, and returns whether or not the
    043:     number of black and white pegs matches up.
    044:      */
    045:     private static boolean resultMatches(String guess, String solution,
    046:                                          int numBlack, int numWhite) {
    047:
    048:         // Used to keep tracks of which pegs have already been assigned.
    049:         boolean[] usedBlack = new boolean[guess.length()];
    050:         boolean[] usedWhite = new boolean[guess.length()];
    051:
    052:         // Check if numBlack matches
    053:         int numInCorrectPosition = 0;
    054:
    055:         for (int i = 0; i < guess.length(); i++) {
    056:             if (guess.charAt(i) == solution.charAt(i)) {
    057:                 numInCorrectPosition++;
    058:                 usedBlack[i] = true;
    059:             }
    060:         }
    061:
    062:         // If numBlack does not match, no point in checking the white pegs.
    063:         if (numInCorrectPosition != numBlack) {
    064:             return false;
    065:         }
    066:
    067:         // Check if numWhite matches
    068:         int numOutOfPositon = 0;
    069:         for (int i = 0; i < guess.length(); i++) {
    070:
    071:             /*
    072:             If we're looking at a position that has already been assigned a
    073:             black peg, then continue.
    074:              */
    075:             if (usedBlack[i]) {
    076:                 continue;
    077:             }
    078:
    079:             for (int j = 0; j < guess.length(); j++) {
    080:
    081:                 // Again, skip over assigned pegs.
    082:                 if (usedBlack[j]) {
    083:                     continue;
    084:                 }
    085:
    086:                 if ((guess.charAt(i) == solution.charAt(j)) && !usedWhite[j]) {
    087:                     numOutOfPositon++;
    088:                     usedWhite[j] = true;
    089:                     break;  // Skip to next i, not j.
    090:                 }
    091:             }
    092:         }
    093:
    094:         return numOutOfPositon == numWhite;
    095:     }
    096:
    097:     public int possibleSecrets(String[] guesses, String[] results) {
    098:
    099:         int count = 0;
    100:
    101:         /*
    102:         Generate all possible solutions.  For each solution,
    103:         if it meets the criteria of a good solution, then increment count.
    104:         When done, return count.
    105:          */
    106:         for (char h = '1'; h < '8'; h++) {
    107:             for (char i = '1'; i < '8'; i++) {
    108:                 for (char j = '1'; j < '8'; j++) {
    109:                     for (char k = '1'; k < '8'; k++) {
    110:                         String solution = "" + h + i + j + k;
    111:                         if (goodSolution(solution, guesses, results)) {
    112:                             count++;
    113:                         }
    114:                     }
    115:                 }
    116:             }
    117:         }
    118:
    119:         return count;
    120:     }
    121: }

Notes:

possibleSecrets() generates all possible secret codes. There's only 7 * 7 * 7 * 7 = 2,401 of them, so it's not that many. For each of the possible code, it calls goodSolution() to see if the solution, guesses, and results agree. If so, the count is increased. When done, count will contain the number of solutions that satisfy the game's criteria.

goodSolution() loops through all the guess/response pairs for the given solution, and determines if they satisfy the rules of the game. That is, one, and only one, result does not agree with the given guess and solution. You might think that being able to lie once would make the game much more difficult, but it doesn't. Initially, lied is set to false. The first time a response doesn't match the guess, lied gets set to true. If it happens again, then return false - this cannot be a good solution, since there were two mis-matches. When done, return lied, which will be true if one was found, and false if not.

The most difficult part of the problem is determining if the response matches the guess for the given solution. This is handled in resultMatches(). First, it checks if the number of black pegs matches the number of items in guess that in their correct position. Then, it looks for items that match, but are out of place. Just be careful here to avoid double-counting. The usedBlack[] and usedWhite[] arrays are for keeping track of pegs that have already been accounted for.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

MessageMess

Problem:

TopCoder Problem Statement - MessageMess

Overview:

Given a dictionary determine the possible word combinations that may be in a message.

Java Source:

01: /*
    02: TopCoder
    03: Single Round Match: 149
    04: Division: 1
    05: Level: 2
    06: Points: 500
    07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1331
    08:  */
    09:
    10: public class MessageMess {
    11:
    12:     public String restore(String[] dictionary, String message) {
    13:
    14:         /*
    15:          * Holds the number of ways the message can be recreated up to a given
    16:          * point.  numOfSolutions[0] = 1, represents the one starting state.
    17:          * numOfSolutions[x] is the number of ways the substring beginning
    18:          * with the first x characters of the message can be reached.
    19:          */
    20:         int[] numOfSolutions = new int[message.length() + 1];
    21:         numOfSolutions[0] = 1;
    22:
    23:         /*
    24:          *  Holds the restored string from the message recreated up to a
    25:          *  given point.
    26:          *  If no solutions exists to get to that character x,
    27:          *  then solutions[x] holds IMPOSSIBLE!.
    28:          *  If two or more solutions are found that lead to character x,
    29:          *  then solutions[x] holds "AMBIGUOUS!".
    30:          */
    31:         String[] solutions = new String[message.length() + 1];
    32:
    33:         // Initialize the array.
    34:         solutions[0] = "";
    35:         for (int i = 1; i < solutions.length; i++) {
    36:             solutions[i] = "IMPOSSIBLE!";
    37:         }
    38:
    39:         // Loop through each position in the message.
    40:         for (int position = 0; position < message.length(); position++) {
    41:
    42:             // Only process if positon can be reached once unambiguously.
    43:             if (numOfSolutions[position] == 1) {
    44:
    45:                 for (String word : dictionary) {
    46:
    47:                     // The size the message would be if word were tacked on.
    48:                     int newSize = position + word.length();
    49:
    50:                     /*
    51:                      * If adding this dictionary word to our current
    52:                      * position would take us beyond the length of the
    53:                      * message; or, the dictionary word does not match the
    54:                      * next sequence in the message, then skip it.
    55:                      */
    56:                     if ((newSize <= message.length()) &&
    57:                             (word.equals(message.substring(position,
    58:                                     newSize)))) {
    59:
    60:                         /*
    61:                          * Set the number of ways to reach the new size to
    62:                          * either 1 or 2 - depending on if it was 0 or 1
    63:                          * before.  If it's now 2, mark it as ambiguous.
    64:                          */
    65:
    66:                         if (numOfSolutions[newSize] == 0) {
    67:                             numOfSolutions[newSize] = 1;
    68:                             solutions[newSize] = solutions[position] + " " +
    69:                                     word;
    70:                         } else {
    71:                             numOfSolutions[newSize] = 2;
    72:                             solutions[newSize] = "AMBIGUOUS!";
    73:                         }
    74:                     }
    75:                 }
    76:             }
    77:         }
    78:
    79:         return solutions[solutions.length - 1].trim();
    80:     }
    81: }

Notes:

In my first attempt at this problem, I used a solution involving tries. Everything went smoothly, it passed all my tests on the first attempt. I submitted to the TopCoder arena, and it passed all their tests - except test #27. There's a 2 second time limit, and my code took about two and a half minutes to pass. Time to scrap the code, and use a better algorithm.

The second attempt uses dynamic programming and is a huge improvement performance wise. Test #27 now runs in 0.008 seconds!

It begins by initializing two arrays: numOfSolutions[] and solutions[]. numOfSolutions[x] contains the number of ways that position x in the message can reached starting from the beginning. So, if my dictionary contains {"H", "I", "HI"}, and the message is "HIT" - there are two ways to arrive at the letter T. Either start with H, then use I; or just start with HI. The goal is numOfSolutions[numOfSolutions.length - 1] = 1. That is - there is one, and only one, way to reach the end of the message.

The second array solutions[] contains the decoded message that led up to that point. Each position is initialized to "IMPOSSIBLE!". The first time a position is reached, solutions[x] gets set to the decoded message at that point. If the position is reached again via another path, then solutions[x] is set to "AMBIGUOUS!".

Then, it's just a matter of looping through each character in the message. If there was no way to reach that character, or if that character has been reach by more than one path, then we'll skip it - leaving it as either IMPOSSIBLE! or AMBIGUOUS!.

If there is one path to that character, then we try appending each dictionary word to our current position. If adding the dictionary word does not take us beyond the end of the message, and it matches the next sequence of characters, then we'll mark the end of the new combined message as having 1 solution if it had 0 before, or 2 if it had 1 before. There's no need to keep incrementing the solution count beyond 2. If the solution count becomes 2, the solution is marked as AMBIGUOS!.

Upon reaching the return statement, the solutions array will contain either IMPOSSIBLE!, AMBIGUOUS!, or a valid solution for every substring of the message that starts at the beginning. So, it's just a matter of returning the last value, and not forgetting to trim off the final space.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

NumberGuessing

Problem:

TopCoder Problem Statement - NumberGuessing

Overview:

Choose the best number in a guessing game.

Java Source:

001: /*
002: TopCoder
003: Single Round Match: 148
004: Division: 1
005: Level: 3
006: Points: 1100
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1747
008:  */
009:
010: import java.util.Arrays;
011: import java.util.HashSet;
012: import java.util.Set;
013:
014: public class NumberGuessing {
015:
016:     /*
017:      * Returns a set of all Integers that should be tried.  If there are no
018:      * guesses to follow, then the set will be:
019:      * 1 less than the smallest guess.
020:      * 1 greater than all previous guesses.
021:      * If there are more guesses to follow, then return all integers in the
022:      * range.
023:      * In either case, do not add any numbers that already appear in guesses.
024:      */
025:     public static Set getPossibleGuesses(int range, int[] guesses,
026:                                                   boolean isLast) {
027:
028:         Set possibleGuesses = new HashSet<>();
029:
030:         if (isLast) {
031:
032:             // If there are no guesses, and no guesses to follow, just return 1
033:             if (guesses.length == 0) {
034:                 possibleGuesses.add(1);
035:                 return possibleGuesses;
036:
037:                 /*
038:                 * If there are guesses to follow, return one less than the
039:                 * smallest guess, and one greater than all other guesses.
040:                 * Be sure to check that we're not adding < 1 or > range.
041:                 */
042:             } else {
043:                 if (guesses[0] > 1) {
044:                     possibleGuesses.add(guesses[0] - 1);
045:                 }
046:
047:                 for (int g : guesses) {
048:                     if (g < range) {
049:                         possibleGuesses.add(g + 1);
050:                     }
051:                 }
052:             }
053:
054:             /*
055:              * If there are guesses to follow, then we'll check every number
056:              * in the range that hasn't alredy been guesses.
057:              */
058:         } else {
059:             for (int i = 1; i <= range; i++) {
060:                 possibleGuesses.add(i);
061:             }
062:         }
063:
064:         for (int i : guesses) {
065:             possibleGuesses.remove(i);
066:         }
067:
068:         return possibleGuesses;
069:     }
070:
071:     /*
072:      * Makes the best guess possible based on the guesses that have been taken,
073:      * and the number of guesses to follow.  Returns an array that equals
074:      * guesses, except that the new best guess is inserted.
075:      * The best guess is obtained by following these steps.
076:      * 1. Obtain possible guesses.
077:      * 2. For each possible guess, call makeBestGuess recursively to get how
078:      * all the following guessers will respond.
079:      * 3. Check what the yield is for that guess (how many numbers = a win)
080:      * 4. Repeat for all other possible guesses, keeping track of the largest
081:      * yield.
082:      */
083:     public GuessResults makeBestGuess(int range, int[] guesses,
084:                                       int numLeft) {
085:
086:         // When numLeft < 0, return to break the recursion.
087:         if (numLeft < 0) {
088:             return new GuessResults(guesses);
089:         }
090:
091:         // Used to keep track of the best guess tried so far and it's result.
092:         int maxYield = 0;
093:         GuessResults maxResults = new GuessResults();
094:
095:         Set possibleGuesses = getPossibleGuesses(range, guesses,
096:                 (numLeft == 0));
097:
098:         for (int possibleGuess : possibleGuesses) {
099:
100:             /*
101:              * Make a copy of the guesses array, and insert the new guess into
102:              * its proper location.
103:              */
104:             int[] beforeTry = Arrays.copyOf(guesses, guesses.length + 1);
105:             beforeTry[beforeTry.length - 1] = possibleGuess;
106:             Arrays.sort(beforeTry);
107:
108:             /*
109:              * Recursively call makeBestGuess() using this current guess and
110:              * check the results.
111:              */
112:             GuessResults afterTry = makeBestGuess(range, beforeTry,
113:                     numLeft - 1);
114:             afterTry.guess = possibleGuess;
115:
116:             int yield = calculateYield(possibleGuess, afterTry.results, range);
117:
118:             if ((yield > maxYield) ||
119:                     ((yield == maxYield) &&
120:                             (possibleGuess < maxResults.guess))) {
121:                 maxYield = yield;
122:                 maxResults = afterTry;
123:             }
124:         }
125:
126:         return maxResults;
127:     }
128:
129:     /*
130:      * Given an array of guesses, returns how many numbers result in a win
131:      * for the given guess.
132:      * The given guess must exist in the array of guesses.
133:      */
134:     public int calculateYield(int guess, int[] guesses, int range) {
135:
136:         int yield;
137:
138:         // Determine the position of guess in the array of guesses.
139:         int i = 0;
140:         while (guesses[i] != guess) {
141:             i++;
142:         }
143:
144:         // This guess is the lowest.
145:         if (i == 0) {
146:             yield = guess + ((guesses[i + 1] - guess - 1) / 2);
147:
148:             // This guess is the highest.
149:         } else if (i == (guesses.length - 1)) {
150:             yield = (range - guess + 1) + ((guess - guesses[i - 1] - 1) / 2);
151:
152:             // This guess is somewhere in between two other guesses.
153:         } else {
154:             yield = (((guesses[i + 1] - guess - 1) / 2)
155:                     + 1 +
156:                     ((guess - guesses[i - 1] - 1) / 2));
157:         }
158:
159:         return yield;
160:     }
161:
162:     /*
163:      * Loops through all possible guesses to determine which one results in
164:      * the greatest yeild.
165:      */
166:     public int bestGuess(int range, int[] guesses, int numLeft) {
167:
168:         // If there is only one number possible, take it and quit early.
169:         if (range == 1) {
170:             return 1;
171:         }
172:
173:         return makeBestGuess(range, guesses, numLeft).guess;
174:     }
175:
176:     /*
177:      * Ties a guess to the resulting array of guesses
178:      */
179:     private class GuessResults {
180:         int[] results;
181:         Integer guess;
182:
183:         GuessResults() {
184:             this.results = null;
185:             this.guess = Integer.MAX_VALUE;
186:         }
187:
188:         GuessResults(int[] results) {
189:             this.results = results;
190:             this.guess = Integer.MAX_VALUE;
191:         }
192:     }
193: }

Notes:

There's a lot of pitfalls waitng in this problem. I'll start with an overview of the solution, and then go into some of the mistakes that I made along the way.

The solution first obtains a list of numbers that it should try. It's farily clear that if there are no guesses to follow, then your guess should either be 1 lower that the lowest guess, or 1 higher than a previous guess. Any number picked between two numbers will yield the same number of wins as any other number picked between those same two numbers, so it's sufficient just to try the lowest in any segment.

The first problem comes up when trying to determine which numbers to pick when you're not that last to go. You might just pick numbers that are at the mid-point between two previous guesses. A more sophisticated approach might introduce the number of guesses to follow. So pick the 1/2 point, if there is one guess to follow. Pick 1/4 way points if there are two guesses to follow, etc. This will drive you nuts, and is ultimately unnecessary - maybe - see below.

The specs limit the range and number of followers sufficiently so that you can use brute force on any guess that has followers. The numbers to try in this case are just all numbers that haven't been guessed previously.

Armed with the list of number to try, we loop through each of them. First, we re-create the guesses[] array adding the current number that we're trying. Then we pass this new array, along with one less follower to makeBestGuess(). This returns an array containting all the responses from all the followers for that guess. Next, we check how many numbers will result in a win with that guess, and finally, store that guess and the results if it yielded more wins than anything previously seen.

One thing that was more annoying than difficult is the fact that makeBestGuess() and bestGuess() require two different return values. makeBestGuess() needs an array of ints that represents all of the resulting guesses; while bestGuess() just need the guess itself. To solve this problem, and avoid a lot of duplicate code, I introduced the GuessResults inner class to tie the guess and it's response together.

The final difficult part is in calculating the number of wins that a given guess yields. This is handled by the calculateYield() method. It expects an array containing all the guesses, both before and after our guess, as well as our guess and also the range. There are three separate equations: One if our guess is the lowest, one if it's the highest, and one if it falls between two other guesses. Care, and a lot of testing, are needed to get these right.

As a final note, the longest running test in the TopCoder arena took 3.7 seconds to complete, which is greater than the 2 seconds they allow. However, on my machine, the same test ran in .4 seconds, so I can live with it.

I tried some optimizations, such as replacing the calls to Arrays.sort() with a customized sort that took advantage of the fact that there was only one number to add. These didn't add up to much. If I had to get that test down under 2 seconds, I'd need to revisit the getPossibleGuesses() method for guesses that had followers.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

PowerOutage

Problem:

SRM 144 DIV 2 - 1100 Points

Overview:

Find the shortest amount of time required to traverse a series of tunnels connected in a tree-like layout.

Java Source:

    001: /*
    002: TopCoder
    003: Single Round Match: 144
    004: Division: 2
    005: Level: 3
    006: Points: 1100
    007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1697
    008:  */
    009:
    010: import java.util.ArrayList;
    011:
    012: public class PowerOutage {
    013:
    014:     private static final int MAX_JUNCTIONS = 50;
    015:
    016:     /* Each tunnel will need to be traversed twice, once on the way out and
    017:     then again on the way back.  However, if we save the longest tunnel for
    018:     last, then the power can go back on before we return along the longest
    019:     path.  Therefore the estimate time out is 2 * the sum of all the lenghts,
    020:      minus the longest length.
    021:      */
    022:     public int estimateTimeOut(int[] fromJunction, int[] toJunction,
    023:                                int[] ductLength) {
    024:
    025:         int sumOfLengths = 0;
    026:         for (int i : ductLength) sumOfLengths += i;
    027:
    028:         int longestLength = getLongestLength(fromJunction, toJunction,
    029:                 ductLength);
    030:
    031:         return (2 * sumOfLengths) - longestLength;
    032:     }
    033:
    034:     /*
    035:     Creates a graph representing the tunnels and junctions.  Then calls
    036:     getMaxLength() to determine the longest path.
    037:      */
    038:     private int getLongestLength(int[] from, int[] to, int[] length) {
    039:
    040:         EdgeWeightedDigraph graph = new EdgeWeightedDigraph(MAX_JUNCTIONS);
    041:
    042:         for (int i = 0; i < from.length; i++) {
    043:             graph.addEdge(new DirectedEdge(from[i], to[i], length[i]));
    044:         }
    045:
    046:         return getMaxLength(graph, 0);
    047:     }
    048:
    049:     /*
    050:     Uses recursion to return the length of the longest path beginning at the
    051:     source.
    052:      */
    053:     private int getMaxLength(EdgeWeightedDigraph graph, int source) {
    054:
    055:         int max = 0;
    056:
    057:         for (DirectedEdge edge : graph.getAdjacent(source)) {
    058:             int length = edge.weight + getMaxLength(graph, edge.to);
    059:             if (length > max) { max = length; }
    060:         }
    061:
    062:         return max;
    063:     }
    064:
    065:     /*
    066:     Holds a to and from junction, and the weight(distance) between them
    067:      */
    068:     class DirectedEdge {
    069:
    070:         final int from;
    071:
    072:         final int to;
    073:
    074:         final int weight;
    075:
    076:         DirectedEdge(int from, int to, int weight) {
    077:             this.from = from;
    078:             this.to = to;
    079:             this.weight = weight;
    080:         }
    081:     }
    082:
    083:     /*
    084:     A slimmed down Edge-Weighted Directed Graph.
    085:      */
    086:     class EdgeWeightedDigraph {
    087:
    088:         private final ArrayList[] adjLists;
    089:
    090:         EdgeWeightedDigraph(int numVertices) {
    091:             adjLists = new ArrayList[numVertices];
    092:             for (int i = 0; i < numVertices; i++) {
    093:                 adjLists[i] = new ArrayList();
    094:             }
    095:         }
    096:
    097:         void addEdge(DirectedEdge e) {
    098:             adjLists[e.from].add(e);
    099:         }
    100:
    101:         Iterable getAdjacent(int vertex) {
    102:             return adjLists[vertex];
    103:         }
    104:     }
    105: }

Notes:

First, the tunnels are laid out in a tree-like fashion. So there is only one path from the root to each junction and there are no loops.
Second, The power can go back on as soon as the last junction is reached.
Each tunnel will be traversed twice, once on the way out, and once again on the way back. Except for the longest length. We save the longest path for last, since the power can then go back on without having to wait for our return trip. Therefore, the estimated time is (2 * the sum of all tunnel lenghts) - (the length of the longest path)
Determining the sum of all lengths is trivial (Lines 25-26). Finding the longest path is a bit tougher. For this, I borrowed some code from an Edge-Weighted Directed Graph class that I was working with recently. The class is stripped down so that it only contains the addEdge() and getAdjacent() methods.
The graph is created by feeding it source junctions, destination junctions, and the time it takes to traverse the tunnel; all wrapped up in the form of a DirectedEdge class (Lines 40-44). It then calls getMaxLength() to determine the longest path starting from the source.
getMaxLength() determines the longest path rooted at the given junction by recursively calling getMaxLenght() on each of it's adjacent junctions and adding the distance to that adjacent junction.

Thank you for taking the time to read this solution. I welcome any feedback you may have.
For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

CodeChef: Dish Owner

Problem Statement:

CodeChef: Dish Owner

Overview:

Keep track of winners in a cooking competition.

Java Source:

    01: /*
    02: CodeChef
    03: July Challenge 2014
    04: Description: http://www.codechef.com/JULY14/problems/DISHOWN
    05:  */
    06:
    07: import java.io.File;
    08: import java.util.Scanner;
    09:
    10: public class DishOwner {
    11:
    12:     public static void main(String[] args) throws Exception {
    13:
    14:         Scanner sc;
    15:
    16:         // If an arg is given, read from that file. Otherwise use stdin.
    17:         if (args.length > 0) {
    18:             File f = new File(args[0]);
    19:             sc = new Scanner(f);
    20:         } else {
    21:             sc = new Scanner(System.in);
    22:         }
    23:
    24:         // Get number of Test Cases
    25:         int numTestCases = Integer.parseInt(sc.nextLine());
    26:
    27:         for (int i = 0; i < numTestCases; i++) {
    28:
    29:             // Get number of Chefs
    30:             int numOfChefs = Integer.parseInt(sc.nextLine());
    31:
    32:             // Set dish owners
    33:             int[] owners = new int[numOfChefs];
    34:             for (int owner = 0; owner < numOfChefs; owner++) {
    35:                 owners[owner] = owner;
    36:             }
    37:
    38:             // Set scores for each Dish
    39:             int[] scores = new int[numOfChefs];
    40:
    41:             int dish = 0;
    42:             for (String s : sc.nextLine().split(" ")) {
    43:                 scores[dish++] = Integer.parseInt(s);
    44:             }
    45:
    46:             // Get number of Queries
    47:             int numOfQueries = Integer.parseInt(sc.nextLine());
    48:
    49:             // Process each query
    50:             for (int q = 0; q < numOfQueries; q++) {
    51:                 String[] query = sc.nextLine().split(" ");
    52:
    53:                 if (query.length == 3) {
    54:                     doCompetition(Integer.parseInt(query[1]) - 1,
    55:                             Integer.parseInt(query[2]) - 1, scores, owners);
    56:                 } else {
    57:                     System.out.println(getDishOwner(Integer.parseInt
    58:                             (query[1]) - 1, owners) + 1);
    59:                 }
    60:             }
    61:         }
    62:     }
    63:
    64:     private static void doCompetition(int dish1, int dish2, int[] scores,
    65:                                       int[] owners) {
    66:
    67:         int chef1 = getDishOwner(dish1, owners);
    68:         int chef2 = getDishOwner(dish2, owners);
    69:
    70:         if (chef1 == chef2) {
    71:             System.out.println("Invalid query!");
    72:             return;
    73:         }
    74:
    75:         if (scores[dish1] > scores[dish2]) {
    76:             owners[dish2] = chef1;
    77:         } else if (scores[dish2] > scores[dish1]) {
    78:             owners[dish1] = chef2;
    79:         } else {
    80:             // Tie. do nothing
    81:         }
    82:     }
    83:
    84:     private static int getDishOwner(int dish, int[] owners) {
    85:
    86:         int chef = dish;
    87:         while (owners[dish] != chef) {
    88:             chef = owners[dish];
    89:         }
    90:         return chef;
    91:     }
    92: }

Notes:

This is the first problem that I've attempted on the CodeChef.com site. I haven't registered for an account there, so I did not submit this code, and therefore I cannot guarantee that it passes their tests. It does however pass their example and my own unit tests.

The algorithm works by maintaining two integer arrays - scores, and owners. There are at most 10^4 chefs, and scores may be as large as 10^6 which easily fit into an int. Scores simply holds the scores for each dish. Once set, their values never change. owners initially holds the chef that brought the dish to the competion, but as challenges are won and lost, these values change.

The problem states that each chef chooses their dish optimally, and there is no constraint prohibiting them from using the same dish multiple times. I took this to mean that they always put up their highest scoring dish which will be the dish they started with since it's impossible to obtain one with a higher score. This also means that if the value in the owners array matches it's index, then that chef has never lost.

When a competition starts, I first determine the owner of the two dishes, more on this next. It checks to see if the owners are the same. Then determines a winner (or a tie). Here, the loser's owner is set to the winning chef. That is, in the owners array, the value at index loser is set to the winner: owners[loser] = winner

Now, to determine a dish's owner, we look into the owners array, and follow the chain up until the owner of the dish is the same value as the chef. The following table shows the state of the owners array after a series of competitions.

	owners
Initial Setup:	index 0 1 2 value 0 1 2
Dish 2 beats Dish 0:	index 0 1 2 value 2 1 2
Dish 1 beats Dish 2:	index 0 1 2 value 2 1 1

To determine the owner of dish 0 after this series of competitions, we look at owners[0] and see the value is 2. Since 0 != 2, we then look at owners[2] and see the vaue of 1. Again, 2 != 1, so we continue following the chain by looking at owners[1]. Here, the index matches the value, so we conclude that 1 is the owner of dish 0.

Be careful about subtracting 1 from the index (Lines 54, 55, and 58) since the chefs and scores are numbered starting at 1 while our array starts at 0. We then need to add 1 back on when printing out the owner.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

Dragons

Problem:

TopCoder Problem Statement - Dragons

Overview:

Divide food up among 6 hungry Dragons.

Java Source:

001: /*
002: TopCoder
003: Single Round Match: 147
004: Division: 1
005: Level: 2
006: Points: 500
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1520
008:  */
009:
010: import java.math.BigDecimal;
011:
012: public class Dragons {
013:
014:     // The side of the cube we'll be returning.
015:     private static final int SNAUGS_SIDE = 2;
016:
017:     public String snaug(int[] initialFood, int rounds) {
018:
019:         /*
020:         Any two sides are neighbors if their numbers do not add up to 7.
021:          */
022:         int[] neighbors = {1, 6, 2, 5, 3, 4};
023:
024:         // Copy the initialFood amounts into the currentRound.
025:         Fraction[] currentRound = new Fraction[6];
026:         for (int i = 0; i < currentRound.length; i++) {
027:             currentRound[i] = new Fraction(initialFood[i]);
028:         }
029:
030:         // Loop for the given number of rounds.
031:         for (int round = 1; round <= rounds; round++) {
032:
033:             // Create an array of fractions to hold the results.
034:             Fraction[] nextRound = new Fraction[6];
035:             for (int j = 0; j < nextRound.length; j++) {
036:                 nextRound[j] = new Fraction(0);
037:             }
038:
039:             // Loop through all size sides.
040:             for (int side = 0; side < 6; side++) {
041:
042:                 // Loop for all neighboring sides.
043:                 for (int neighbor = 0; neighbor < 6; neighbor++) {
044:
045:                     /*
046:                     The side is a neighbor if, and only if, side != neighbor,
047:                      and their two values in the neighbors array do not add
048:                      up to 7.
049:                      */
050:                     if ((neighbor == side) || (neighbors[side] +
051:                             neighbors[neighbor] == 7)) { continue; }
052:
053:                     // Add the neighbors value.
054:                     nextRound[side] = nextRound[side].add
055:                             (currentRound[neighbor]);
056:                 }
057:
058:                 // At the end of the round divide by 4 to get 1/4.
059:                 nextRound[side] = nextRound[side].div(4);
060:             }
061:
062:             // Set currentRound to prepare for the next loop.
063:             currentRound = nextRound;
064:         }
065:
066:         return currentRound[SNAUGS_SIDE].toString();
067:     }
068:
069:     /*
070:     This class handles all the fraction operations that we'll need.  The
071:     tests like to overflow even longs, so the internals are stored as
072:     BigDecimals.
073:      */
074:     public class Fraction {
075:
076:         // Used in several places, so let's just have one copy.
077:         final BigDecimal Zero = new BigDecimal(0);
078:
079:         BigDecimal numerator;
080:
081:         BigDecimal denominator;
082:
083:         Fraction(BigDecimal num, BigDecimal den) {
084:             this.numerator = num;
085:             this.denominator = den;
086:             reduce();
087:         }
088:
089:         Fraction(long num) {
090:             this.numerator = new BigDecimal(num);
091:             this.denominator = new BigDecimal(1);
092:         }
093:
094:         /*
095:         Adds another fraction to this fraction.  Return a new instance.
096:          */
097:         public Fraction add(Fraction f) {
098:
099:             BigDecimal num;
100:             BigDecimal den;
101:
102:             // If the denominators are equal, just add the numerators.
103:             if (this.denominator.equals(f.denominator)) {
104:                 den = this.denominator;
105:                 num = this.numerator.add(f.numerator);
106:
107:                 // Otherwise, cross-multiply.
108:             } else {
109:                 num = (this.denominator.multiply(f.numerator)).add(
110:                         (this.numerator.multiply(f.denominator)));
111:
112:                 den = (this.denominator).multiply(f.denominator);
113:             }
114:
115:             return new Fraction(num, den);
116:         }
117:
118:         /*
119:         Divides this fraction by an int.  Returns a new instance.
120:          */
121:         public Fraction div(int x) {
122:
123:             // Division is done by multiplying the denominator by x.
124:             return new Fraction(
125:                     this.numerator,
126:                     this.denominator.multiply(new BigDecimal(x))
127:             );
128:         }
129:
130:         public String toString() {
131:
132:             /*
133:             If the denominator divides the numerator evenly,
134:             return a whole number.
135:              */
136:             if ((this.numerator.remainder(this.denominator)).equals(Zero)) {
137:                 return "" + this.numerator.divide(this.denominator);
138:
139:                 // Otherwise, display as a fraction.
140:             } else {
141:                 return this.numerator + "/" + this.denominator;
142:             }
143:         }
144:
145:         /*
146:         Reduces the fraction by dividing the numerator and denominator by
147:         their greatest common multiple.
148:          */
149:         private void reduce() {
150:             BigDecimal gcm = greatestCommonMultiple(this.numerator,
151:                     this.denominator);
152:             this.numerator = this.numerator.divide(gcm);
153:             this.denominator = this.denominator.divide(gcm);
154:         }
155:
156:         // Returns the greatest common multiple of two numbers.
157:         private BigDecimal greatestCommonMultiple(BigDecimal x, BigDecimal y) {
158:             if (y.equals(Zero)) {
159:                 return x;
160:             } else {
161:                 return greatestCommonMultiple(y, x.remainder(y));
162:             }
163:         }
164:     }
165: }

Notes:

The algorithm for solving this problem is very easy. Each round, the dragons steal 1/4 of the food available from each of their neighbors. The sum becomes their food for the start of the next round. The real difficulty lies in dealing with the fractions.

I used an inner class Fraction to encapsulate all of the work that needs to be done, including adding fractions, dividing, and printing them out in a canonical form. The tricky part here is that the numerators and denominators can get really big - like 61,572,651,155,457 / 17,592,186,044,416. After struggling with Longs that kept overflowing, I switched all the internals of the Fraction class over to BigDecimals.

Probably the most useful thing from the Fractions class is the greatestCommonMultiple() method. This is a good method to save since it comes up time and time again.

I believe lines 22 and 51 provide a good way for determining the neighbors on the cube. If you think of the cube as standard six-sided die , then the sum of any two opposite sides is 7. 1 is opposite 6, 2 is opposite 5, and 3 is opposite 4. Since the neighboring sides are any that are not yourself, or your opposite, we can use this array to skip any side / neighbor pairs where side == neighbor, or neighbors[side]+ neighbors[neighbor] == 7.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

Flags

Problem:

TopCoder Problem Statement - Flags

Overview:

Given a set of constraints, determine the minimum number of stripes needed to create flags using various colors.

Java Source:

001: /*
002: TopCoder
003: Single Round Match: 147
004: Division: 1
005: Level: 3
006: Points: 1000
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1206
008:  */
009:
010: import java.util.HashMap;
011: import java.util.HashSet;
012: import java.util.Map;
013: import java.util.Set;
014:
015: public class Flags {
016:
017:     /*
018:     Checks to see if there is at least one color that allows two neighbors.
019:      */
020:     private static boolean isLinearGrowth(Map> contributes) {
022:
023:         for (int color : contributes.keySet()) {
024:             if (contributes.get(color).size() > 1) {
025:                 return false;
026:             }
027:         }
028:
029:         return true;
030:     }
031:
032:     public long numStripes(String numFlags, String[] forbidden) {
033:
034:         int numColors = forbidden.length;
035:
036:         long numFlagsNeeded = Long.parseLong(numFlags);
037:
038:         /*
039:         Maps each ending stripe color with to a set of next stripe colors
040:          */
041:         Map> contributes = new HashMap<>();
042:
043:         for (int color = 0; color < numColors; color++) {
044:
045:             // Get the forbidden colors for this color and add them to a set.
046:             String[] forbiddenForColor = forbidden[color].split(" ");
047:             Set forbiddenForColorSet = new HashSet<>();
048:             for (String s : forbiddenForColor) {
049:                 forbiddenForColorSet.add(Integer.parseInt(s));
050:             }
051:
052:             /*
053:             Create a set that contains all the allowed colors.  That is,
054:             the colors not in the forbidden colors set.
055:              */
056:             Set availableForNextColor = new HashSet<>();
057:             for (int nextColor = 0; nextColor < numColors; nextColor++) {
058:                 if (!forbiddenForColorSet.contains(nextColor)) {
059:                     availableForNextColor.add(nextColor);
060:                 }
061:             }
062:
063:             // Store the color index along with its allowed next colors.
064:             contributes.put(color, availableForNextColor);
065:         }
066:
067:         /*
068:         Do we have at least one color that can have more than one neighbor.
069:         If not, then the number of flags grows linearly with the number of
070:         stripes and we'll do some division to figure out the anser.
071:          */
072:         if (isLinearGrowth(contributes)) {
073:             int divisor = 0;
074:             int subtract = 0;
075:             for (int color = 0; color < numColors; color++) {
076:                 if (contributes.get(color).size() == 0) { subtract++; }
077:                 if (contributes.get(color).size() == 1) { divisor++; }
078:             }
079:             if (divisor == 0) {
080:                 return -1;  // Impossible to make number of flags.
081:             }
082:             return (numFlagsNeeded / divisor) - (subtract / 2); // ??
083:         }
084:
085:         // A map to hold how many patterns end with each color.
086:         Map endsWithCount = new HashMap<>();
087:
088:         // Start of with flags ending in each of the colors
089:         for (int i = 0; i < numColors; i++) {
090:             endsWithCount.put(i, 1L);
091:         }
092:
093:         long numFlagsFound = numColors;
094:         long numStripes = 1;
095:
096:         /*
097:         Loop until we have the number of flags needed.  With each iterations,
098:          we look at the last color, and how many neighboring colors it will
099:          contribute to the next round.
100:          */
101:         while (numFlagsFound < numFlagsNeeded) {
102:             numStripes++;
103:
104:             /*
105:              Map holds the number of patterns that end with each color at the
106:              end of the round.  Starts each color at 0.
107:               */
108:             Map newEndsWithCount = new HashMap<>();
109:             for (int color = 0; color < numColors; color++) {
110:                 newEndsWithCount.put(color, 0L);
111:             }
112:
113:             /*
114:             For each color, look at how many neighbors it can have,
115:             then increments the number of flags ending with each neighboring
116:             color by the number of the current color elements.  For example,
117:             if the current round has 10 flags whose pattern ends with color
118:             0, and color 0 allows 1, 2, and 3; then in the next round,
119:             patterns ending in 1, 2, and 3 will appear 10 (more) times.
120:              */
121:             for (int color = 0; color < numColors; color++) {
122:                 for (int nextColor : contributes.get(color)) {
123:                     long toAdd = endsWithCount.get(color);
124:                     newEndsWithCount.put(nextColor, toAdd + newEndsWithCount
125:                             .get(nextColor));
126:                     numFlagsFound += toAdd;
127:
128:                     // Return as soon as possible.
129:                     if (numFlagsFound >= numFlagsNeeded) { return numStripes; }
130:                 }
131:             }
132:
133:             // Set current round to the next.
134:             endsWithCount = newEndsWithCount;
135:         }
136:
137:         return numStripes;
138:     }
139: }

Notes:

Start with N flags each with 1 stripe (solid colors). Then each time we add a stripe, we'll look at the current color, and for each possible neighboring color, we'll create a flag of that color. So, if we have three colors (0, 1, 2) and the only constraint is that the same color cannot be next to each other, then we'll get:

Stripes	Flags
1	0, 1, 2
2	01, 02, 10, 12, 20, 21
3	010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212
...	...

For each flag ending in 0, we create one ending in 01 and 02. Same goes for those ending in 1 and 2.

Line 41 creates a Map named "contributes", while lines 45-65 initialize it. Each key in the map is a color, and the value is a Set containing all the colors that may neighbor it. In each round, the ending color will contribute each of these colors to the next round.

On Line 86 a Map called endsWithCount is created. This holds a key for each color, and the value is the number of flags in that round that end with that color. When combined with the contributes map, we can see how many flags end with each color, and how many will end with each color in the next round.

What makes this problem difficult is the cases where all of the colors allow only one neighbor. Here, each additional stripe creates at most N additions flags, where N is the number of colors. The number of flags created grows linearly (instead of exponentially), and when some of the test cases expect 10 quadrillion flags, it could take a while. To handle this case, the check at line 72 is performed. If isLinearGrowth() returns true, then we abandon trying to determine the number of flags by iterating through each additional stripe, and instead use division to arrive at the answer.

Thank you for taking the time to read this solution. I welcome any feedback you may have.