A virus gone viral 2

Computer Science Level 3

In a laboratory housed in kotebe micro-organisms were arranged in a n × n n\times n grid for studying purpose. By accident one of the laboratory technicians spills an infectious virus on some of the organism.This virus has the ability to infect the organism located immediately (east, west, north and south) of its already infected organism in 3 3 microseconds.

To mitigate the rapid spread of this deadly virus some of the grid indices were left empty. How many microseconds does it take for all the organisms to be infected for the 19 × 19 19\times 19 grid shown below. were 0 0 means infected and 1 1 means normal and - means empty. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
 
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,0,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                     1,1,1,1,1,-,1,1,1,1,1,1,1,1,1,1,1,1,1

Details and Assumptions

-Explicit example, If the virus was spilled on a 3 × 3 3\times 3 grid.

( 1 1 1 1 − 1 0 1 − ) ⟶ 3 μ s ( 1 1 1 0 − 1 0 0 − ) ⟶ 3 μ s ( 0 1 1 0 − 1 0 0 − ) ⋯ ( 0 0 0 0 − 0 0 0 − ) \begin{pmatrix} 1 & 1 & 1 \\ 1 & - & 1 \\ 0 & 1 & - \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 1 & 1 & 1 \\ 0 & - & 1 \\ 0 & 0 & - \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 0 & 1 & 1 \\ 0 & - & 1 \\ 0 & 0 & - \end{pmatrix}\cdots \begin{pmatrix} 0 & 0 & 0 \\ 0 & - & 0 \\ 0 & 0 & - \end{pmatrix}

For a total of 15 microseconds.

The organism will quickly start infecting other organisms after being infected.

Here is an easier version


The answer is 108.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Vishnu Bhagyanath
Aug 26, 2015

My C++ code, pretty lengthy, but does the job: I used -3 to classify walls and 0 for infected cells with -2 for uninfected cells Temporary -1 for classifying cells infected in the nth step, later converted to 0 after the iteration. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int array[19][19],i,j,count=0,total=0;
    for(i=0;i<19;++i)
    {
        for(j=0;j<19;++j)
        {
            array[i][j]=-2;
        }
    }
    // set current state of array
    //infected cell
    array[17][1]=0;
    // blank cells
    array[18][5]=-3;
    array[17][4]=-3;
    array[16][3]=-3;
    array[15][2]=-3;
    array[14][1]=-3;
    while(1)
    {
        for(i=0;i<19;++i)
        {
            for(j=0;j<19;++j)
            {
                //if infected, infect neighbours
                if(array[i][j]==0)
                {
                    //if conditions to restrict going outside boundaries
                    // nested if to prevent dash cells being infected
                    if(i!=18)
                    {
                     if(array[i+1][j]==-2)
                        array[i+1][j]=-1;
                    }
                    if(i!=0)
                    {
                     if(array[i-1][j]==-2)
                        array[i-1][j]=-1;
                    }
                    if(j!=0)
                    {
                     if(array[i][j-1]==-2)
                         array[i][j-1]=-1;
                    }
                    if(j!=18)
                    {
                     if(array[i][j+1]==-2)
                         array[i][j+1]=-1;
                    }
                }
            }
        }
        for(i=0;i<19;++i)
        {
            for(j=0;j<19;++j)
            {
                if(array[i][j]==-1)
                {
                    array[i][j]=0;
                }
            }
        }
        count++;
        total=0;
        // Totals the value
        for(i=0;i<19;++i)
        {
            for(j=0;j<19;++j)
                total+=array[i][j];
        }
        //Total should eventually be -15 since there are 5 dash cells, rest should be 0;
        if(total==-15)
            break;
    }
    cout << count*3 << " microseconds taken";
    getch();
}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

I just counted! It's simply the minimum number of steps to get from 0 to the top right corner in this case.

Owen Leong - 5 years, 8 months ago

Here is my solution , it's also a little lengthy. Written in javascript , so it can be tested in the browser , just hit F12 , go to console tab and paste in the code. ( Make sure to expand the log window so you can see the progression of the virus ) 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
var time = 0;
var grid = [        
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,'-',1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,'-',1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,'-',1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,0,1,1,'-',1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,'-',1,1,1,1,1,1,1,1,1,1,1,1,1
]

function drawGrid(){
    var gridString = "";
    for (var i = 1; i <= grid.length; i++) {
        if(i % 19 == 0){gridString = gridString + grid[i-1] + " \n";}
        else gridString = gridString + grid[i-1] + "\t";
    };

    console.log(gridString);
}

function getAllInfected(){
    var t = [];
    jQuery.each(grid , function(index, val) { 
        if(val === 0){
            t.push(index)
        }

    });
    return t;
}


function infect(square){
    var infected = 0;
    var north = grid[square + 19];
    var south = grid[square - 19];
    var east  = grid[square + 1];
    var west  = grid[square - 1];

    if(north == 1){ 
        grid[square + 19] = 0;
        infected = 1;
    }

    if(south == 1){ 
        grid[square - 19] = 0;
        infected = 1;
    }


    if (square % 20 != 0) 
        if(east == 1){ 
            grid[square + 1] = 0;
            infected = 1;
        }

    if (square % 19 != 0)
        if(west == 1){ 
            grid[square - 1] = 0;
            infected = 1;
        }

    return infected;
}

function delay(ms) {
    var cur_d = new Date();
    var cur_ticks = cur_d.getTime();
    var ms_passed = 0;
    while(ms_passed < ms) {
        var d = new Date();  // Possible memory leak?
        var ticks = d.getTime();
        ms_passed = ticks - cur_ticks;
        // d = null;  // Prevent memory leak?
    }
}

while(jQuery.inArray(1,grid) != -1){

        var hasInfected = [];
        var a = getAllInfected();

        for (var i = a.length - 1; i >= 0; i--) {
            var current = a[i];
            hasInfected.push(infect(current));
        };

        delay(100);
        clear();
        drawGrid();

        var noInfections = true;
        for (var i = 0; i < hasInfected.length + 1; i++) {
            if(hasInfected[i] == 1) noInfections = false;
        };

        if (noInfections == true) break;


        time = time + 3;



}

console.log(time);

Radosav Brajic - 5 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...