• 1 Introduction 
  The 100 prisoners riddle aims at freeing all the prisoners given that each prisoner can find his number slip within the given number of trials. Please view the video for a comprehensive understanding of the riddle. The underlying sense to solve the riddle is to start by opening the box with the respective prisoner's number and then proceed to the box indicated on the slip in the current box. This process would be continued in order to reach a box which points to a box that would contain the prisoner's slips. We are essentially formi loops with all the boxes.
  
  As you can see from the video, surprisingly one-third of the time all 100 prisoners are able to find their slips within 50 trials. And when there is a loop that contains more than 50 slips, a nice guard can help swap the contents of two boxes in the longest loop to split it into two loops each shorter than 50.
  
  In this assignment, we would be simulating this process by implementing the number of boxes that the prisoners would be opening to find their slip, as an 1D integer array in C++. For simplicity of implementation using C++ arrays, unlike in the video, prisoners are numbered 0 to N-1 instead of 1 to N. The students are then expected to work on the following four functions:
  

• simulateRoom(const int boxes[],int num_prisoners, int num_trials)
  

• statsRoom(const int boxes[], int num_prisoners, int num_trials)
  

• successRooms (int boxes[], int num_prisoners, int num_trials)
  

• niceGuard(int boxes[], int num_prisoners, int num_trials)
  

2 Tasks

We have provided the skeleton code for you, and you must complete the following tasks based on that skeleton code. You are encouraged to complete those tasks in the given order. And you are encouraged to reuse the functions you have already implemented. You can also write your own helper functions, but please make sure the function you call is bug-free, or you may lose marks in all tasks that call this function.

We have provided two functions for implementation in the skeleton code. The following is the description of these functions:

• void placeSlips(int boxes[] ,int num_prisoners)
  This function is used to fill the 1D array with a random sequence of unique numbers from 1 to the user input for the number of prisoners.
  

• int main()
  
  The main function provides you with the user input section where you would be recording the num_prisoners (this variable stores the number of prisoners, and you may assume that this variable will not be larger than 1000 in this assignment), num_trials (this variable stores the number of trials each prisoner has to open the boxes) and seed (this variable stores the seed for randomization so that the arrays stays consistent throughout the implementation for all the four functions)
  
  We use the following integer and functions to make a pseudo random number generator:
  

• unsigned int next_num
  Here we initiate an unsigned integer next_num to be used in the following functions.
  

• unsigned int pa1_rand()
  This function is used to return a pseudo random number from 0 to 32767.
  

• void pa1_srand (unsigned int seed)
  
  This function is used to set a seed of the pseudo random number generator. Everytime you call pa1_rand(), you will get a new pseudo random number. For the same seed, the sequence of pseudo random number is fixed. For example, when seed = 3, the sequence of pseudo random number is fixed to be [17746, 30897, 9622, 18921, 4034, 17510, 24152, 14388, 23665,
  
  31532, ...]. When seed = 5, the sequence of pseudo random number is fixed to be [18655, 32247, 9873, 9718, 26373, 27678, 5314, 22512, 31845, 22885, ...]
  

You can try to run the skeleton code, input the values of num_prisoners, num_trials, seed, and select option 0 to print the boxes[]

• Example:

 •

o num_prisoners=10,num_trials=5,seed=3 

o After select option 0:

 53 284701 6 9 •

o num_prisoners=12,num_trials=6,seed=8 o After select option 0:

3 10 2 4 8 11 1 5 7 6 0 9 

2.1 Task 1 

Simulate an actual riddle room.

bool simulateRoom(const int boxes[] ,  int num_prisoners,  int

num_trials)

• Parameters: 

o boxes: the array which consists of all the randomised slips.

 num_prisoners: this variable stores the number of prisoners entered by

num_trials: this variable stores the number of trials each prisoner has to open the box.

• Description:

o Simulate the process of all prisoners going through the room and checking if they can find their slip within the given number of trials.

o If all the prisoners are able to find their slips within the number of trials then return true, else return false. 

• Example:

o num_prisoners=10,num_trials=5,seed=3 

o After function call:

 Failure! Not all prisoners were able to find their slip. •

o num_prisoners=100,num_trials=50,seed=2 o After function call:

 Success! All prisoners found their slip.

2.2 Task 2 45 Points

Display certain statistics for a given room.

void statsRoom(const int boxes[], int num_prisoners, int num_trials)

• Parameters: o

boxes: the array which consists of all the randomised slips.

num_prisoners: this variable stores the number of prisoners entered by

num_trials: this variable stores the number of trials each prisoner has to open the box.

• Description:

o In this task, you are required to display the following statistics given a

1D boxes array with the slips:

§  Number of prisoners find their slips: display the total number
of prisoners who were able to find their slip within the number of trials.
§  Number of loops: display the total number of loops that are formed in a given room.
§  Smallest loop length: display the length of the smallest loop.
§  Longest loop length: display the length of the longest loop.
§  Display the loop sequence of the longest loop: You should

print the loop from the smallest slip number and notice that a number can only be allowed to occur in your printed loop once. If there are multiple loops that tie for longest loop, you should only print the one with the smallest slip number. (Hint: If implemented cleverly, this will be the first one found among them.)

• Example:
o num_prisoners=10,num_trials=5,seed=3 o After function call:

The number of prisoners find their slips: 3 Number of loops: 4

Smallest loop length: 1

Longest loop length: 7

Longest loop: 0 5 7 1 3 8 6

o num_prisoners=15, num_trials=8, seed= 67 o After function call:

The number of prisoners find their slips: 15 Number of loops: 6

Smallest loop length: 1

Longest loop length: 8

Longest loop: 3 4 10 6 12 11 9 5

2.3 Task 3 10 Points

Find the number of instances in 1000 rooms when the prisoners will all be able

to escape.

double successRooms(int boxes[], int num_prisoners, int num_trials)

• Parameters: o

o

o

: the array which consists of all the randomised slips.

: this variable stores the number of prisoners entered by

 boxes

 num_prisoners

the user.

num_trials: this variable stores the number of trials each prisoner has to open the box.

• Description:

o Simulate 1000 rooms.

o Note that you would need to call placeSlips(int boxes[], int size) to generate each of the 1000 rooms.

o You can use the result of Task 1 to count the number of the successful instances where the prisoners will be able to escape.

• Example •

o num_prisoners=10,num_trials=5,seed=3 o After function call:

§ All prisoners were able to leave 376/1000 of the rooms. o num_prisoners=20, num_trials=10, seed= 79

o After function call:

§ All prisoners were able to leave 303/1000 of the rooms. 2.4 Task 4 30 Points

Nice guard will help the prisoners to successfully leave the room by breaking any loop which is greater than the number of trials.

Notice that in this task we only consider the cases that the num_trials not less than half of the num_prisoners

bool niceGuard(int boxes[], int num_prisoners, int num_trials)

• Parameters: o

o

o

: the array which consists of all the randomised slips.

: this variable stores the number of prisoners entered by

 boxes

 num_prisoners

the user.

num_trials: this variable stores the number of trials each prisoner has to open the box.

• Description:

o In this function, you have to determine if there is a loop longer then the

number of trials.

o If so you must apply an intervention to break this loop into two smaller

loops, thus allowing all prisoners to escape successfully

o Return true if the intervention was applied, else return false.

o You are allowed to apply any single intervention that swaps the contents of the two boxes and ensure that there is a successful

escape.

• Example: •

o num_prisoners=10,num_trials=5,seed=3 o After function call:

Intervention applied.

All the prisoners were able to escape.

o num_prisoners=100,num_trials=50,seed=72 o After function call:

No Intervention needed.