linq 如何对角分组方形网格

gk7wooem  于 12个月前  发布在  其他
关注(0)|答案(2)|浏览(102)

我有一串布尔值,代表一个正方形网格。

0100001110000100

字符串


的数据
我试图写验证例程,检查网格对角线,以确保没有对角线中有一个以上的'1'值。



从这个例子中可以看出,第五组有两个1。
为了做到这一点,我想把网格排列成集合,然后检查每个集合,看看它是否有一个以上的“1”值。
下面显示的是作为集合排列的值,以及每个值在原始字符串中的位置。

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


我一直在试图找出弦的位置和它属于哪一组之间的数学关系。我试过各种公式,但我不擅长数学,所以我被难倒了。
作为参考,下面的方法是我用来水平验证字符串的方法。我想提出的解决方案需要像这样,使用LINQ和基于集合的操作,而不是大量笨拙的循环。我正在做的练习是关于风电场中涡轮机放置的代码kata。

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;
    }


这里有一个链接,如果有人感兴趣:Windfarm Kata

vi4fp9gy

vi4fp9gy1#

如果你正在寻找从左下到右上的对角线,你可以利用对角线上的所有元素都有恒定的column + row值的事实:

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);

字符串
如果你想查询字符串windfarm,表示 square grid,你可以这样做:

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
如果是从左上到右下的对角线,我们应该使用row - column而不是row + column(或者index / n - index % n而不是index / n + index % n

2jcobegt

2jcobegt2#

我认为,尽管我更喜欢@Dmitry的解决方案,但值得展示的是,一种枯燥的、带有过程味道的方法可以用相对较少的代码来实现。
我的解决方案是用Ruby编写的。不熟悉Ruby的读者如果认为我写的代码是伪代码,他们应该很容易理解。
我们有一个n x n数组arr,其中包含的元素arr[i][j]等于'1''0'。例如,

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

字符串
首先,我们需要一种方法来确定一个给定的对角线是否至多包含一个'1',我们可以将其写成如下:

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


rowcol分别是对角线左下角的偏移量。row = 00 <= col <= n-2col = 00 <= row <= n-2。范围的上限是n-2而不是n-1,因为不需要检查长度为1的对角线。
可以看出,n-row-col是对角线的长度。
我们现在可以编写主例程,检查所有对角线,直到找到无效对角线,如果找到无效对角线,则返回false,否则返回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,因为arr[1][3]arr[3][1]在同一对角线上,并且两个值都等于'1'
如果给我们的是一个字符串而不是一个数组,比如

str = "str = "0100001110000110"


我们有两个选择。
第一种方法是从字符串构造一个数组,然后应用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"]]

的字符串
第二种方法是首先构造一个将数组偏移量Map到字符串偏移量的方法:

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


比如说,

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

str[offset]
  #=> "0"


然后相应地更改方法。例如,在diag_valid?中,

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


将改为

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

相关问题