Question

C++ Problem

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:

The leprechaun jumps to a new location xi + r * gi, where r is a random number between -1 and 1.

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 player’s score (the player starts with score=0).

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.

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.

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

HERE IS THE SAMPLE CODE THAT MUST BE USED, DO NOT CHANGE ANYTHING JUST ADD TO IT:

#include "stdafx.h"
#include <iostream>
#include <chrono>
#include <random>

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<chrono::milliseconds>(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;
}

SAMPLE OUTPUT:

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