# Propagation in grid

Can I do it with a lower Big O / better code? How can I improve this solution?

Task:

Let's assume we have a array like this:

1 0 0 1 0

0 0 0 0 0

0 0 0 1 0

0 0 0 0 0

1 0 0 0 0

In each turn, '1's are propagated to the neighbors(left, top, right, bottom). Return number of turns after which the whole grid will be filled with '1's.

Example of the above:

After turn 1(bold - a new '1' in the last turn):

1 1 1 1 1

1 0 0 1 0

0 0 1 1 1

1 0 0 1 0

1 1 0 0 0

After turn 2:

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

After turn 3:

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

Result: 3

My approach:

1. Collect all '1'
2. For each saved '1' propagate to all neighbors that are '0' and save newly propagated
3. Repeat 2 till nothing new appear
4. Return number of turns/generations

What is the Big O?

R - rows

C - columns

I would assume. R*C(initial discover of '1') + 4*R*C(because each number will check ones all the neighbors) = 5*RC = RC

I think it is R*C and it is linear. Am I correct?

My code(the main method contains 4 additional examples):

class Program
{
static void Main(string[] args)
{
Console.WriteLine(MinimumGenerations(2, 2, new int[2,2] { { 1, 0 }, { 0, 0 } }));//result 2
Console.WriteLine(MinimumGenerations(3, 3, new int[3,3] { { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } }));//result 4
Console.WriteLine(MinimumGenerations(1, 1, new int[1, 1] { { 0 } }));//result -1
Console.WriteLine(MinimumGenerations(1, 1, new int[1, 1] { { 1 } }));//result 0

Console.ReadKey();
}

public static int MinimumGenerations(int rows, int columns, int[,] grid)
{
var toPropagate = InitialPointsToPropagate(rows, columns, grid);

if(toPropagate.Count == 0)//whole grid was filled with '0'
{
return -1;
}

if(toPropagate.Count == rows * columns)//whole grid was filled with '1'
{
return 0;
}

var generation = 0;
do
{
var toPropagateInNextGeneration = PropagateAllPoints(rows, columns, grid, toPropagate);
if (toPropagateInNextGeneration.Any())
{
generation++;
toPropagate = toPropagateInNextGeneration;
}
} while (toPropagate.Count > 0);

return generation;
}

private static Queue<CustomPoint> PropagateAllPoints(int rows, int columns, int[,] grid, Queue<CustomPoint> toPropagate)
{
var toPropagateInNextGeneration = new Queue<CustomPoint>();

while(toPropagate.Count > 0)
{
var pointToProcess = toPropagate.Dequeue();
if(EmptyBottom(rows, grid, pointToProcess))
{
var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row + 1);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);
}

if(EmptyLeft(grid, pointToProcess))
{
var newPoint = new CustomPoint(pointToProcess.Column - 1, pointToProcess.Row);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);
}

if(EmptyRight(columns, grid, pointToProcess))
{
var newPoint = new CustomPoint(pointToProcess.Column + 1, pointToProcess.Row);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);
}

if(EmptyTop(grid, pointToProcess))
{
var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row - 1);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);
}
}

return toPropagateInNextGeneration;
}

private static Queue<CustomPoint> InitialPointsToPropagate(int rows, int columns, int[,] grid)
{
var toPropagate = new Queue<CustomPoint>();

for (var row = 0; row < rows; row++)
{
for(var column = 0; column < columns; column++)
{
if(grid[row, column] == 1)
{
toPropagate.Enqueue(new CustomPoint(column, row));
}
}
}

return toPropagate;
}

private static bool EmptyRight(int columns, int[,] grid, CustomPoint point)
{
return point.Column<columns - 1 && grid[point.Row, point.Column + 1] == 0;
}

private static bool EmptyLeft(int[,] grid, CustomPoint point)
{
return point.Column > 0 && grid[point.Row, point.Column - 1] == 0;
}

private static bool EmptyBottom(int rows, int[,] grid, CustomPoint point)
{
return point.Row < rows - 1 && grid[point.Row + 1, point.Column] == 0;
}

private static bool EmptyTop(int[,] grid, CustomPoint point)
{
return point.Row > 0 && grid[point.Row - 1, point.Column] == 0;
}
}

internal struct CustomPoint
{
public int Row { get;  }
public int Column { get; }

public CustomPoint(int column, int row)
{
Row = row;
Column = column;
}
}

## 1 Answer

Just one remark: do not copy-paste code and then change one tiny bit of it. This indicates that you should create a method. What I mean is this:

var newPoint = new CustomPoint(pointToProcess.Column, pointToProcess.Row + 1);
grid[newPoint.Row, newPoint.Column] = 1;
toPropagateInNextGeneration.Enqueue(newPoint);

Those three lines are always the same, except the values of the parameters used in the CustomPoint constructor.

I'd create a AllPointsPropagator like this:

internal class AllPointsPropagator
{
private static readonly Queue<CustomPoint> ToPropagateInNextGeneration = new Queue<CustomPoint>();

public static Queue<CustomPoint> Execute(int rows, int columns, int[,] grid, Queue<CustomPoint> toPropagate)
{
while (toPropagate.Count > 0)
{
var pointToProcess = toPropagate.Dequeue();
if (EmptyBottom(rows, grid, pointToProcess))
{
AddNewPoint(grid, pointToProcess.Column, pointToProcess.Row + 1);
}

if (EmptyLeft(grid, pointToProcess))
{
AddNewPoint(grid, pointToProcess.Column - 1, pointToProcess.Row);
}

if (EmptyRight(columns, grid, pointToProcess))
{
AddNewPoint(grid, pointToProcess.Column + 1, pointToProcess.Row);
}

if (EmptyTop(grid, pointToProcess))
{
AddNewPoint(grid, pointToProcess.Column, pointToProcess.Row - 1);
}
}

return ToPropagateInNextGeneration;
}

private static void AddNewPoint(int[,] grid, int column, int row)
{
var newPoint = new CustomPoint(column, row);
grid[newPoint.Row, newPoint.Column] = 1;
ToPropagateInNextGeneration.Enqueue(newPoint);
}

The four Empty* methods should also move to this class. Now PropagateAllPoints() can be replaced by AllPointsPropagator.Execute(rows, columns, grid, toPropagate);.

• Good point with separate AddNewPoint(). I did that before but when I was running a performance test the average time for some reason was slower. I assumed it was correlated with stack calls. Here I don't see the difference. I like the idea of a separate class. I didn't think about it for a task like this. I will next time. There is one small mistake in the code you provided. After 1st turn ToPropagateInNextGeneration and toPropagate are the same stack. 1st line in Execute() method should be: ToPropagateInNextGeneration = new Queue<CustomPoint>(); and that field should not be readonly. Mar 11, 2020 at 15:17
• @Egnever Yeah, the code is more like proof of concept than actual production code. Mar 11, 2020 at 15:51