A trivial question

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.

8 hours ago,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.