/////////////////////////////////// // File: ManifestDestiny.c // // Programmer: Marc Douet // // Date: 08/09/01 // /////////////////////////////////// #include #include #include #include #define MAXDIM 20 //The maximum map dimension // Object that represents a position on a matrix: struct Coordinate { int x; int y; }; // Object that stores the state of a Tribe: struct Tribe { char name; //Name of the Tribe int population; //Number of people in the Tribe int strength; //Number of people the Tribe can kill Coordinate currentPos; //The current position of the Tribe on the map int visitedArray[MAXDIM][MAXDIM]; //The decision values of all positions on the map Coordinate lastVisitedPos; //The position of the spot last visited by the tribe bool isDead; //Tells whether the Tribe is dead or alive int roundKilled; //The round the tribe was killed (0 if Tribe is alive) }; /////////////////////////////////////////////////////////// // Search the next character in the input for a newline: // /////////////////////////////////////////////////////////// bool foundEOL() { char token; int position = cin.tellg(); cin.get(token); while(token == ' ') cin.get(token); cin.seekg(position); if(token == '\n') return true; else return false; } //////////////////////////////////////////////////////////// // Search the next string in the input for a 'END' label: // //////////////////////////////////////////////////////////// bool foundEND() { char endString[4] = "\0"; int position = cin.tellg(); cin >> endString; if(!strcmp(endString, "END")) return true; else { cin.seekg(position); return false; } } ////////////////////////////////////////////////////////////////// // Populate the tribes using the descriptor and value matrices: // ////////////////////////////////////////////////////////////////// void populateTribes(Tribe tribe[10], char descriptorArray[MAXDIM][MAXDIM], int valueArray[MAXDIM][MAXDIM], int numRows, int numCols) { // Mark all tribes as dead: for(int index = 0; index < 10; index ++) { tribe[index].isDead = true; tribe[index].roundKilled = -1; } // Find live tribes and populate them: for(int row = 0; row < numRows; row ++) { for(int col = 0; col < numCols; col ++) { // See if we found a tribe descriptor: if(isdigit(descriptorArray[row][col])) { // Convert the tribe name into an index: int tribeIndex = descriptorArray[row][col] - '0'; // Build the tribe, indexed with the tribe's name: tribe[tribeIndex].name = descriptorArray[row][col]; tribe[tribeIndex].population = valueArray[row][col]; tribe[tribeIndex].strength = int(ceil(valueArray[row][col] / 2.0)); tribe[tribeIndex].currentPos.x = col; tribe[tribeIndex].currentPos.y = row; tribe[tribeIndex].lastVisitedPos.x = -1; tribe[tribeIndex].lastVisitedPos.y = -1; tribe[tribeIndex].isDead = false; tribe[tribeIndex].roundKilled = 0; // Intialize the visitedArray of the tribe: for(int tempRow = 0; tempRow < numRows; tempRow ++) for(int tempCol = 0; tempCol < numCols; tempCol ++) tribe[tribeIndex].visitedArray[tempRow][tempCol] = 0; } } } } ////////////////////////////////////////////////////////////// // Attack the chosen tribe, doing damage to the tribe and // // adjusting the attacking tribe's population and strength: // ////////////////////////////////////////////////////////////// void attackTribe(Tribe tribe[10], char descriptorArray[MAXDIM][MAXDIM], int tribeIndex, int enemyIndex, int round) { // Do damage to enemy equal to attacking tribe's strength: tribe[enemyIndex].population -= tribe[tribeIndex].strength; // Recalculate population of the attacking tribe for 10% fighting damage: int numDeadFighters = int(ceil(tribe[tribeIndex].population / 10.0)); tribe[tribeIndex].population -= numDeadFighters; // Adjust the attacking tribe's strength: tribe[tribeIndex].strength = int(ceil(tribe[tribeIndex].population / 2.0)); // If enemy has been killed, take them off the map, and mark them dead: if(tribe[enemyIndex].population <= 0) { int enemyRow = tribe[enemyIndex].currentPos.y; int enemyCol = tribe[enemyIndex].currentPos.x; descriptorArray[enemyRow][enemyCol] = '.'; tribe[enemyIndex].isDead = true; tribe[enemyIndex].population = 0; tribe[enemyIndex].roundKilled = round; } // Else, the enemy is still alive, so adjust the enemy tribe's strength: else tribe[enemyIndex].strength = int(ceil(tribe[enemyIndex].population / 2.0)); } ////////////////////////////////////////////////////////////////////////////////// // If there is a tribe to fight, fight them and return true, else return false: // ////////////////////////////////////////////////////////////////////////////////// bool tribeFight(Tribe tribe[10], int tribeIndex, char descriptorArray[MAXDIM][MAXDIM], int numRows, int numCols, int currentRound) { //Get the attacker's position: int col = tribe[tribeIndex].currentPos.x; int row = tribe[tribeIndex].currentPos.y; //Search for a tribe to fight from the North: if(isdigit(descriptorArray[row-1][col])) row = row-1; //Search for a tribe to fight from the East: else if(isdigit(descriptorArray[row][col+1])) col = col+1; //Search for a tribe to fight from the South: else if(isdigit(descriptorArray[row+1][col])) row = row+1; //Search for a tribe to fight from the West: else if(isdigit(descriptorArray[row][col-1])) col = col-1; //Else, didn't find a tribe to fight, so return FALSE: else return false; // Convert the enemy name into an index: int enemyIndex = descriptorArray[row][col] - '0'; // Attack the chosen enemey tribe and return TRUE: attackTribe(tribe, descriptorArray, tribeIndex, enemyIndex, currentRound); return true; } ////////////////////////////////////////////////////////////////////////////// // Consume the food, reduce the food count, and return the number of people // // who were not able to eat because of a deficiency in food: // ////////////////////////////////////////////////////////////////////////////// int consumeFood(char descriptorArray[MAXDIM][MAXDIM], int valueArray[MAXDIM][MAXDIM], int hungryPeople, int row, int col) { //Used to store a copy of humgryPeople: int tempHungryPeople = 0; //If there was not enough food, adjust the copy of hungryPeople: if(valueArray[row][col] < hungryPeople) { tempHungryPeople = hungryPeople - valueArray[row][col]; } // Consume what food is left and set hungryPeople to the copy: valueArray[row][col] -= hungryPeople; hungryPeople = tempHungryPeople; // If all of the food was eaten, take the food off the map: if(valueArray[row][col] <= 0) { descriptorArray[row][col] = '.'; valueArray[row][col] = 0; } return hungryPeople; } ////////////////////////////////////////////////////////////////////// // If there is food to eat, eat and return true, else return false: // ////////////////////////////////////////////////////////////////////// bool tribeEat(Tribe& tribe, char descriptorArray[MAXDIM][MAXDIM], int valueArray[MAXDIM][MAXDIM], int numRows, int numCols) { //Get the position of the hungry tribe: int col = tribe.currentPos.x; int row = tribe.currentPos.y; //Since everyone is hungry, set the entire population as hungry: int numHungryPeople = tribe.population; int tempPopulation; //Search for food to the North: if(descriptorArray[row-1][col] == 'w') { row = row-1; //We found food, so let's eat and return the number of // people who are still hungry: numHungryPeople = consumeFood(descriptorArray, valueArray, numHungryPeople, row, col); row = row+1; } //If we still have hungry people, search for food to the East: if(numHungryPeople > 0 && descriptorArray[row][col+1] == 'w') { col = col+1; //We found food, so let's eat and return the number of // people who are still hungry: numHungryPeople = consumeFood(descriptorArray, valueArray, numHungryPeople, row, col); col = col-1; } //If we still have hungry people, search for food to the South: if(numHungryPeople > 0 && descriptorArray[row+1][col] == 'w') { row = row+1; //We found food, so let's eat and return the number of // people who are still hungry: numHungryPeople = consumeFood(descriptorArray, valueArray, numHungryPeople, row, col); row = row-1; } //If we still have hungry people, search for food to the West: if(numHungryPeople > 0 && descriptorArray[row][col-1] == 'w') { col = col-1; //We found food, so let's eat and return the number of // people who are still hungry: numHungryPeople = consumeFood(descriptorArray, valueArray, numHungryPeople, row, col); col = col+1; } //If no food was found, return FALSE: if(numHungryPeople == tribe.population) return false; // Calculate the 5% population decrease based on the number of starving people: int populationDecrease = int(ceil(numHungryPeople / 20.0)); // Calculate the 33% population increase based on the number of people who did eat: int numFullPeople = tribe.population - numHungryPeople; int populationIncrease = int(ceil(numFullPeople * .33)); // Adjust the population against the population increase and decrease: tribe.population = tribe.population + populationIncrease - populationDecrease; // Recalculate the tribe's strength and return TRUE: tribe.strength = int(ceil(tribe.population / 2.0)); return true; } ////////////////////////////////////////////////////////////////////////////// // Visit the selected field and adjust the tribe's population and strength: // ////////////////////////////////////////////////////////////////////////////// void visitField(Tribe& tribe, char descriptorArray[MAXDIM][MAXDIM], int row, int col) { //Adjust the map to show the tribe's move: int oldRow = tribe.currentPos.y; int oldCol = tribe.currentPos.x; descriptorArray[oldRow][oldCol] = '.'; descriptorArray[row][col] = tribe.name; //Mark the position the tribe is coming from: tribe.lastVisitedPos.x = tribe.currentPos.x; tribe.lastVisitedPos.y = tribe.currentPos.y; //Update the tribe's current position: tribe.currentPos.x = col; tribe.currentPos.y = row; //Increment the number of times the position you are coming from was visited so far: tribe.visitedArray[oldRow][oldCol]++; } //////////////////////////////////////////////////////////// // Move the tribe one space in the appropriate direction: // //////////////////////////////////////////////////////////// void tribeMove(Tribe& tribe, char descriptorArray[MAXDIM][MAXDIM], int numRows, int numCols) { //Get the position of the tribe: int col = tribe.currentPos.x; int row = tribe.currentPos.y; int bestDirection[4]; //Store the value of the direction Coordinate bestCoordinate[4]; //Store the coordinates of the direction //Intialize the local arrays: for(int index = 0; index < 4; index ++) { bestDirection[index] = 999; bestCoordinate[index].x = 0; bestCoordinate[index].y = 0; } //Search for a field to the North: if(row != 0 && descriptorArray[row-1][col] == '.') { row = row-1; bestDirection[0] = tribe.visitedArray[row][col]; //IF this was the last visited position, double it's visited value: if((tribe.lastVisitedPos.x == col) && (tribe.lastVisitedPos.y == row)) bestDirection[0] = (bestDirection[0] * 2); bestCoordinate[0].x = col; bestCoordinate[0].y = row; row = row+1; } //Search for a field to the East: if(col != MAXDIM-1 && descriptorArray[row][col+1] == '.') { col = col+1; bestDirection[1] = tribe.visitedArray[row][col]; //IF this was the last visited position, double it's visited value: if((tribe.lastVisitedPos.x == col) && (tribe.lastVisitedPos.y == row)) bestDirection[1] = (bestDirection[1] * 2); bestCoordinate[1].x = col; bestCoordinate[1].y = row; col=col-1; } //Search for a field to the South: if(row != MAXDIM-1 && descriptorArray[row+1][col] == '.') { row = row+1; bestDirection[2] = tribe.visitedArray[row][col]; //IF this was the last visited position, double it's visited value: if((tribe.lastVisitedPos.x == col) && (tribe.lastVisitedPos.y == row)) bestDirection[2] = (bestDirection[2] * 2); bestCoordinate[2].x = col; bestCoordinate[2].y = row; row = row-1; } //Search for a field to the West: if(col != 0 && descriptorArray[row][col-1] == '.') { col = col-1; bestDirection[3] = tribe.visitedArray[row][col]; //IF this was the last visited position, double it's visited value: if((tribe.lastVisitedPos.x == col) && (tribe.lastVisitedPos.y == row)) bestDirection[3] = (bestDirection[3] * 2); bestCoordinate[3].x = col; bestCoordinate[3].y = row; col = col+1; } //Pick the best spot to move to by looking for a bestDirection of 0: for(int bestSoFar = 0; bestSoFar < 1000; bestSoFar++) for(int index = 0; index < 4; index ++) { //If this spot is the best so far, let's check it out: if(bestDirection[index] <= bestSoFar) { row = bestCoordinate[index].y; col = bestCoordinate[index].x; //If we found a field, let's move there and break out of both loops: if(descriptorArray[row][col] == '.') { visitField(tribe, descriptorArray, row, col); index = 4; bestSoFar = 1000; } } } //Decrease the tribe's population by 10% to account for not eating: int numDeadTravelers = int(ceil(tribe.population / 10.0)); tribe.population -= numDeadTravelers; //Adjust the strength to 50% of the new population: tribe.strength = int(ceil(tribe.population / 2.0)); } ////////////////////////////////////////////////////// // Play the game for the specified number of moves: // ////////////////////////////////////////////////////// void playGame(Tribe tribe[10], char descriptorArray[MAXDIM][MAXDIM], int valueArray[MAXDIM][MAXDIM], int numTurns, int numRows, int numCols) { //Play the game for the specified number of rounds: for(int round = 1; round <= numTurns; round ++) { //Search through the Tribes to find the next to play: for(int index = 0; index < 10; index ++) { //If the tribe is not dead, let them take a turn: if(!tribe[index].isDead) { //Search for someone to fight: if(!tribeFight(tribe, index, descriptorArray, numRows, numCols, round)) //If no one to fight, look for something to eat: if(!tribeEat(tribe[index], descriptorArray, valueArray, numRows, numCols)) //If nothing to eat, move to another field: { tribeMove(tribe[index], descriptorArray, numRows, numCols); } //IF the tribe died on this turn, mark them dead: if(tribe[index].population <= 0) { tribe[index].isDead = true; tribe[index].roundKilled = round; } } } } } //////////////////////////////////// // Print the results of the game: // //////////////////////////////////// void printOutput(Tribe tribe[10]) { //Search through the Tribe Array and find existing Tribes: for(int index = 0; index < 10; index ++) { // Only print tribes that were created: if(tribe[index].roundKilled != -1) { //Print the tribe's info: cout << tribe[index].name << " " << tribe[index].population << " (" << tribe[index].currentPos.x << "," << tribe[index].currentPos.y << ")"; //If the tribe is dead, print the round it was killed in: if(tribe[index].isDead) cout << " " << tribe[index].roundKilled; cout << endl; } } //Print an extra newline to seperate data set outputs: cout << endl; } ////////////////////////////////////////////////////////// // Get the map from the input file, populate the tribe, // // play the game for the specified number of turns, // // and print the resulting output: // ////////////////////////////////////////////////////////// int main() { char label[6] = "\0"; //String to read in the START/IN label char descriptor; //Char to read in the descriptor int descriptorVal; //Int to read in the descriptor's value int numTurns; //Number of turns read from the input file int numRows; //Number of rows in the matrix int numCols; //Number of columns in the matrix int tempNumCols; //Copy of 'numCols' char descriptorArray[MAXDIM][MAXDIM] = {'\0'}; //Matrix to hold the descriptor map int valueArray[MAXDIM][MAXDIM] = {0}; //Matrix to hold the descriptor values Tribe tribe[10]; //List of Tribes // Grab the START label: cin >> label; // Gather the input and play the game as long as there is input to process: while(cin && !strcmp(label, "START")) { // Reinitialize re-used variables to allow them to be re-used if necessary: numRows = 0; numCols = 0; tempNumCols = 0; // Reinitalize the arrays to allow them to be re-used if necessary: for(int x = 0; x < MAXDIM; x++) for(int y = 0; y < MAXDIM; y++) { descriptorArray[x][y] = '\0'; valueArray[x][y] = 0; } // Get the number of turns: cin >> numTurns; // Get the map, partitioning the descriptor and value into separate arrays: for(int index = 0; index < MAXDIM; index++) { //As long as we are not at the end, get the next descriptor/value pair: while(!foundEND()) { //If we found a descriptor/value pair, store them in the appropriate arrays // (scanf is used because cin reads in descriptorVal as an octal number): if(cin >> descriptor && cin >> descriptorVal) { descriptorArray[numRows][tempNumCols] = descriptor; valueArray[numRows][tempNumCols] = descriptorVal; numCols++; tempNumCols++; //If we've come to the end of the line, break from the loop: if(foundEOL()) break; } } //Increment the number of rows because we are at the end of the row: numRows++; //IF we are not at the end of the data set, restart the loop: if(!foundEND()) { index = 0; tempNumCols = 0; } //ELSE we are at the end of the data set, so break out: else break; } //Calculate the number of columns of the matrix: numCols = numCols / numRows; //Ensure that the dimensions of the map are valid: if((numRows > 20) || (numCols > 20)) { cout << "Error: The map is too large!\n"; return 1; } //Populate the existing Tribes: populateTribes(tribe, descriptorArray, valueArray, numRows, numCols); //Play the game for the specified amount of rounds: playGame(tribe, descriptorArray, valueArray, numTurns, numRows, numCols); //The game is over, so print the results: printOutput(tribe); //Try to grab the next START label: cin >> label; } //The program finished successfully, so return 0: return 0; }