Answer to Question #67031 in Java | JSP | JSF for Christa Jordan

Question

Alice is throwing a party with N other guests, including Bob. Bob starts a rumor about Alice by telling it to one of the other guests. A person hearing this rumor for the first time will immediately tell it to one other guest, chosen at random from all the people at the party except Alice and the person from whom they heard it. If a person (including Bob) hears the rumor for a second time, he or she will not propagate it further. Write a program to estimate the probability that everyone at the party (except Alice) will hear the rumor before it stops propagating. Also calculate an estimate of the expected number of people to hear the rumor. For each line of the code, add comments.

Answer 1

package com.company;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
final int attempts = 100; //hardcoded amount of times we will check to empirically calculate probabilities
Scanner sc = new Scanner(System.in); //read data using Scanner
System.out.println("Enter how much people should be at the party: ");
System.out.println("Number should be > 2");
int n = sc.nextInt(); //read N
int countTimesFullSpreaded = 0; //Ho many times all people heard the rumor
int peopleReached = 0; //How many people in all attempt heard the rumor
for(int i=0;i<attempts;i++){
boolean guests[] = new boolean[n]; // Alice is zero element, Bob is 1, all other guests - from 2 to N
guests[1] = true; //Bob already heard
boolean alreadyHeard = false; //Condition to exit while loop
int nextPerson = -1; //our random next person
int currentPerson = 1; //we start from Bob
while(!alreadyHeard){
nextPerson = 1 + (int)(Math.random() * (n-1)); //randomize next person
if(nextPerson == currentPerson){ // check that it's not our current person
while(nextPerson == currentPerson) //if it's true then we just randoming till we get other person
nextPerson = 1 + (int)(Math.random() * (n-1));
}
if(guests[nextPerson]) //if guest already heard
{
if(rumorSpreaded(guests)) //if all people heard
countTimesFullSpreaded++;
peopleReached = peopleReached + countPeopleReached(guests); //how many people we get at all
alreadyHeard = true; // our condition is true
}
guests[nextPerson] = true; //now nextperson heard rumor
currentPerson = nextPerson; //current person now is nextperson
}
}
//For bigger N we will have less empirical probability
System.out.println("Empirical probability that everyone will hear rumor except Alice in "+attempts+" attempts: " +
(double)countTimesFullSpreaded/attempts);
System.out.println("Average amount of people that rumor reached is: "+peopleReached/attempts);
}

public static int countPeopleReached(boolean arr[]){
int counter = 0;
for(int i = 1;i<arr.length;i++)
if(arr[i])
counter++;
return counter;
}

public static boolean rumorSpreaded(boolean arr[]){
for(int i = 1;i<arr.length;i++)
if(!arr[i])
return false;
return true;
}


}