Entries:
Discussions:

Something went wrong getting user information from Channel 9

Latest Achievement:

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Something went wrong getting the Visual Studio Achievements

# A trivial question

• Oops, something didn't work.

Getting subscription
Subscribe to this conversation
Unsubscribing
Subscribing
• I have a 2d array of bools and I want to find the largest solid square of trues within, using linq, returning the topleft coordinate and the width. I worked on this earlier today and the performance was so terrible that I decided to just walk away for a day. Any ideas?

-Josh

• My first reaction would be to look for the longest runs of contiguous trues within rows; then from the reduced set I would start looking for squares.

Herbie

• ```
static int FindOffset(bool[] arr, out int longestRunLength)
{
int longestRunOffset = -1;
longestRunLength = 0;

// look for the start of a block of trues:
for(int i = 0; i < arr.Length - longestRunLength; i++)
{
// ignore falses at the start and in blocks of falses:
if(arr[i] == false) continue;

// we found a true - let's see how long the block is:
int thisRunStart = i;
int thisRunLength = 0;
for(/* no init */ ; i < arr.Length; i++)
{
if(arr[i] == true)
// still in that block of trues:
continue;
else
// end of that block of trues:
break;
}

int thisRunLength = i - thisRunStart;
if(thisRunLength > longestRunLength)
{
longestRunOffset = thisRunStart;
longestRunLength = thisRunLength;
}
}
return longestRunOffset;
}

```

• ``` static int FindOffset(bool[] arr, out int longestRunLength)
{
int longestRunOffset = -1;
longestRunLength = 0;

// look for the start of a block of trues:
for(int i = 0; i < arr.Length - longestRunLength; i++)
{
// ignore falses at the start and in blocks of falses:
if(arr[i] == false) continue;

// we found a true - let's see how long the block is:
int thisRunStart = i;
int thisRunLength = 0;
for(/* no init */ ; i < arr.Length; i++)
{
if(arr[i] == true)
// still in that block of trues:
continue;
else
// end of that block of trues:
break;
}

int thisRunLength = i - thisRunStart;
if(thisRunLength > longestRunLength)
{
longestRunOffset = thisRunStart;
longestRunLength = thisRunLength;
}
}
return longestRunOffset;
}

```

• I don't know why Channel9 sucks so badly at pasting code. Even if I paste it into notepad and back again it doesn't work, and I even went so far as to go into HTML mode and paste <br>s at the end of each line. C9's editor epically sucks.

• Yup. It's totally jacked. The code editor on CodePlex works perfectly, and it appears to be the same as the one here.

• ,JoshRoss wrote

I have a 2d array of bools and I want to find the largest solid square of trues within, using linq, returning the topleft coordinate and the width. I worked on this earlier today and the performance was so terrible that I decided to just walk away for a day. Any ideas?

-Josh

Are you using a true multi-dimensional array or a jagged array? I know that LINQ works with only jagged arrays.

• The solution is to create a 2x2 mask from the original 2D array. Then you apply the same 2x2 mask against the mask. You keep iterating until you get all zeroes in the mask. The previous mask that contains some ones will give you all the positions of the squares, and the number of iterations that you ran indicates the size.

I have some code that does this. I'll post it later if I can figure out how to do it here.

• OK. Let's try snipplr.com.

http://bit.ly/iFcHn5

• @cbae: Wow, I can read it; there is a lot of funk with the code block mechanism on this site. I left the project on my other computer and wont be able to try it out until monday. I'll let you know how this works. Thanks for all the time and thought!

-Josh

• Okay, that's bizarre. The code block used to work fine for me, but now it's utterly broken.

• Wouldn't this be simpler to solve and write with the following Recursive Function?

```Module Module1

Sub Main()
Dim a()() As Boolean = {({True, True, True, False, True, True}),
({True, True, True, True, True, True}),
({True, True, True, True, True, True}),
({False, False, True, True, True, True}),
({False, False, True, True, True, True})}

Dim best As New xys(-1, -1, 0)
For y = 0 To 4
For x = 0 To 5
Dim s = a.LargestTrueSquare(x, 5, y, 4, 0)
If s > best.S Then best = New xys(x, y, s)
Next
Next

End Sub
Public Class xys
Protected _X As Integer
Protected _Y As Integer
Protected _S As Integer
Public Sub New(x, y, s)
_X = x : _Y = y : _S = s
End Sub
Public ReadOnly Property X As Integer
Get
Return _X
End Get
End Property
Public ReadOnly Property Y As Integer
Get
Return _Y
End Get
End Property
Public ReadOnly Property S As Integer
Get
Return _S
End Get
End Property
End Class

<Runtime.CompilerServices.Extension()>
Public Function LargestTrueSquare(mem()() As Boolean,
x As Integer, xm As Integer,
y As Integer, ym As Integer,
ByVal d As Integer) As Integer
Return If(x > xm OrElse y > ym OrElse Not mem(y)(x),
d,
Math.Min(mem.LargestTrueSquare(x + 1, xm, y, ym, d + 1),
mem.LargestTrueSquare(x, xm, y + 1, ym, d + 1)))
End Function

End Module
```

• My previous didn't work quite right. (It worked for the provided test data but not others),

Rewrote so it works know.

```  <Runtime.CompilerServices.Extension()>
Public Function BigSquare(ByVal mem()() As Boolean) As xys
Return mem.Select(Function(e, y) e.
Select(Function(e1, x) New xys(x, y, mem.SqrReach(x, y))
).
OrderByDescending(Function(e1) e1.S
).
First
).
OrderByDescending(Function(e1) e1.S).First
End Function

<Runtime.CompilerServices.Extension()>
Public Function SqrReach(mem()() As Boolean,
x As Integer,
y As Integer) As Integer
Dim ds = (From e In mem.Skip(y) Select e.Skip(x).TakeWhile(Function(ee) ee)).ToList
If ds.Count = 0 Then Return 0
Dim cc = ds.TakeWhile(Function(e) e.Count >= ds.First.Count).ToList
Return Math.Min(cc.Count, ds(0).Count)
End Function```

• With a tweak to the xys class, so it Implements IComparable(Of xys)

```  <Runtime.CompilerServices.Extension()>
Public Function BigSquare(ByVal mem()() As Boolean) As xys
Return mem.Select(Function(e, y) e.Select(Function(e1, x) New xys(x, y, mem.SqrReach(x, y))).Max).Max
End Function```

• Hey, somebody finally fixed this.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace C9Test
{
class Program
{
static void Main(string[] args)
{
int width = 6, length = 5;
int[][] arr = new int[length][];

arr[0] = new int[] { 1, 1, 1, 0, 1, 1 };
arr[1] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[2] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[3] = new int[] { 0, 0, 1, 1, 1, 1 };
arr[4] = new int[] { 0, 0, 1, 1, 1, 1 };

/*
//After run 1
{ 1, 1, 0, 0, 1, 0 }
{ 1, 1, 1, 1, 1, 0 }
{ 0, 0, 1, 1, 1, 0 }
{ 0, 0, 1, 1, 1, 0 }
{ 0, 0, 0, 0, 0, 0 }

//After run 2
{ 1, 0, 0, 0, 0, 0 }
{ 0, 0, 1, 1, 0, 0 }
{ 0, 0, 1, 1, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }

//After run 3
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 1, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }

//After run 4
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0 }

*/

int size = 1;
int maxlencheck = length;
int maxcolcheck = width;
do
{
var newarr = SetMask(arr, width, size);

var hasone = newarr.Count(y => y.Any(x => x == 1));
if (hasone == 0)
{
break;
}
else
{
size++;
arr = newarr;
maxlencheck = length - size;
maxcolcheck = width - size;
}
}
while (maxlencheck > 0 && maxcolcheck > 0);

if (size > 1)
{
var rowhasones = arr.Select((r, i) => new { Index = i, RowData = r })
.Where((r, i) => r.RowData.Any(x => x == 1))
.Select(r => r.Index);

foreach (var rowindex in rowhasones)
{
for (int i = 0; i <= maxcolcheck; i++)
{
if (arr[rowindex][i] == 1)
{
Console.WriteLine("{0:d}x{0:d} square @ ({1:d},{2:d})", size, rowindex, i);
}
}
}
}
}

static int[][] SetMask(int[][] arrSrc, int width, int offset)
{
var length = arrSrc.Length;
var maxlencheck = length - 1;
var maxcolcheck = width - offset;

var arrRet = new int[maxlencheck][];
for (int i = 0; i < maxlencheck; i++)
{
arrRet[i] = new int[maxcolcheck]; //default to zeroes
}

//Project to anonymous type to get array index
var rowhasones = arrSrc.Select((r, i) => new { Index = i, RowData = r })
.Where((r) => r.Index < maxlencheck && r.RowData.Any(x => x == 1))
.Select(r => r.Index)
.OrderBy(i => i);

foreach (var rowindex in rowhasones)
{

var currow = arrSrc[rowindex];
var nextrow = arrSrc[rowindex + 1];
for (int i = 0; i < maxcolcheck; i++)
{
if (currow[i] == 1 && currow[i + 1] == 1 && nextrow[i] == 1 && nextrow[i + 1] == 1)
{
arrRet[rowindex][i] = 1;
}
}
}
return arrRet;
}
}
}```

• By the way, my program will find all overlapping squares. So, if given a 6x5 array of all 1s:

```            arr[0] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[1] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[2] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[3] = new int[] { 1, 1, 1, 1, 1, 1 };
arr[4] = new int[] { 1, 1, 1, 1, 1, 1 };```

It will find two 5x5 squares: 1st one at (0,0) and 2nd one at (1,0).

• Thank you gods of the channel nine, for fixing the code doohickey. I'm still trying to see what approach works better on arrays of more than two million elements and will report back here with my progress.

-Josh

• @JoshRoss: 2 million elements? Yikes! What are the dimensions of this array? And how sparse are the trues? And does it have to be array (jagged or otherwise)? Can it be a collection of objects? In my code, I tried to do some opitimization by filtering the array using the LINQ Where() extension method, but you end up losing the array element index in the Select extension method, so it requires first projecting the outer array into an anonymous object with member holding the index and a member referencing the inner array, which creates some processing overhead.

My particular code can be further optimized by changing the upper bound of one of the for loops in the SetMask() on each subsequent call and by also using the element index in the Where() extension method. Each call essentially reduces the range of elements that need to be checked by one row and one column. Also, if you can use a collection of objects instead of a jagged array, you can further optimize the code by keeping track of the number trues in each row and storing it in a member property of the object. Then the Where() extension method can use this property insead of calling the Any() extension method on each inner array.