Coffeehouse Thread

29 posts

A trivial question

Back to Forum: Coffeehouse
  • User profile image
    JoshRoss

    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

  • User profile image
    Dr Herbie

    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

  • User profile image
    evildictait​or

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

  • User profile image
    evildictait​or

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

  • User profile image
    evildictait​or

    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.

  • User profile image
    cbae

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

  • User profile image
    cbae

    ,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.

  • User profile image
    cbae

    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.

  • User profile image
    cbae

    OK. Let's try snipplr.com.

    http://bit.ly/iFcHn5

  • User profile image
    JoshRoss

    @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

  • User profile image
    Sven Groot

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

  • User profile image
    Adam​Speight2008

    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
    

  • User profile image
    Adam​Speight2008

    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

  • User profile image
    Adam​Speight2008

    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

  • User profile image
    cbae

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

  • User profile image
    cbae

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

  • User profile image
    JoshRoss

    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

  • User profile image
    cbae

    @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.

     

Comments closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.