A local government organization has been testing a new biological triggering device. The actual cost has gotten out of hand and they have recruited you to test the new style trigger through simulation.
The trigger device is a 20 by 20 grid where each square is a sensor. Each square in the grid starts with one flea. All the fleas jump and land on a neighboring square or the current square which leaves some squares blank or without a flea. Some squares will then have more than one flea. The fleas continue to jump and at some point when 75% of the squares are blank (no fleas) the trigger is fired.
If the flea jumps off the 20 x 20 grid, the flea is zapped and will no longer be able to jump. Flea lost was the big cost overrun the government was having doing real simulations.
To simulate the process, we need to know which way the flea will jump. A flea will only jump to a neighboring square and never two or more squares over. After much research, it was determined which direction a flea will jump. There are nine places a flea can land, the neighboring square or the square the flea is currently jumping from. A flea will jump in one of the corner squares 5% of the time. Each corner is 5%. The top, bottom, left and the current square the flea will jump in 15% of the time and to the right 20% of the time. 20% direction is the way the dog's hair grows and the fleas jump with the hair a little more often than in the other directions. A flea is in the middle square and the directions the flea will jump are shown below.
5 15 5
15 15 20
5 15 5
A simulation consists of setting one flea on each square, and then letting the fleas jump. After each jump, check to see if 75% of the squares are empty. If they are not, then let each flea jump again. You continue letting the fleas jump until 75% of the squares are empty and the simulation stops.
1. How many times will the fleas jump before the trigger is fired?
2. If fleas jumps 5 times every 8 seconds, how much time does one have to clear the area before the trigger is fired?
3. What were the shortest time and the longest time in all simulation
that were needed to clear the area?
4. How many fleas on the average were lost before the trigger was fired? (This is to show the government the cost savings by using simulation rather than the real fleas).
Please find attached 619583.cpp that implements the required simulation using C++ .
Source code has enough comments to help you understand the implementation, ...
Solution allows you to experiment with different size grids by changing just two macro variables (GROWS, GCOLS) in source code. Moreover it allows you to run arbitrary number of simulations during each run of the program, by passing the required simulations count as argument to the program.