How to resolve the algorithm 100 prisoners step by step in the C programming language
How to resolve the algorithm 100 prisoners step by step in the C programming language
Table of Contents
Problem Statement
Show and compare the computed probabilities of success for the two strategies, here, on this page.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm 100 prisoners step by step in the C programming language
The code simulates a game where a certain number of prisoners have been thrown in jail and each has a drawer with a number in it. Only one of the drawers has the prisoner's number, the rest have a different number. The prisoners are lined up, and each prisoner can only open a limited number of drawers. If a prisoner opens the drawer with their number, they are set free, otherwise they are executed.
The code first defines a couple of constants, LIBERTY and DEATH, which are used to indicate whether a prisoner is set free or executed, respectively. It then defines a struct, drawer, which has two members: cardNum, which is the number in the drawer, and hasBeenOpened, which indicates whether the drawer has been opened.
The function initialize initializes the drawerSet with the numbers from 1 to prisoners. It first generates a random number and assigns it to the first drawer. It then generates a unique random number for each of the remaining drawers, ensuring that no two drawers have the same number.
The function closeAllDrawers closes all the drawers in the drawerSet.
The function libertyOrDeathAtRandom simulates the game where the prisoners open drawers at random. It iterates over the prisoners, and for each prisoner, it opens a certain number of drawers at random. If the prisoner finds their number in one of the drawers, they are set free, otherwise they are executed. The function returns LIBERTY if all the prisoners are set free, and DEATH otherwise.
The function libertyOrDeathPlanned simulates the game where the prisoners open drawers in a strategic way. It iterates over the prisoners, and for each prisoner, it opens a certain number of drawers. If the prisoner finds their number in one of the drawers, they are set free, otherwise they continue to open drawers until they either find their number or they have opened all the drawers. The function returns LIBERTY if all the prisoners are set free, and DEATH otherwise.
The main function takes three arguments: the number of prisoners, the number of chances each prisoner has to open a drawer, and the number of trials to run. It then runs the simulations and prints the results.
The output of the program shows that the strategic method is more likely to result in the prisoners being set free than the random method. This is because the strategic method ensures that each prisoner opens a drawer with their number, while the random method may not.
Source code in the c programming language
#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define LIBERTY false
#define DEATH true
typedef struct{
int cardNum;
bool hasBeenOpened;
}drawer;
drawer *drawerSet;
void initialize(int prisoners){
int i,j,card;
bool unique;
drawerSet = ((drawer*)malloc(prisoners * sizeof(drawer))) -1;
card = rand()%prisoners + 1;
drawerSet[1] = (drawer){.cardNum = card, .hasBeenOpened = false};
for(i=1 + 1;i<prisoners + 1;i++){
unique = false;
while(unique==false){
for(j=0;j<i;j++){
if(drawerSet[j].cardNum == card){
card = rand()%prisoners + 1;
break;
}
}
if(j==i){
unique = true;
}
}
drawerSet[i] = (drawer){.cardNum = card, .hasBeenOpened = false};
}
}
void closeAllDrawers(int prisoners){
int i;
for(i=1;i<prisoners + 1;i++)
drawerSet[i].hasBeenOpened = false;
}
bool libertyOrDeathAtRandom(int prisoners,int chances){
int i,j,chosenDrawer;
for(i= 1;i<prisoners + 1;i++){
bool foundCard = false;
for(j=0;j<chances;j++){
do{
chosenDrawer = rand()%prisoners + 1;
}while(drawerSet[chosenDrawer].hasBeenOpened==true);
if(drawerSet[chosenDrawer].cardNum == i){
foundCard = true;
break;
}
drawerSet[chosenDrawer].hasBeenOpened = true;
}
closeAllDrawers(prisoners);
if(foundCard == false)
return DEATH;
}
return LIBERTY;
}
bool libertyOrDeathPlanned(int prisoners,int chances){
int i,j,chosenDrawer;
for(i=1;i<prisoners + 1;i++){
chosenDrawer = i;
bool foundCard = false;
for(j=0;j<chances;j++){
drawerSet[chosenDrawer].hasBeenOpened = true;
if(drawerSet[chosenDrawer].cardNum == i){
foundCard = true;
break;
}
if(chosenDrawer == drawerSet[chosenDrawer].cardNum){
do{
chosenDrawer = rand()%prisoners + 1;
}while(drawerSet[chosenDrawer].hasBeenOpened==true);
}
else{
chosenDrawer = drawerSet[chosenDrawer].cardNum;
}
}
closeAllDrawers(prisoners);
if(foundCard == false)
return DEATH;
}
return LIBERTY;
}
int main(int argc,char** argv)
{
int prisoners, chances;
unsigned long long int trials,i,count = 0;
char* end;
if(argc!=4)
return printf("Usage : %s <Number of prisoners> <Number of chances> <Number of trials>",argv[0]);
prisoners = atoi(argv[1]);
chances = atoi(argv[2]);
trials = strtoull(argv[3],&end,10);
srand(time(NULL));
printf("Running random trials...");
for(i=0;i<trials;i+=1L){
initialize(prisoners);
count += libertyOrDeathAtRandom(prisoners,chances)==DEATH?0:1;
}
printf("\n\nGames Played : %llu\nGames Won : %llu\nChances : %lf %% \n\n",trials,count,(100.0*count)/trials);
count = 0;
printf("Running strategic trials...");
for(i=0;i<trials;i+=1L){
initialize(prisoners);
count += libertyOrDeathPlanned(prisoners,chances)==DEATH?0:1;
}
printf("\n\nGames Played : %llu\nGames Won : %llu\nChances : %lf %% \n\n",trials,count,(100.0*count)/trials);
return 0;
}
You may also check:How to resolve the algorithm Color of a screen pixel step by step in the Clojure programming language
You may also check:How to resolve the algorithm Memory allocation step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Variables step by step in the D programming language
You may also check:How to resolve the algorithm Generic swap step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Anagrams/Deranged anagrams step by step in the Maple programming language