TopCoder Problem Statement - PaternityTest
Determine possible fathers given a DNA sequence from a child, mother, and array of potential fatehrs.
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: ListpossibleList = 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: }
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.