C++11, 6-8 minutes
My test run takes about 6-8 minutes in my Fedora 19, i5 machine. But due to the randomness of the mutation, it might as well be faster or take longer than that. I think the scoring criteria needs to be readdressed.
Prints the result as text at the end of completion, healthy person denoted by dot (.), infected person by asterisk (*), unless ANIMATE flag is set to true, in which case it will display different characters for people infected with different virus strain.
Here is a GIF for 10x10, 200 periods.
Mutation behaviour
Each mutation will give new strain never seen before (so it is possible that one person infects the four neighboring people with 4 distinct strains), unless 800 strains have been generated, in which case no virus will go any further mutation.
The 8-minute result comes from the following number of infected people:
Period 0, Infected: 4
Period 100, Infected: 53743
Period 200, Infected: 134451
Period 300, Infected: 173369
Period 400, Infected: 228176
Period 500, Infected: 261473
Period 600, Infected: 276086
Period 700, Infected: 265774
Period 800, Infected: 236828
Period 900, Infected: 221275
while the 6-minute result comes from the following:
Period 0, Infected: 4
Period 100, Infected: 53627
Period 200, Infected: 129033
Period 300, Infected: 186127
Period 400, Infected: 213633
Period 500, Infected: 193702
Period 600, Infected: 173995
Period 700, Infected: 157966
Period 800, Infected: 138281
Period 900, Infected: 129381
Person representation
Each person is represented in 205 bytes. Four bytes to store the virus type this person is contracting, one byte to store how long has this person been infected, and 200 bytes to store how many times he has contracted each strain of virus (2 bit each). Perhaps there are some additional byte-alignment done by C++, but the total size will be around 200MB. I have two grids to store the next step, so total it uses around 400MB.
I store the location of infected people in a queue, to cut the time required in the early periods (which is really useful up to periods < 400).
Program technicalities
Every 100 steps this program will print the number of infected people, unless ANIMATE flag is set to true, in which case it will print the whole grid every 100ms.
This requires C++11 libraries (compile using -std=c++11 flag, or in Mac with clang++ -std=c++11 -stdlib=libc++ virus_spread.cpp -o virus_spread).
Run it without arguments for the default values, or with arguments like this:
./virus_spread 1 0.01 1000
#include <cstdio>
#include <cstring>
#include <random>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <deque>
#include <cmath>
#include <functional>
#include <unistd.h>
typedef std::pair<int, int> pair;
typedef std::deque<pair> queue;
const bool ANIMATE = false;
const int MY_RAND_MAX = 999999;
std::default_random_engine generator(time(0));
std::uniform_int_distribution<int> distInt(0, MY_RAND_MAX);
auto randint = std::bind(distInt, generator);
std::uniform_real_distribution<double> distReal(0, 1);
auto randreal = std::bind(distReal, generator);
const int VIRUS_TYPE_COUNT = 800;
const int SIZE = 1000;
const int VIRUS_START_COUNT = 4;
typedef struct Person{
int virusType;
char time;
uint32_t immune[VIRUS_TYPE_COUNT/16];
} Person;
Person people[SIZE][SIZE];
Person tmp[SIZE][SIZE];
queue infecteds;
double transmissionProb = 1.0;
double mutationProb = 0.01;
int periods = 1000;
char inline getTime(Person person){
return person.time;
}
char inline getTime(int row, int col){
return getTime(people[row][col]);
}
Person inline setTime(Person person, char time){
person.time = time;
return person;
}
Person inline addImmune(Person person, uint32_t type){
person.immune[type/16] += 1 << (2*(type % 16));
return person;
}
bool inline infected(Person person){
return getTime(person) > 0;
}
bool inline infected(int row, int col){
return infected(tmp[row][col]);
}
bool inline immune(Person person, uint32_t type){
return (person.immune[type/16] >> (2*(type % 16)) & 3) == 3;
}
bool inline immune(int row, int col, uint32_t type){
return immune(people[row][col], type);
}
Person inline infect(Person person, uint32_t type){
person.time = 1;
person.virusType = type;
return person;
}
bool inline infect(int row, int col, uint32_t type){
auto person = people[row][col];
auto tmpPerson = tmp[row][col];
if(infected(tmpPerson) || immune(tmpPerson, type) || infected(person) || immune(person, type)) return false;
person = infect(person, type);
infecteds.push_back(std::make_pair(row, col));
tmp[row][col] = person;
return true;
}
uint32_t inline getType(Person person){
return person.virusType;
}
uint32_t inline getType(int row, int col){
return getType(people[row][col]);
}
void print(){
for(int row=0; row < SIZE; row++){
for(int col=0; col < SIZE; col++){
printf("%c", infected(row, col) ? (ANIMATE ? getType(row, col)+48 : '*') : '.');
}
printf("\n");
}
}
void move(){
for(int row=0; row<SIZE; ++row){
for(int col=0; col<SIZE; ++col){
people[row][col] = tmp[row][col];
}
}
}
int main(const int argc, const char **argv){
if(argc > 3){
transmissionProb = std::stod(argv[1]);
mutationProb = std::stod(argv[2]);
periods = atoi(argv[3]);
}
int row, col, size;
uint32_t type, newType=0;
char time;
Person person;
memset(people, 0, sizeof(people));
for(int row=0; row<SIZE; ++row){
for(int col=0; col<SIZE; ++col){
people[row][col] = {};
}
}
for(int i=0; i<VIRUS_START_COUNT; i++){
row = randint() % SIZE;
col = randint() % SIZE;
if(!infected(row, col)){
infect(row, col, 0);
} else {
i--;
}
}
move();
if(ANIMATE){
print();
}
for(int period=0; period < periods; ++period){
size = infecteds.size();
for(int i=0; i<size; ++i){
pair it = infecteds.front();
infecteds.pop_front();
row = it.first;
col = it.second;
person = people[row][col];
time = getTime(person);
if(time == 0) continue;
type = getType(person);
if(row > 0 && randreal() < transmissionProb){
if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
newType++;
if(!infect(row-1, col, newType)) newType--;
} else {
infect(row-1, col, type);
}
}
if(row < SIZE-1 && randreal() < transmissionProb){
if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
newType++;
if(!infect(row+1, col, newType)) newType--;
} else {
infect(row+1, col, type);
}
}
if(col > 0 && randreal() < transmissionProb){
if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
newType++;
if(!infect(row, col-1, newType)) newType--;
} else {
infect(row, col-1, type);
}
}
if(col < SIZE-1 && randreal() < transmissionProb){
if(newType < VIRUS_TYPE_COUNT-1 && randreal() < mutationProb){
newType++;
if(!infect(row, col+1, newType)) newType--;
} else {
infect(row, col+1, type);
}
}
time += 1;
if(time == 4) time = 0;
person = setTime(person, time);
if(time == 0){
person = addImmune(person, type);
} else {
infecteds.push_back(std::make_pair(row, col));
}
tmp[row][col] = person;
}
if(!ANIMATE && period % 100 == 0) printf("Period %d, Size: %d\n", period, size);
move();
if(ANIMATE){
printf("\n");
print();
usleep(100000);
}
}
if(!ANIMATE){
print();
}
return 0;
}
V, the second contracts virusV'. The contraction will both end at the same period. Can virusVinfects the second person? (Or a more black-and-white question: is it possible that a person be infected immediately after he is healed, so he will end up with 6 consecutive period of infection?) \$\endgroup\$Vin personA, andVagain in personB. When they transmit the virus, can they both mutate to the same mutationV'? Or perhaps they in fact should mutate to the same virus strain? If they can mutate arbitrarily, what is the probability of two viruses mutating to the same virus strain? \$\endgroup\$