Wednesday, April 18, 2012

Lab 25: Social Zombies

In this lab you will write a program to simulate the spread of a virus among a population. Our virus of choice is the zombie virus. We assume that each person has the same number of friends, all chosen randomly from the population. Then, at each time step, all zombie persons will randomly choose one of their friends (zombie or not) and bite him. If the friend was not a zombie he will turn into a zombie. Zombie bites on zombies do nothing.

More specifically, for this lab you will implement a Person class and a Graph class.

The Person has (at least, you will need more methods):
  • a data member friends that holds all his friends (which are of type Person)
  • a boolean zombie which tells us if he is a zombie

The Graph class has (at least, you will need more methods)
  • a people data member which holds all the people
  • a getRandomPerson() which returns a random person from people
  • a getRandomOther(Person p) which returns a random person from people that is not p
  • a makeFriends(int x) which gives each person in the graph x randomly chosen friends
  • a infectOne() method which infects (sets as a zombie) one random person
  • a go() method which runs one step of the simulation: all the zombies bite one of their friends at random
Thus, the following main
public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    System.out.print("Enter the number of people:");
    int numPeople = keyboard.nextInt();
    System.out.print("Enter the number of friends each person has:");
    int numFriends = keyboard.nextInt();
    Graph g = new Graph(numPeople);
    g.makeFriends(numFriends);
    //print it out, for testing.
    //System.out.println(g);
    g.infectOne();
    int day = 1;
    int count = 0;
    do {
      count = g.getNumZombies();
      System.out.println("Day " + day + ": Zombie count is " + count);
      g.go();
      day++;
    } while (count < numPeople);
    System.out.println("Zombieland");
   }
will print out something like:
Enter the number of people:100
Enter the number of friends each person has:5
Day 1: Zombie count is 1
Day 2: Zombie count is 2
Day 3: Zombie count is 4
Day 4: Zombie count is 10
Day 5: Zombie count is 21
Day 6: Zombie count is 35
Day 7: Zombie count is 59
Day 8: Zombie count is 77
Day 9: Zombie count is 89
Day 10: Zombie count is 91
Day 11: Zombie count is 96
Day 12: Zombie count is 97
Day 13: Zombie count is 97
Day 14: Zombie count is 99
Day 15: Zombie count is 100
Zombieland
Note that if you use a small number of friends (say, 2) then it might get into an infinite loop with a fixed number of zombies. This is because none of the zombies have a friend that is not a zombie (what you have then are 2 or more disconnected graphs, in graph theoretic terms). As always, turn it in on the dropbox.cse.sc.edu. You have an extra 48 hours to finish this lab, if you can't finish it during lab.

This is the last lab for the year. See you at the Final!

1 comment:

Anonymous said...

I'll be honest; i'm going to miss this class.