Search code examples
c#algorithmlinqdiagonal

How to group a square grid diagonally

I have a string of boolean values which represent a square grid.

0100001110000100

boolean string represented as a grid

I am trying to write validation routine which checks the grid diagonally to ensure that there are no diagonal lines which have more than one '1' value in them.

enter image description here

As you can see from this example, the fifth group has two ones.

In order to do this, I would like to arrange the grid into collections and then check each collection to see if it has more than one '1' value.

Shown below is the the values arranged as a collection, as well as the position of each value in the original string.

0       0  
01      4  1
100     8  5  2
0010    12 9  6 3
101     13 10 7
00      14 11 
0       15

I have been trying to figure out the mathematical relationship between the string position and which group it belongs to. I have tried all kinds of formulas but I'm not great at maths so I became stumped.

For reference, the method below is the one I used to validate the string horizontally. The solution I want to come up with needs to be something like this, using LINQ and set based operations as opposed to lots of awkward loops. The exercise I am working on is a code kata about placement of turbines in a windfarm.

    public bool HorizontalValidate(string windfarm)
    {
        var farmSize = (int) Math.Sqrt(windfarm.Length);

        var rows = Enumerable.Range(0, farmSize)
            .Select(x => windfarm.Substring(x * farmSize, farmSize))
            .ToList();

        if (rows.Select(x => x.Count(y => y == '+')).Max() > 1)
            return false;

        return true;
    }

Here is a link if anyone is interested: Windfarm Kata

Solution

  • If you are looking for left-bottom to right-top diagonals you can exploit the fact all items on a diagonal have constant column + row value:

    var int[][] grid = ...

bool result = grid
   .SelectMany((line, row) => line
       .Select((item, column) => (item, diag : row + column)))
   .Where(pair => pair.item == 1)    // Let's keep 1's only
   .GroupBy(pair => pair.diag)       // required GroupBy
   .Any(group => group.Count() > 1);

    If you want to query string windfarm which represents square grid, you can do it as follow:

    string windfarm = "0100110010000100";
int n = (int)Math.Sqrt(windfarm.Length);

bool result = windfarm
   .Select((c, index) => (item : c - '0', diag : index / n + index % n))
   .Where(pair => pair.item == 1)
   .GroupBy(pair => pair.diag)
   .Any(group => group.Count() > 1);

    Fiddle

    In case of left-top to right-bottom diagonals we should use row - column instead of row + column (or index / n - index % n instead of index / n + index % n)