/********************************** ** File: bluegene.c ** ** Programmer: Marc Douet ** ** Date: 06/20/02 ** **********************************/ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <malloc.h> #include <string.h> #define MIN_STRAND_LENGTH 1 /* Min length of a virus strand. */ #define MAX_STRAND_LENGTH 20 /* Max length of a virus strand. */ #define TRUE 1 /* Macro for boolean true. */ #define FALSE 0 /* Macro for boolean false. */ /********************** ** Global Variables ** **********************/ char *virusStrand; /* String to hold elements of a virus strand. */ int endOfStrand; /* The last position of the virus strand. */ char *tag; /* String to hold the START/END tag. */ int ERROR_OCCURRED = FALSE; /* Flag to tell when an error occurrs. */ /*************************************************************************** * Function: ctoi * * Synopsis: int ctoi(char character) * * character [IN] Character to be converted * * Description: Converts a character to its integer equivalent. * * Return Value: Integer equivalent of the character. ***************************************************************************/ int ctoi(char character) { return character - 48; } /*************************************************************************** * Function: itoc * * Synopsis: char itoc(int number) * * number [IN] Integer to be converted * * Description: Converts an integer to its character equvalent. * * Return Value: Character equivalent of the integer. ***************************************************************************/ char itoc(int number) { return number + 48; } /*************************************************************************** * Function: HandleError * * Synopsis: void HandleError(void) * * Description: Called whenever an error occurs in the main logic to free * up any allocated memory, and exit with 1. * * Return Value: None. ***************************************************************************/ void HandleError() { /* If memory is allocated for the START/END tag, free it. */ if(tag != NULL) free(tag); /* If memory is allocated for the virus strand, free it. */ if(virusStrand != NULL) free(virusStrand); /* There's no turning back now, so let's exit 1. */ exit(1); } /*************************************************************************** * Function: ReadStrand * * Synopsis: int ReadStrand(void) * * Description: Allocates enough memory for the virus strand, reads the * virus strand into the array from input, and ensures that * the virus strand array is the right size and that the * data is valid (uppercase or digit). * * Return Value: Returns 1 on success, and 0 if errors occur. ***************************************************************************/ int ReadStrand() { int strandSize = ((endOfStrand+1)*sizeof(char));/* Size of the virus strand. */ int index; /* Index into strand string. */ /* Try to allocate memory for the virus strand using the data size. */ if((virusStrand = (char*)malloc(strandSize)) == NULL) { printf("Error: Unable to malloc %d bytes for virus strand.\n", strandSize); return 0; } /* Read the virus strand into the string. */ scanf("%s", virusStrand); /* Ensure that the string is the right size. */ if(strlen(virusStrand) != endOfStrand) { printf("Error: %d elements expected, %d elements found.\n", strandSize-1, strlen(virusStrand)); return 0; } /* Ensure that the data is valid. */ for(index = 0; index < endOfStrand; index++) if(!isupper(virusStrand[index]) && !isdigit(virusStrand[index])) { printf("Error: %c must be uppercase or a digit.\n", virusStrand[index]); return 0; } /* If we got here, everything is ok. */ return 1; } /*************************************************************************** * Function: FindSubStrand * * Synopsis: int FindSubStrand(int currentPosition) * * currentPosition [IN] Current position of the element in * the virus strand we are looking at. * * Description: Find the start of the next sub-strand by using the * following criterion: * 1. IF it is an uppercase letter, return the current * postion + one. * 2. If it is the number 0, return -1 since it is * a stable sub-strand. * 3. If it is a non-zero digit, return the digit's * value + the current position IF that value is * <= to the end position of the virus strand, ELSE * return the current position + 1. * 4. If none of the above is true, then something * is really wrong with the input, so print out * an error message, set the error flag, and return * end postition + 1 so the error can be detected. * * Return Value: Returns the start position of the next sub-strand, or -1 * if it is stable, or the end postion + 1 if an error has * occurred. * * Assumptions: It is assumed that the end position will never be passed * into this function, since the base case will catch it. ***************************************************************************/ int FindSubStrand(int currentPosition) { int num; /* Integer to hold character to integer conversions. */ /* If the current position is not valid, throw an error and return. */ if(currentPosition < 0 || currentPosition > endOfStrand) { printf("Error: %i is not a valid virus strand position.\n", currentPosition); ERROR_OCCURRED = TRUE; return (endOfStrand + 1); } /* IF it is an uppercase letter, return the current position + 1. */ if(isupper(virusStrand[currentPosition])) return (currentPosition + 1); /* If it is a digit... */ else if(isdigit(virusStrand[currentPosition])) { /* IF the digit value is stable (0), return -1. */ if( virusStrand[currentPosition] == '0') return -1; /* IF the digit's value + the current position is <= the */ /* end position, return that value. */ else if((num = ctoi(virusStrand[currentPosition]) + currentPosition) <= endOfStrand) return num; /* ELSE return the current position + 1. */ else return (currentPosition + 1); } /* ELSE it is not valid input. Shouldn't get here, but we may have * * overwritten the virus strand string with some corrupted data. */ else { printf("Error: %c is not a valid virus strand element.\n", virusStrand[currentPosition]); ERROR_OCCURRED = TRUE; return (endOfStrand + 1); } } /*************************************************************************** * Function: MutateElement * * Synopsis: int MutateElement(int mutatePosition, int numMutations) * * mutatePosition [IN] Position of the element in the * virus strand to mutate. * numMutations [IN] The number of mutations that have * occurred thus far (used to mutate letters). * * Description: Mutate the element by using the following criterion: * 1. IF it is an uppercase letter, mutate it to * the number of total mutations thus far IF * it is NOT the last letter in the strand. * ELSE mutate it to 0 (it becomes stable). * Then increment the number of total mutations, * and return that number. * 2. If it is the number 0, do nothing since it * is stable, and return the current number of * mutations. * 3. If it is a non-zero digit, mutate it by * decrementing it by one, increment the total * number of mutations, and return that number. * 4. If none of the above is true, then something * is really wrong with the input, so print out * an error message, set the error flag, and * return the current number of mutations. * * Return Value: Returns the number of mutations thus far. ***************************************************************************/ int MutateElement(int mutatePosition, int numMutations) { int num; /* Integer for character and integer conversions. */ /* If the mutate position is not valid throw an error and return. */ if(mutatePosition < 0 || mutatePosition > endOfStrand) { printf("Error: %i is not a valid virus strand position!\n", mutatePosition); ERROR_OCCURRED = TRUE; return numMutations; } /* IF it is an uppercase letter... */ if(isupper(virusStrand[mutatePosition])) { /* IF we are at the last element in the strand, mutate it to stable. */ if(mutatePosition == endOfStrand) virusStrand[mutatePosition] = '0'; /* Else mutate it to the number of mutations so far. */ else { /* IF there are more than 9 mutations, mutate to (mutations % 10). */ if(numMutations > 9) num = numMutations % 10; /* ELSE mutate to the number of mutations. */ else num = numMutations; virusStrand[mutatePosition] = itoc(num); } return numMutations + 1; } /* If it is a digit... */ else if(isdigit(virusStrand[mutatePosition])) { /* If it is the number 0, do nothing since it is stable */ if( virusStrand[mutatePosition] == '0') return numMutations; /* ELSE mutate it to the digit value - 1. */ else { num = ctoi(virusStrand[mutatePosition]); virusStrand[mutatePosition] = itoc(num-1); return numMutations + 1; } } /* ELSE it is not valid input. Shouldn't get here, but we may have * * overwritten the virus strand string with some corrupted data. */ else { printf("Error: %c is not a valid virus strand element!\n", virusStrand[mutatePosition]); ERROR_OCCURRED = TRUE; return numMutations; } } /*************************************************************************** * Function: MutateStrand * * Synopsis: int MutateStrand(int startOfStrand) * * startOfStrand [IN] Position of the first element * in the strand we are mutating. * * Description: Mutates the virus strand starting at the passed-in * start position by recursively calling itself to * mutate each of its corresponding sub-strands. * * Return Value: Returns an integer which represents the total number * of mutations thus far. Returns a -1 if an error is * encountered, and a 0 if a stable element was found. ***************************************************************************/ int MutateStrand(int startOfStrand) { int nextStartOfStrand; /* Start of the next sub-strand. */ /* Error Case - Somewhere an error has occurred, so let's return -1. */ if(ERROR_OCCURRED) return -1; /* Base Case - The end of the strand is reached, so mutate, * * passing in 0 since no mutations should have * * occurred before now, and return. */ if(startOfStrand == endOfStrand) return MutateElement(startOfStrand, 0); /* Look up the start of the next sub-strand. */ nextStartOfStrand = FindSubStrand(startOfStrand); /* Trap for errors occurring if an invalid next start position was found. * * Doesn't trap for less than 0 because that is our stable strand case. */ if(nextStartOfStrand > endOfStrand) { ERROR_OCCURRED = TRUE; return -1; } /* If we found a stable element, return 0 to stop any further mutations. */ if(nextStartOfStrand < 0) return 0; /* Mutate the sub-strand, returning the number of total mutations. */ return MutateElement(startOfStrand, MutateStrand(nextStartOfStrand)); } /*************************************************************************** * Function: main * * Synopsis: main(void) * * Description: Main driver of the program. Consists of a loop that * through each iteration: * 1. Reads in a virus strand. * 2. Uses the virus strand to populate the global * virus strand string. * 3. Calls MutateStrand() with 0, to recursively mutate * the virus strand starting a the first element. * 4. Prints out the final mutated virus strand. * 5. If another "START" string exists, continue. * 6. If another "START" string does not exist, * break out of the loop and exit. * * Return Value: Exit 0 if success, exit 1 if error was encountered. ***************************************************************************/ main() { /* Try to allocate memory to hold the START/END * * tag using the size of the bigger tag (START). */ if((tag = (char*)malloc(sizeof("START"))) == NULL) { printf("Error: Unable to malloc %d bytes for START/END tag.\n", sizeof("START")); HandleError(); } /* Read in the START tag and element count. */ scanf("%s %d", tag, &endOfStrand); /* WHILE we have found a START tag... */ while(!strcmp(tag, "START")) { /* IF the element count is invalid, print an error message and exit 1. */ if(endOfStrand < MIN_STRAND_LENGTH || endOfStrand > MAX_STRAND_LENGTH) { printf("Error: %d is not a valid virus strand length.\n", endOfStrand); HandleError(); } /* Try to read in the virus strand from input. */ if(!ReadStrand()) { HandleError(); } /* Decrement to represent the last position in the strand array. */ endOfStrand--; /* Clear out the START/END tag to read in the END tag. */ memset((void *)tag, '\0', sizeof(tag)); /* Read in the END tag. */ scanf("%s", tag); /* IF an END tag was not found, print an error, and exit 1. */ if(strcmp(tag, "END")) { printf("Error: No END tag was found after the data.\n"); HandleError(); } /* Mutate the virus strand, starting with the first element. */ MutateStrand(0); /* IF an error has occurred, exit 1. */ if(ERROR_OCCURRED) HandleError(); /* Print out the final mutated strand. */ printf("%s\n", virusStrand); /* Free the virus strand array. */ free(virusStrand); /* Clear the START/END tag and reset the element count. */ memset((void *)tag, '\0', sizeof(tag)); endOfStrand = 0; /* Try to read in another tag and element count. */ scanf("%s %d", tag, &endOfStrand); } /* We're done, so let's free up all allocated memory and exit with 0. * * Note that the virus strand should have already been freed by now. */ if(tag != NULL) free(tag); exit(0); }