452 /********************************************************************** 453 * Declare standard C '#include' header files 454 *********************************************************************/ 476 #include 532 #include 535 536 /********************************************************************** 537 * Define enum constants for some exit status values from this program 538 *********************************************************************/ 541 enum 542 { 544 ExitStatusSuccess = 0, 554 ExitStatusHelp = 1, 562 ExitStatusBadCmdArgs = 2, 569 ExitStatusBadInputData = 3 577 }; 580 581 /********************************************************************** 582 * Globals helpMsg1Format and helpMsg2Array[] for the help messages 583 *********************************************************************/ 591 const char *helpMsg1Format = 592 "USAGE #1: bloodtype1\n" 593 "USAGE #2: bloodtype1 < Blood1In.txt > Blood1Out.txt\n" 594 "\n" 595 "FOR HELP: bloodtype1 -h | more (prints %d lines)\n"; 604 const char *helpMsg2Array[] = 605 { 606 "", 607 "ARGUMENTS: No arguments are expected on the command line, but", 608 " text input and text output may be redirected.", 609 "", 610 "REVISION: 1.02 -- 02/19/2008 by Don Braun", 611 "", 612 "PURPOSE:", 613 "", 614 " This program bloodtype1 solves \"Problem A+, Consanguine", 615 " Calculations\" for the 2007 World Finals of the ACM", 616 " (Association for Computing Machinery) International Collegiate", 617 " Programming Contest. This is the first problem described in", 618 " the file at the Web address", 619 " http://" 620 "icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf", 621 " as follows.", 622 "", 623 " Every person's blood has 2 markers called ABO alleles. Each of", 624 " the markers is represented by one of three letters: A, B, or", 625 " O. This gives six possible combinations of these alleles that", 626 " a person can have, each of them resulting in a particular ABO", 627 " blood type for that person.", 628 "", 629 " Combination ABO Blood Type", 630 " ----------- --------------", 631 " AA A", 632 " AB AB", 633 " AO A", 634 " BB B", 635 " BO B", 636 " OO O", 637 "", 638 " Likewise, every person has two alleles for the blood Rh factor,", 639 " represented by the characters + and -. Someone who is", 640 " \"Rh positive\" or \"Rh+\" has at least one + allele, but", 641 " could have two. Someone who is \"Rh negative\" always has", 642 " two - alleles.", 643 "", 644 " The blood type of a person is a combination of ABO blood type", 645 " and Rh factor. The blood type is written by suffixing the", 646 " ABO blood type with the + or - representing the Rh factor.", 647 " Examples include A+, AB-, and O-.", 648 "", 649 " Blood types are inherited: each biological parent donates one", 650 " ABO allele (randomly chosen from their two) and one Rh factor", 651 " allele to their child. Therefore 2 ABO alleles and 2 Rh", 652 " factor alleles of the parents determine the child's blood", 653 " type. For example, if both parents of a child have blood type", 654 " A-, then the child could have either type A- or type O- blood.", 655 " A child of parents with blood types A+ and B+ could have any", 656 " blood type.", 657 "", 658 " In this problem, you will be given the blood type of either both", 659 " parents or one parent and a child; you will then determine", 660 " the (possibly empty) set of blood types that might", 661 " characterize the child or the other parent.", 662 "", 663 " Note: an uppercase letter \"Oh\" is used in this problem to", 664 " denote blood types, not a digit (zero).", 665 "", 666 " Input", 667 " -----", 668 "", 669 " The input consists of multiple test cases. Each test case is", 670 " on a single line in the format: the blood type of one parent,", 671 " the blood type of the other parent, and finally the blood type", 672 " of the child, except that the blood type of one parent or the", 673 " child will be replaced by a question mark. To improve", 674 " readability, whitespace may be included anywhere on the line", 675 " except inside a single blood type specification.", 676 "", 677 " The last test case is followed by a line containing the letters", 678 " E, N, and D separated by whitespace.", 679 "", 680 " Output", 681 " ------", 682 "", 683 " For each test case in the input, print the case number", 684 " (beginning with 1) and the blood type of the parents and the", 685 " child. If no blood type for a parent is possible, print", 686 " \"IMPOSSIBLE\". If multiple blood types for parents or child", 687 " are possible, print all possible values in a comma-separated", 688 " list enclosed in curly braces. The order of the blood types", 689 " inside the curly braces does not matter.", 690 "", 691 " The sample output illustrates multiple output formats. Your", 692 " output format should be similar.", 693 "", 694 " Sample Input Output for the Sample Input", 695 " ------------ ------------------------------------------", 696 " O+ O- ? Case 1: O+ O- {O+, O-}", 697 " O+ ? O- Case 2: O+ {A-, A+, B-, B+, O-, O+} O-", 698 " AB- AB+ ? Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB-}", 699 " AB+ ? O+ Case 4: AB+ IMPOSSIBLE O+", 700 " E N D", 701 NULL 702 }; 705 const int numLinesHelpMsg1 = 4; 707 const int numLinesHelpMsg2 = 708 sizeof(helpMsg2Array) / sizeof(char *) - 1; 712 713 /********************************************************************** 714 * #define; bloodTypeNames[]; 'typedef enum { TypAP, ... } BloodType' 715 *********************************************************************/ 727 #define DimInputLine 5120 735 #define DimAllelePairs 6 741 #define DimBloodTypes 8 750 #define DimBloodTypeStr 35 757 const char *bloodTypeNames[DimBloodTypes] = 758 { "A+", "A-", "B+", "B-", "O+", "O-", "AB+", "AB-" }; 771 typedef enum 772 { 773 TypAP = 0, 774 TypAN, 775 TypBP, 776 TypBN, 777 TypOP, 778 TypON, 779 TypABP, 780 TypABN, 781 TypUnknown 782 } BloodType; 785 786 /********************************************************************** 787 * Global array 'BloodType typeFrom2AllelePairs[6][6] = {{Typ...},...}' 788 *********************************************************************/ 801 /* Row: Column: */ 802 /* allele pair allele pair */ 803 /* from mom from dad */ 804 /* -------------- -------------- */ 805 BloodType typeFrom2AllelePairs[DimAllelePairs][DimAllelePairs] = 806 { 807 /* Allele Allele pair from dad */ 808 /* pair ============================================== */ 809 /* from mom A+ A- B+ B- O+ O- */ 810 /* -------- ------- ------- ------- ------- ------- ------ */ 811 /* A+ */ { TypAP, TypAP, TypABP, TypABP, TypAP, TypAP }, 812 /* A- */ { TypAP, TypAN, TypABP, TypABN, TypAP, TypAN }, 813 /* B+ */ { TypABP, TypABP, TypBP, TypBP, TypBP, TypBP }, 814 /* B- */ { TypABP, TypABN, TypBP, TypBN, TypBP, TypBN }, 815 /* O+ */ { TypAP, TypAP, TypBP, TypBP, TypOP, TypOP }, 816 /* O- */ { TypAP, TypAN, TypBP, TypBN, TypOP, TypON } 817 }; /* End of 'BloodType typeFrom2AllelePairs[][] =' */ 873 #define DimGenotypes 9 876 877 /********************************************************************** 878 * Global array 'BloodType allAllelePairs[DimGenotypes] = {Typ...,...}' 879 *********************************************************************/ 891 BloodType allAllelePairs[DimGenotypes] = 892 { TypAP, TypAN, TypBP, TypBN, TypOP, TypON, 893 TypUnknown, TypUnknown, TypUnknown }; 896 897 /********************************************************************** 898 * Function 'void fprintMsg()' 899 *********************************************************************/ 916 void fprintMsg( 918 FILE *pFileMsg, 923 const char * const *msgPtrArray) 930 { 932 while (*msgPtrArray) 933 fprintf(pFileMsg, "%s\n", *msgPtrArray++); 935 return; 937 } 940 941 /******************************************************************** 942 * Function 'int fgetline()' 943 ********************************************************************/ 992 int fgetline( 994 FILE *fp, 998 char str[], 1005 int lim) 1014 { 1016 int c = 'a'; 1017 int i = 0; 1019 while (--lim > 0 && (c=getc(fp)) != EOF && c != '\0' && 1020 c != '\n') 1021 str[i++] = (char) c; 1023 if (c == '\n') 1024 str[i++] = (char) c; 1025 else if (c != '\0' && c != EOF) 1026 while ((c=getc(fp)) != EOF && c != '\0' && c != '\n') 1027 ; 1029 if (lim >= 0) 1030 str[i] = (char) '\0'; 1031 return(i); 1033 } 1036 1037 /********************************************************************** 1038 * Function 'void getMomsAndDadsAllelePairsFromKidsType()' 1039 *********************************************************************/ 1063 void getMomsAndDadsAllelePairsFromKidsType( 1065 const BloodType kidsType, 1070 int *pNumAllelePairs, 1084 BloodType momsAllelePairs[DimGenotypes], 1085 BloodType dadsAllelePairs[DimGenotypes]) 1095 { 1101 int momsAllele; 1107 int dadsAllele; 1113 int numAllelePairs = 0; 1125 for (momsAllele = 0; momsAllele < DimAllelePairs; momsAllele++) 1126 for (dadsAllele = 0; dadsAllele < DimAllelePairs; dadsAllele++) 1127 { 1128 if (typeFrom2AllelePairs[momsAllele][dadsAllele] == kidsType) 1129 { 1130 momsAllelePairs[numAllelePairs] = (BloodType) momsAllele; 1131 dadsAllelePairs[numAllelePairs] = (BloodType) dadsAllele; 1132 numAllelePairs++; 1133 } 1134 } 1136 *pNumAllelePairs = numAllelePairs; 1137 return; 1139 } 1142 1143 /********************************************************************** 1144 * Function 'void sortUniqueTypes()' 1145 *********************************************************************/ 1199 void sortUniqueTypes( 1201 int *pNumTypes, 1211 BloodType typesArg[DimGenotypes]) 1224 { 1230 int iArg; 1234 int jCnt; 1240 int typesCount[DimBloodTypes + 1]; 1253 for (jCnt = 0; jCnt <= DimBloodTypes; jCnt++) 1254 typesCount[jCnt] = 0; 1262 for (iArg = 0; iArg < *pNumTypes; iArg++) 1263 typesCount[typesArg[iArg]]++; 1275 iArg = 0; 1277 for (jCnt = 0; jCnt <= DimBloodTypes; jCnt++) 1278 if (typesCount[jCnt] > 0) 1279 typesArg[iArg++] = (BloodType) jCnt; 1285 *pNumTypes = iArg; 1286 return; 1288 } 1291 1292 /********************************************************************** 1293 * Function 'void getTypesFromAnyAlleles1AndAnyAlleles2()' 1294 *********************************************************************/ 1322 void getTypesFromAnyAlleles1AndAnyAlleles2( 1325 const int numAlleles1, 1326 const BloodType allelePairs1[DimGenotypes], 1333 const int numAlleles2, 1334 const BloodType allelePairs2[DimGenotypes], 1341 int *pNumTypes, 1350 BloodType typesArg[DimGenotypes]) 1367 { 1373 int i1; 1377 int j2; 1381 int kArg; 1385 int mCnt; 1391 int typesCount[DimBloodTypes]; 1406 for (mCnt = 0; mCnt < DimBloodTypes; mCnt++) 1407 typesCount[mCnt] = 0; 1419 for (i1 = 0; i1 < numAlleles1; i1++) 1420 for (j2 = 0; j2 < numAlleles2; j2++) 1421 typesCount 1422 [ typeFrom2AllelePairs [allelePairs1[i1]] [allelePairs2[j2]] ]++; 1433 kArg = 0; 1435 for (mCnt = 0; mCnt < DimBloodTypes; mCnt++) 1436 if (typesCount[mCnt] > 0) 1437 typesArg[kArg++] = (BloodType) mCnt; 1443 *pNumTypes = kArg; 1444 return; 1446 } 1449 1450 /********************************************************************** 1451 * Function 'void keepMomDadAllelesOnlyIfMomsType()' 1452 *********************************************************************/ 1481 void keepMomDadAllelesOnlyIfMomsType( 1483 const BloodType momsType, 1489 int *pNumAlleles, 1501 BloodType momsAllelePairs[DimGenotypes], 1502 BloodType dadsAllelePairs[DimGenotypes]) 1537 { 1543 int iA; 1550 int jA; 1561 int kT; 1568 int isAlleleOK; 1588 for (iA = 0; iA < *pNumAlleles; iA++) 1589 { 1591 for (kT = 0; kT < DimAllelePairs; kT++) 1592 if (isAlleleOK = (typeFrom2AllelePairs[momsAllelePairs[iA]][kT] 1593 == momsType)) 1594 break; 1602 if (! isAlleleOK) 1603 { 1615 for (jA = iA + 1; jA < *pNumAlleles; jA++) 1616 { 1617 momsAllelePairs[jA - 1] = momsAllelePairs[jA]; 1618 dadsAllelePairs[jA - 1] = dadsAllelePairs[jA]; 1619 } 1626 (*pNumAlleles)--; 1635 iA--; 1637 } 1639 } 1641 return; 1643 } 1646 1647 /********************************************************************** 1648 * Function 'void keepDadMomAllelesOnlyIfDadsType()' 1649 *********************************************************************/ 1678 void keepDadMomAllelesOnlyIfDadsType( 1680 const BloodType dadsType, 1686 int *pNumAlleles, 1698 BloodType dadsAllelePairs[DimGenotypes], 1699 BloodType momsAllelePairs[DimGenotypes]) 1734 { 1748 keepMomDadAllelesOnlyIfMomsType(dadsType, pNumAlleles, 1749 dadsAllelePairs, momsAllelePairs); 1751 return; 1753 } 1756 1757 /********************************************************************** 1758 * Function 'BloodType getTypeEnumFromTypeStr()' 1759 *********************************************************************/ 1770 BloodType getTypeEnumFromTypeStr( 1772 const char *bloodTypeStr) 1778 { 1784 int typeInt; 1793 for (typeInt = 0; typeInt < DimBloodTypes; typeInt++) 1794 { 1795 if (strcmp(bloodTypeStr, bloodTypeNames[typeInt]) == 0) 1796 return (BloodType) typeInt; 1797 } 1799 return TypUnknown; 1801 } 1804 1805 /********************************************************************** 1806 * Function 'BloodType getStrFromTypeEnums()' 1807 *********************************************************************/ 1838 const char *getStrFromTypeEnums( 1840 const int numTypes, 1845 const BloodType typeEnums[DimGenotypes]) 1856 { 1862 static char typesStr[DimBloodTypeStr]; 1883 int iType; 1891 if (numTypes == 0) 1892 return "IMPOSSIBLE"; 1894 if (numTypes == 1) 1895 return bloodTypeNames[typeEnums[0]]; 1900 for (iType = 0; iType < numTypes; iType++) 1901 { 1902 if (iType == 0) 1903 strcpy(typesStr, "{"); 1904 else 1905 strcat(typesStr, ", "); 1907 strcat(typesStr, bloodTypeNames[typeEnums[iType]]); 1908 } 1910 strcat(typesStr, "}"); 1911 return typesStr; 1913 } 1916 1917 /********************************************************************** 1918 * Declarations for program main(...) 1919 *********************************************************************/ 1922 int main( 1924 int argc, 1926 char *argv[]) 1932 { 1938 char inpLin[DimInputLine]; 1951 int indexNewline; 1957 int exitStatus = ExitStatusSuccess; 1982 int numCase = 0; 1988 int numMomsAllelePairs; 1989 int numDadsAllelePairs; 1999 BloodType momsAllelePairs[DimGenotypes]; 2000 BloodType dadsAllelePairs[DimGenotypes]; 2011 BloodType lostAllelePairs[DimGenotypes]; 2019 int numMomsTypes; 2020 int numDadsTypes; 2021 int numKidsTypes; 2030 BloodType momsTypes[DimGenotypes]; 2031 BloodType dadsTypes[DimGenotypes]; 2032 BloodType kidsTypes[DimGenotypes]; 2043 char strMomsType[DimInputLine]; 2044 char strDadsType[DimInputLine]; 2045 char strKidsType[DimInputLine]; 2084 2085 /********************************************************************** 2086 * main(): Begin execution by printing a help message if necessary 2087 *********************************************************************/ 2095 if (argc != 1) 2096 { 2102 printf(helpMsg1Format, numLinesHelpMsg1 + numLinesHelpMsg2); 2108 if (argc == 2 && strcmp(argv[1], "-h") == 0) 2109 { 2110 fprintMsg(stdout, helpMsg2Array); 2111 return ExitStatusHelp; 2112 } 2118 return ExitStatusBadCmdArgs; 2120 } 2123 2124 /********************************************************************** 2125 * main(): Begin 'while (1)' loop; read and parse the next input line 2126 *********************************************************************/ 2142 while (1) 2143 { 2150 numCase++; 2151 indexNewline = fgetline(stdin, inpLin, DimInputLine) - 1; 2160 if (indexNewline == -1 || inpLin[indexNewline] != '\n') 2161 { 2162 printf("Case %d: *** ERROR: The input line was bad, so " 2163 "terminate this program.\n", 2164 numCase); 2165 return ExitStatusBadInputData; 2166 } 2173 inpLin[indexNewline] = '\0'; 2181 if (sscanf(inpLin, "%s%s%s", strMomsType, strDadsType, strKidsType) 2182 != 3) 2183 { 2188 printf("Case %d: *** ERROR: 3 fields are not on input line " 2189 "\"%s\".\n", 2190 numCase, inpLin); 2194 continue; 2195 } 2206 if (strcmp(strMomsType, "E") == 0 && 2207 strcmp(strDadsType, "N") == 0 && 2208 strcmp(strKidsType, "D") == 0) 2209 return exitStatus; 2212 2213 /********************************************************************** 2214 * main(): Find mom's allowed blood types if 1st input field was "?" 2215 *********************************************************************/ 2229 if (strcmp(strMomsType, "?") == 0) 2230 { 2239 if ((dadsTypes[0] = getTypeEnumFromTypeStr(strDadsType)) == 2240 TypUnknown) 2241 { 2248 printf("Case %d: *** ERROR: Dad's (2nd) input blood type " 2249 "\"%s\" is bad.\n", 2250 numCase, strDadsType); 2251 exitStatus = ExitStatusBadInputData; 2252 continue; 2253 } 2262 if ((kidsTypes[0] = getTypeEnumFromTypeStr(strKidsType)) == 2263 TypUnknown) 2264 { 2271 printf("Case %d: *** ERROR: Kid's (3rd) input blood type " 2272 "\"%s\" is bad.\n", 2273 numCase, strKidsType); 2274 exitStatus = ExitStatusBadInputData; 2275 continue; 2276 } 2286 getMomsAndDadsAllelePairsFromKidsType(kidsTypes[0], 2287 &numDadsAllelePairs, momsAllelePairs, dadsAllelePairs); 2308 keepDadMomAllelesOnlyIfDadsType(dadsTypes[0], 2309 &numDadsAllelePairs, dadsAllelePairs, momsAllelePairs); 2311 numMomsAllelePairs = numDadsAllelePairs; 2329 getTypesFromAnyAlleles1AndAnyAlleles2( 2330 numMomsAllelePairs, momsAllelePairs, 2331 DimAllelePairs, allAllelePairs, 2332 &numMomsTypes, momsTypes); 2337 printf("Case %d: %s %s %s\n", 2338 numCase, 2339 getStrFromTypeEnums(numMomsTypes, momsTypes), 2340 strDadsType, 2341 strKidsType); 2346 continue; 2348 } 2351 2352 /********************************************************************** 2353 * main(): Find dad's allowed blood types if 2nd input field was "?" 2354 *********************************************************************/ 2368 if (strcmp(strDadsType, "?") == 0) 2369 { 2378 if ((momsTypes[0] = getTypeEnumFromTypeStr(strMomsType)) == 2379 TypUnknown) 2380 { 2387 printf("Case %d: *** ERROR: Mom's (1st) input blood type " 2388 "\"%s\" is bad.\n", 2389 numCase, strMomsType); 2390 exitStatus = ExitStatusBadInputData; 2391 continue; 2392 } 2401 if ((kidsTypes[0] = getTypeEnumFromTypeStr(strKidsType)) == 2402 TypUnknown) 2403 { 2410 printf("Case %d: *** ERROR: Kid's (3rd) input blood type " 2411 "\"%s\" is bad.\n", 2412 numCase, strKidsType); 2413 exitStatus = ExitStatusBadInputData; 2414 continue; 2415 } 2425 getMomsAndDadsAllelePairsFromKidsType(kidsTypes[0], 2426 &numMomsAllelePairs, momsAllelePairs, dadsAllelePairs); 2447 keepMomDadAllelesOnlyIfMomsType(momsTypes[0], 2448 &numMomsAllelePairs, momsAllelePairs, dadsAllelePairs); 2450 numDadsAllelePairs = numMomsAllelePairs; 2468 getTypesFromAnyAlleles1AndAnyAlleles2( 2469 numDadsAllelePairs, dadsAllelePairs, 2470 DimAllelePairs, allAllelePairs, 2471 &numDadsTypes, dadsTypes); 2476 printf("Case %d: %s %s %s\n", 2477 numCase, 2478 strMomsType, 2479 getStrFromTypeEnums(numDadsTypes, dadsTypes), 2480 strKidsType); 2485 continue; 2487 } 2490 2491 /********************************************************************** 2492 * main(): Find kid's allowed blood types if 3rd input field was "?" 2493 *********************************************************************/ 2507 if (strcmp(strKidsType, "?") == 0) 2508 { 2517 if ((momsTypes[0] = getTypeEnumFromTypeStr(strMomsType)) == 2518 TypUnknown) 2519 { 2526 printf("Case %d: *** ERROR: Mom's (1st) input blood type " 2527 "\"%s\" is bad.\n", 2528 numCase, strMomsType); 2529 exitStatus = ExitStatusBadInputData; 2530 continue; 2531 } 2540 if ((dadsTypes[0] = getTypeEnumFromTypeStr(strDadsType)) == 2541 TypUnknown) 2542 { 2549 printf("Case %d: *** ERROR: Dad's (2nd) input blood type " 2550 "\"%s\" is bad.\n", 2551 numCase, strDadsType); 2552 exitStatus = ExitStatusBadInputData; 2553 continue; 2554 } 2572 getMomsAndDadsAllelePairsFromKidsType(momsTypes[0], 2573 &numMomsAllelePairs, momsAllelePairs, lostAllelePairs); 2591 getMomsAndDadsAllelePairsFromKidsType(dadsTypes[0], 2592 &numDadsAllelePairs, dadsAllelePairs, lostAllelePairs); 2602 sortUniqueTypes(&numMomsAllelePairs, momsAllelePairs); 2603 sortUniqueTypes(&numDadsAllelePairs, dadsAllelePairs); 2622 getTypesFromAnyAlleles1AndAnyAlleles2( 2623 numMomsAllelePairs, momsAllelePairs, 2624 numDadsAllelePairs, dadsAllelePairs, 2625 &numKidsTypes, kidsTypes); 2631 printf("Case %d: %s %s %s\n", 2632 numCase, 2633 strMomsType, 2634 strDadsType, 2635 getStrFromTypeEnums(numKidsTypes, kidsTypes)); 2640 continue; 2642 } 2645 2646 /********************************************************************** 2647 * main(): End of loop 'while (1)'; end of function 'int main()' 2648 *********************************************************************/ 2651 printf("Case %d: *** ERROR: Missing \"?\" in 3 args of input line " 2652 "\"%s\"\n", 2653 numCase, 2654 inpLin); 2656 } /* End of the loop 'while (1)' */ 2658 } /* End of 'int main()' */