CODEWITHSUNDEEP
arraysalgorithmmultidimensional-array
Lg102
Lg102

Reputation: 4898

Finding blocks in arrays

I was looking over some interview questions, and I stumbled onto this one:

There's an m x n array. A block in the array is denoted by a 1 and a 0 indicates no block. You are supposed to find the number of objects in the array. A object is nothing but a set of blocks that are connected horizontally and/or vertically.

eg

0 1 0 0
0 1 0 0
0 1 1 0
0 0 0 0
0 1 1 0

Answer: There are 2 objects in this array. The L shape object and the object in the last row.

I'm having trouble coming up with an algorithm that would catch a 'u' (as below) shape. How should i approach this?

0 1 0 1
0 1 0 1
0 1 1 1
0 0 0 0
0 1 1 0

Upvotes: 7

Views: 3052

Answers (7)

גלעד ברקן
גלעד ברקן

Reputation: 23955

My two cents (slash) algorithm:

1. List only the 1's.

2. Group (collect connected ones).

In Haskell:

import Data.List (elemIndices, delete) 

example1 =
  [[0,1,0,0]
  ,[0,1,0,0]
  ,[0,1,1,0]
  ,[0,0,0,0]
  ,[0,1,1,0]]

example2 =
  [[0,1,0,1]
  ,[0,1,0,1]
  ,[0,1,1,1]
  ,[0,0,0,0]
  ,[0,1,1,0]]

objects a ws = solve (mapIndexes a) [] where
  mapIndexes s = 
    concatMap (\(y,xs)-> map (\x->(y,x)) xs) $ zip [0..] (map (elemIndices s) ws)
  areConnected (y,x) (y',x') =
    (y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1)
  solve []     r = r
  solve (x:xs) r =
    let r' = solve' xs [x]
    in solve (foldr delete xs r') (r':r)
  solve' vs r =
    let ys = filter (\y -> any (areConnected y) r) vs
    in if null ys then r else solve' (foldr delete vs ys) (ys ++ r)

Output:

*Main> objects 1 example1
[[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1085360 bytes)

*Main> objects 1 example2
[[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]]
(0.01 secs, 1613356 bytes)

Upvotes: 1

comingstorm
comingstorm

Reputation: 26107

I would use a disjoint-set datastructure (otherwise known as union-find).

Briefly: for each connected component, build an "inverse tree" using a single link per element as a "parent" pointer. Following the parent pointers will eventually find the root of the tree, which is used for component identification (as it is the same for every member of the connected component). To merge neighboring components, make the root of one component the parent of the other (which will no longer be a root, as it now has a parent).

Two simple optimizations make this datastructure very efficient. One is, make all root queries "collapse" their paths to point directly to the root -- that way, the next query will only need one step. The other is, always use the "deeper" of the two trees as the new root; this requires a maintaining a "rank" score for each root.

In addition, in order to make evaluating neighbors more efficient, you might consider preprocessing your input on a row-by-row basis. That way, a contiguous segment of 1's on the same row can start life as a single connected component, and you can efficiently scan the segments of the previous row based on your neighbor criterion.

Upvotes: 1

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

This works in C#

    static void Main()
    {
        int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } };
        Console.WriteLine(GetNumber(array));
        Console.ReadKey();
    }

    static int GetNumber(int[][] array)
    {
        int objects = 0;
        for (int i = 0; i < array.Length; i++)
            for (int j = 0; j < array[i].Length; j++)
                if (ClearObjects(array, i, j))
                    objects++;
        return objects;
    }

    static bool ClearObjects(int[][] array, int x, int y)
    {
        if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false;
        if (array[x][y] == 1)
        {
            array[x][y] = 0;
            ClearObjects(array, x - 1, y);
            ClearObjects(array, x + 1, y);
            ClearObjects(array, x, y - 1);
            ClearObjects(array, x, y + 1);
            return true;
        }
        return false;
    }

Upvotes: 2

Pablo Francisco P&#233;rez Hidalgo
Pablo Francisco P&#233;rez Hidalgo

Reputation: 27702

I would use Disjoint sets (connected components).

At the begining, each (i,j) matrix element with value 1 is one element set itself.

Then you can iterate over each matrix element and for each element (i,j) you should join each adjacent position set {(i+1,j),(i-1,j),(i,j+1),(i,j-1)} to (i,j) set if its value is 1.

You can find an implementation of disjoint sets at Disjoint Sets in Python

At the end, the number of diffrent sets is the number of objects.

Upvotes: 1

thegrinner
thegrinner

Reputation: 12243

One approach would use Flood Fill. The algorithm would be something like this:

for row in block_array:
    for block in row:
        if BLOCK IS A ONE and BLOCK NOT VISITED: 
            FLOOD_FILL starting from BLOCK

You'd mark items visited during the flood fill process, and track shapes from there as well.

Upvotes: 3

iluxa
iluxa

Reputation: 6969

Something like this should work:

  1. while array has a 1 that's not marked:
    1. Create a new object
    2. Create a Queue
    3. Add the 1 to the queue
    4. While the queue is not empty:
      1. get the 1 on top of the queue
      2. Mark it
      3. Add it to current object
      4. look for its 4 neighbors
      5. if any of them is a 1 and not marked yet, add it to queue

Upvotes: 0

masotann
masotann

Reputation: 911

Why not just look at all the adjacent cells of a given block? Start at some cell that has a 1 in it, keep track of the cells you have visited before, and keep looking through adjacent cells until you cannot find a 1 anymore. Then move onto cells that you have not looked yet and repeat the process.

Upvotes: 0

Related Questions