Problem statement

A virus is spreading. It spreads one in all directions. Every hour, it spreads one space in all directions. Given the grid, how many hours it takes it to contaminate the whole grid?

So if you have a grid-like this:

0 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

In one hour it will be like this

0 0 0 1 1

0 0 0 0 1

0 0 0 0 0

0 0 0 0 0

Taking into consideration that the virus can appear anywhere in a grid, which has dimensions that are given by rows x columns, and the grid, which contains the initial virus locals. The virus cell is represented as 1 whereas, normal cells are 0 on the grid.

Resolution

I thought about this problem in two ways: one is procedural, the second is the virus as a living being.

1 – Procedural implementation:

So, you go line by line, get the positions of the virus, and calculate the four next positions ~ validate the positions and change from 0 to 1. In a loop. And continue doing that until all the 0 become 1’s

2 – Node implementation

The virus is actually a node, that grows in four dimensions (so the node knows where it will grow). So, if you have a mechanism to control those nodes, that control this growth. I called a tree but is much more like a linked list of nodes, that know where they will grow.

It will continue to spread while the grid still has 0’s, which is done on the growth process:

while(tree.still_can_grow()):

    aux.print_grid(grid)

    hours = hours + 1

    return hours

Implementation

For the procedural implementation, it is here

The tree implementation is here

Benchmarks

I’m doing some benchmarks on this to see the performance.