How to group a square grid diagonally

Question 1

I have a string of boolean values represents a square grid.

0100001110000100

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 on them.

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

Question 2

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)

Question 3

I thought it might be worthwhile to show that a boring, procedural-flavoured approach could be implemented with relatively little code, though I do prefer @Dmitry’s solution.

My solution is in Ruby. Viewers unfamiliar with Ruby should have little trouble following what I will write if they think of the code as pseudo-code.

We are given an n x n array, arr, containing elements arr[i][j] that equal '1' or '0'. For example,

arr = [["0", "1", "0", "0"],
       ["0", "0", "1", "1"],
       ["1", "0", "0", "0"],
       ["0", "1", "1", "0"]]

Firstly, we need a method that determines if a given diagonal contains at most one '1'. We can write that as follows.

def diag_valid?(arr, row, col)
  n = arr.size
  found1 = false
  (n-row-col).times do |i|
    if arr[row+i][col+i] == '1'
      return false if found1 == true
      found1 = true
    end
  end
  true
end

row and col are respectively the offsets for the bottom-left end of the diagonal. Either row = 0 and 0 <= col <= n-2 or col = 0 and 0 <= row <= n-2. The upper ends of the ranges are n-2 rather than n-1 because there is no need to check diagonals of length one.

It is seen that n-row-col is the length of the diagonal.

We may now write the main routine that checks all diagonals until and if
an invalid one is found, in which case it returns false, else it returns true.

def arr_valid?(arr)
  n = arr.size
  # check main diagonal
  return false unless diag_valid?(arr,0,0)
  return true if n <= 2
  (1..n-2).all? { |i| diag_valid?(arr,0,i) && diag_valid?(arr,i,0) }
end

arr_valid?(arr)
  #=> false

false is returned because arr[1][3] and arr[3][1] are on the same diagonal and both values equal '1'.

If we are given a string rather than an array, such as

str = "str = "0100001110000110"

we have two choices.

The first is to construct an array from the string and then apply arr_valid?(arr):

n = Integer.sqrt(str.size)
  #=>4

arr = str.each_char.each_slice(n).to_a
  #=> [["0", "1", "0", "0"],
  #    ["0", "0", "1", "1"],
  #    ["1", "0", "0", "0"],
  #    ["0", "1", "1", "0"]]

The second approach is to first construct a method that maps array offsets to a string offset:

def array_offsets_to_string_offset(row, col, n)
  n * (n-row-1) + col
end

For example,

array_offsets_to_string_offset(1, 2, 4)
  #=> 10

str[offset]
  #=> "0"

Then change the methods accordingly. For example, in diag_valid?,

if arr[row+i][col+i] == '1'

would be changed to

if str[array_offsets_to_string_offset(row+1, col+1, n)] == '1'

Leave a Comment Cancel reply