C++ In this project, you are to write a program that performs such an n-body simulation for a game called Jumping Leprechauns. Rules The game starts out with n leprechauns. Each leprechaun starts out with a million dollars of gold (i.e., gi = 1,000,000). The player wants to trap as many of these leprechauns in a pit and steal their gold! The leprechauns are all in a row, with each leprechaun at location xi, a double precision floating point number. Initially, the first leprechaun is at x = 0, the second at x= 1,000,000, ...; i.e., xi = i * gi, i = 0,1,2,.... At every iteration of the simulation, the leprechauns are processed in strict order from i = 0,1,2,... The processing of a leprechaun involves these steps: 1. The leprechaun jumps to a new location xi + r * gi, where r is a random number between -1 and 1. 2. There is a pit located between -1,000 and 1,000. If -1000 < xi < 1000, then that leprechaun is trapped forever (does not participate in the game anymore) and all his gold is added to the players score (the player starts with score = 0). 3. If a leprechaun lands right on top of another (k), then the newly arrived leprechaun steals all the gold from k, and the bankrupt leprechaun k exits the game. 4. The leprechaun then steals half the gold from the nearest leprechauns to his right and left, if he indeed has both neighbours. (If the position moved to is either the largest or smallest value of all xi, then there is only one neighbour that is nearest. In this case he steals half the gold from this nearest neighbour). The game ends after a fixed period of time (e.g., 20 seconds), at which point the final score is displayed. Program Input The program initially asks the user for:

1. A number to initialize the random number generator (that dictates the jumping of the leprechauns) 2. The number of leprechauns 3. Game play time, i.e., time to run the simulation in seconds

Program Output At every iteration, only these events should be printed out: 1. The trapping of a leprechaun in a pit (results in a score increase) 2. Landing exactly on another leprechaun At the end of the simulations, print out: 1. The number of iterations completed 2. The number of leprechauns trapped in the pit 3. The score Data Structures You must use a map-based data structure for this project to efficiently access and modify the state of the leprechauns. While it is possible to implement the logic using simpler data structures, your code will run too slow to be competitive. Note that the more iterations you can complete within the specified time limit, the more likely you are to trap leprechauns and get a higher score. You can use the map container included in the C++ Library, develop your own binary search tree, or modify the code developed in class. In all cases, all your code should be within one file.

Sample Output Here is some sample output to check your code:

Enter seed for random number generator: 123 Enter number of leprechauns: 10000 Enter game play time (seconds): 20 t=0: Caught a leprechaun!! Score = 1000000 t=5: Caught a leprechaun!! Score = 4729343 t=5: Caught a leprechaun!! Score = 5219710 t=8: Caught a leprechaun!! Score = 6522043 t=8: Caught a leprechaun!! Score = 9111052 t=10: Caught a leprechaun!! Score = 9209047 t=10: Caught a leprechaun!! Score = 9642793 t=11: Caught a leprechaun!! Score = 9967663 Number of iterations = 13 Number of trapped leprechauns = 8 Score = 9967663 Template Code #include "stdafx.h" #include #include #include

using namespace std;

class RandomNumberGenerator { public: RandomNumberGenerator(int x) :generator(x) {}; // return a double between -1 and 1 double randomBetween1and2() { return (2.0*generator()) / generator.max() - 1.0; } private: minstd_rand0 generator; };

int N; // Use a constant random number seed so behavior is consistent from run to run. int RANDOM_SEED;

int main() {

cout << "Enter seed for random number generator: "; cin >> RANDOM_SEED; RandomNumberGenerator rng(RANDOM_SEED);

cout << "Enter number of leprechauns: "; cin >> N;

long playtime; cout << "Enter game play time (seconds): "; cin >> playtime; playtime = playtime * 1000; // convert to milliseconds

double score = 0; int nTrapped = 0;

// // CODE FOR INITIALIZING DATA STRUCTURES GOES HERE //

int t = 0; // keep track of number of iterations auto start_time0 = chrono::high_resolution_clock::now(); auto timeSinceStartMS = 0; do {

// // CODE FOR A SINGLE ITERATION GOES HERE //

//// You can use the random number generator like so: // double r = rng.randomBetween1and2(); // x = x + r*gold;

t++; // code to measure run time auto end_time = std::chrono::high_resolution_clock::now(); auto timeSinceStart = end_time - start_time0; timeSinceStartMS = chrono::duration_cast(timeSinceStart).count(); } while (timeSinceStartMS < playtime);

cout << "Number of iterations = " << t << endl; cout << "Number of trapped leprechauns = " << nTrapped << endl; cout << "Score = " << (long)score << endl; return 0; }