Control-The-Virus

Problem Statement :

Designing an efficient method to limit the spread of the virus utilizing limited available resources.

Explanation of this project :

A virus has gripped a village and is spreading at an alarming rate. With each passing night, the virus multiplies in all directions. To prevent the spread of this virus, we need to quarantine as many houses affected as possible. Because of limited resources, we can quarantine only a single block of houses in a day.

Motivation :

Current global crisis has taken a toll on all our lives. Following the pandemic, reducing the effect of the virus was a matter of utmost importance. So, we tried to come up with an idea of quarantining the affected houses thus minimizing the spread of the virus if we had a chance.

Proposed Solution :

The aim of our project is to quarantine those clusters of infected houses which will have a massive impact on the outspread of the virus. Owing to the limited resources, we will first quarantine that part of the village where the maximum number of houses will be affected overnight. By the next day, the virus must have spread in the other parts of the village. Then, we analyze the condition.

Approach to solve this problem:

Here we assume a village is an mXn grid.
Constraints
There will never be a tie. The cluster of affected houses will always form a rectangle. In this, we utilize 2 functions:-

1.) The first function identifies which cluster of houses should be quarantined first.
2.) Since in one day we can quarantine only one cluster, the second function provides us with where the virus has spread in one night.
So, we take a 2-D array where 0 represents unaffected houses and 1 represent houses affected by the virus . As mentioned above, we call two different functions which consist of various loops and conditional statements.
For example: - Based on the above diagram, we quarantine the 5 affected houses on the right. Since the left side couldn’t be quarantined the virus has spread overnight. So, now on the next day we quarantine this side. To represent the quarantined houses we mark them as -1. Thus, we have stopped the virus outbreak.

Proposed Solution:

We illustrate an example below, displaying the results of our code We take a 6X6 grid to show the village affected by the virus. In this example, there are 2 clusters of houses that are already affected by the virus.

1 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 1 1 0
0 0 0 0 0 0

Function Wall As we can see the top-left cluster will affect 5 houses whereas the other cluster affects 10 houses. Utilizing the first function, we identify the cluster of houses to be quarantined and change their value to 2.

1 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 2 2 0
0 0 0 2 2 0
0 0 0 0 0 0

Function Overnight Now, the second function is called which increases the affected houses overnight because of the lack of resources. We show this by spreading the virus to the neighbouring houses.

Final Output
As we can clearly see there is only one cluster of houses left, the functions quarantine the last cluster and terminate the loop.

1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
0 0 0 -1 -1 0
0 0 0 -1 -1 0
0 0 0 0 0 0

2 2 2 0 0 0
2 2 2 0 0 0
2 2 2 0 0 0
0 0 0 -1 -1 0
0 0 0 -1 -1 0
0 0 0 0 0 0

Hence, the affected houses were quarantined and the village was saved.
Total number of houses quarantined: 13
Total number of houses saved: 23
Number of nights to stop the virus: 2

-1 -1 -1 0 0 0
-1 -1 -1 0 0 0
-1 -1 -1 0 0 0
0 0 0 -1 -1 0
0 0 0 -1 -1 0
0 0 0 0 0 0

In order to save a village from being affected by a virus, given the limited number of resources available, it is important to first quarantine those cluster of houses which could lead to a massive outbreak of the virus in the village. To achieve this task, we design an approach that limits the spread of the virus overnight and tries to save the village with the resources available. Our approach can be modified using preexisting approaches like back tracking to minimize this effort.