452 /**********************************************************************
453 * Declare standard C '#include' header files
454 *********************************************************************/
476 #include <stdio.h>
532 #include <string.h>
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()' */