|
import java.util.ArrayList; |
|
import java.util.Arrays; |
|
import java.util.HashMap; |
|
import java.util.List; |
|
import java.util.Map; |
|
|
|
import static java.util.Collections.singletonList; |
|
import static java.util.Collections.unmodifiableList; |
|
import static java.util.Collections.unmodifiableMap; |
|
|
|
/** |
|
* <p><b>Goal</b></p> |
|
* You have to list all the gene combinations of two parents, from their blood type and |
|
* the blood type of one of their children. |
|
* <p><b>Description</b></p> |
|
* Each person has two <b>blood genes</b>, each of them can be <mark>A</mark>, <mark>B</mark> or <mark>O</mark>. |
|
* <p> |
|
* You do not directly know which person has which genes, but you know their <b>phenotypes</b> |
|
* (the apparent expression of the genes). The phenotype can be: A, B, AB or O. |
|
* <p> |
|
* Here are the correspondences between blood genes and phenotype: |
|
* <ul> |
|
* <li>When the two genes of a person are both "A", the phenotype is "A".</li> |
|
* <li>When the genes are both "B", the phenotype is "B".</li> |
|
* <li>When the genes are both "O", the phenotype is "O".</li> |
|
* <li>When one gene is "A" and the other is "B", the phenotype is "AB".</li> |
|
* <li>When one gene is "A" and the other is "O", the phenotype is "A".</li> |
|
* <li>When one gene is "B" and the other is "O", the phenotype is "B".</li> |
|
* </ul> |
|
* <table border="1"> |
|
* <tr> |
|
* <td colspan="2"></td> |
|
* <td colspan="3">blood gene 1</td> |
|
* </tr> |
|
* <tr> |
|
* <td></td> |
|
* <td></td> |
|
* <td>A</td> |
|
* <td>B</td> |
|
* <td>O</td> |
|
* </tr> |
|
* <tr> |
|
* <td rowspan="3">blood gene 2</td> |
|
* <td>A</td> |
|
* <td>A</td> |
|
* <td>AB</td> |
|
* <td>A</td> |
|
* </tr> |
|
* <tr> |
|
* <td>B</td> |
|
* <td>AB</td> |
|
* <td>B</td> |
|
* <td>B</td> |
|
* </tr> |
|
* <tr> |
|
* <td>O</td> |
|
* <td>A</td> |
|
* <td>B</td> |
|
* <td>O</td> |
|
* </tr> |
|
* <tr> |
|
* <td></td> |
|
* <td></td> |
|
* <td colspan="3">Phenotype</td> |
|
* </tr> |
|
* </table> |
|
* A child gets one of the blood genes from their first parent, and the other one from |
|
* their second parent. The genes are randomly chosen. |
|
* <p> |
|
* You are given the phenotypes of three persons: first parent, second parent, and one |
|
* of their children. |
|
* <p> |
|
* Output a list, containing all the possible blood gene combinations of the parents. |
|
* Each element of the list is a sub-list of two strings, containing the blood genes of |
|
* the first and second parent, in that order. |
|
* <p> |
|
* When there is no possible combination, output a list containing only one element: a sub-list |
|
* of two strings, both equal to <mark>--</mark> (two hyphens). |
|
* <p> |
|
* Since the order of genes is not important inside one person, you do not have to describe |
|
* "BO or OB". So, each string will always have one of the following values: |
|
* AA, BB, AB, AO, BO, OO, --. |
|
* <p> |
|
* <b>The elements in the main list must be alphabetically sorted by the first parent genes, |
|
* then by the second parent genes.</b> |
|
* <p> |
|
* <b>Example 1</b> |
|
* <p>You get these values in input:</p> |
|
* <code> |
|
* parent_1 = "AB"<br/> |
|
* parent_2 = "A"<br/> |
|
* child = "A"<br/> |
|
* </code> |
|
* <ul> |
|
* <li>The phenotype of the first parent is "AB", so the blood genes are "AB" (only one possible value).</li> |
|
* <li>The phenotype of the second parent is "A". so the blood genes can be "AA" or "AO"</li> |
|
* </ul> |
|
* The first parent combination is ["AB", "AA"]. Each of the parents can give a blood |
|
* gene "A" to the child. The child would have the phenotype "A". It is possible. |
|
* <p> |
|
* The second parent combination is ["AB", "AO"]. The first parent can give the blood |
|
* gene "A", the second one can give any of the blood genes. The child would have the |
|
* blood genes "AA" or "AO", in both cases it results in the phenotype "A". It is possible. |
|
* <p> |
|
* You have to output the following value : [["AB", "AA"], ["AB", "AO"]] |
|
* <p> |
|
* <b>Example 2</b> |
|
* <p>You get these values in input:</p> |
|
* <code> |
|
* parent_1 = "O"<br/> |
|
* parent_2 = "AB"<br/> |
|
* child = "O"<br/> |
|
* </code> |
|
* <ul> |
|
* <li>The phenotype of the first parent is "O", so tbe blood genes are "OO" (only one possible value).</li> |
|
* <li>The phenotype of the second parent is "AB", so the blood genes are "AB" (only one possible value).</li> |
|
* </ul> |
|
* The first parent always gives a blood gene "O" to the child, the second one gives |
|
* either an "A" or a "B". |
|
* <p> |
|
* In the first case, the blood genes of the child would be "AO", which results in the |
|
* phenotype "A". In the second case, the blood genes would be "BO", which results in |
|
* the phenotype "B". |
|
* <p> |
|
* But the child has the phenotype "O". So it is impossible. |
|
* <p> |
|
* You have to output the following value: [["--", "--"]] |
|
*/ |
|
public class GeneCombinations { |
|
private static Map<String, String> phenotypes = new HashMap<>(); |
|
private static Map<String, List<String>> genesByPhenotype = new HashMap<>(); |
|
private static final List<String> EMPTY_GENE = unmodifiableList(Arrays.asList("--", "--")); |
|
|
|
static { |
|
phenotypes.put("AA", "A"); |
|
phenotypes.put("AO", "A"); |
|
phenotypes.put("BB", "B"); |
|
phenotypes.put("BO", "B"); |
|
phenotypes.put("AB", "AB"); |
|
phenotypes.put("OO", "O"); |
|
|
|
genesByPhenotype.put("A", Arrays.asList("AA", "AO")); |
|
genesByPhenotype.put("B", Arrays.asList("BB", "BO")); |
|
genesByPhenotype.put("AB", singletonList("AB")); |
|
genesByPhenotype.put("O", singletonList("OO")); |
|
|
|
genesByPhenotype = unmodifiableMap(genesByPhenotype); |
|
phenotypes = unmodifiableMap(phenotypes); |
|
} |
|
|
|
/** |
|
* @param parent1 The phenotype of the first parent (A, B, AB or O) |
|
* @param parent2 The phenotype of the second parent (A, B, AB or O) |
|
* @param child The phenotype of the child (A, B, AB or O) |
|
* @return A list of string, containing all the possible blood genes of the two parents. |
|
*/ |
|
public static List<List<String>> computeBloodGenes(String parent1, String parent2, String child) { |
|
List<List<String>> results = new ArrayList<>(); |
|
|
|
// Calculate combinations |
|
List<String> parent1Phenotypes = genesByPhenotype.get(parent1); |
|
List<String> parent2Phenotypes = genesByPhenotype.get(parent2); |
|
build_combinations: |
|
for (String parent1Phenotype : parent1Phenotypes) { |
|
for (String parent2Phenotype : parent2Phenotypes) { |
|
// Check combinations with the child |
|
boolean goodGene = false; |
|
|
|
check_combinations: |
|
for (int idx = 0; idx < parent1Phenotype.length(); idx++) { |
|
for (int jdx = 0; jdx < parent2Phenotype.length(); jdx++) { |
|
char[] genes = {parent1Phenotype.charAt(idx), parent2Phenotype.charAt(jdx)}; |
|
Arrays.sort(genes); |
|
|
|
if (phenotypes.get(new String(genes)).equals(child)) { |
|
goodGene = true; |
|
break check_combinations; |
|
} |
|
} |
|
} |
|
if (!goodGene) { |
|
results.clear(); |
|
break build_combinations; |
|
} |
|
|
|
// Add the combinations |
|
results.add(Arrays.asList(parent1Phenotype, parent2Phenotype)); |
|
} |
|
} |
|
|
|
if (results.isEmpty()) { |
|
results.add(EMPTY_GENE); |
|
} |
|
return results; |
|
} |
|
|
|
public static void main(String[] args) { |
|
System.out.println("(AB, A, A) = " + computeBloodGenes("AB", "A", "A")); |
|
System.out.println("(O, AB, O) = " + computeBloodGenes("O", "AB", "O")); |
|
} |
|
} |
