Problem
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:
- Collect all ‘1’
- For each saved ‘1’ propagate to all neighbors that are ‘0’ and save newly propagated
- Repeat 2 till nothing new appear
- 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;
}
}
Solution
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);.