2D Pattern Matching

Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits.
For example, consider the following 2D matrix:
7283455864
6731158619
8988242643
3839505324
9509505813
3843845384
6473530293
7053106601
0834282956
4607924137

Assume we need to look for the following 2D pattern:
950
384
353

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            // Two-dimensional array.
            int[,] array2D = new int[,] 
            { 
                { 7, 2, 8, 3, 4, 5, 5, 8, 6, 4 }, 
                { 6, 7, 3, 1, 1, 5, 8, 6, 1, 9 }, 
                { 8, 9, 8, 8, 2, 4, 2, 6, 4, 3 }, 
                { 3, 8, 3, 9, 5, 0, 5, 3, 2, 4 },
                { 9, 5, 0, 9, 5, 0, 5, 8, 1, 3 },
                { 3, 8, 4, 3, 8, 4, 5, 3, 8, 4 },
                { 6, 4, 7, 3, 5, 3, 0, 2, 9, 3 },
                { 7, 0, 5, 3, 1, 0, 6, 6, 0, 1 },
                { 0, 8, 3, 4, 2, 8, 2, 9, 5, 6 },
                { 4, 6, 0, 7, 9, 2, 4, 1, 3, 7 }
            };
            
            // Two-dimensional pattern.
            int[,] array2DPattern = new int[,]
            {
                { 9, 5, 0 },
                { 3, 8, 4 },
                { 3, 5, 3 }
            };

            bool found = false;
            //Generate all possible 2D patterns of given dimension
            for(int i = 0; i <= array2D.GetLength(0) - array2DPattern.GetLength(0) && !found; i++)
            {
                for(int j = 0; j <= array2D.GetLength(1) - array2DPattern.GetLength(1); j++)
                {
                    //Console.Write(i + "," + j + " ");
                    int[,] array2DPattern1 = GetSubArray(array2D, i, j, array2DPattern.GetLength(0), array2DPattern.GetLength(1));
                    for (int k = 0; array2DPattern1 != null && k < array2DPattern1.GetLength(0); k++)
                    {
                        for (int l = 0; l < array2DPattern1.GetLength(1); l++)
                        {
                            Console.Write(array2DPattern1[k, l] + " ");
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine("----------------------------------------------------------");
                    if (Is2DArrayEqual(array2DPattern, array2DPattern1))
                    {
                        Console.WriteLine("Pattern Found!!!" + " at index position " + "(" + i + ", " + j + ")");
                        found = true;
                        break;
                    }
                }
            }
            if(!found)
            {
                Console.WriteLine("Pattern NOT Found!!!");
            }
        }

        //Method to check if the arrays are equal
        public static bool Is2DArrayEqual(int[,] array1, int[,] array2)
        {
            if(array1 == null || array2 == null || array1.GetLength(0) != array2.GetLength(0) || array1.GetLength(1) != array2.GetLength(1))
            {
                return false;
            }
            else
            {
                for(int i = 0; i < array1.GetLength(0); i++)
                {
                    for(int j = 0; j < array2.GetLength(1); j++)
                    {
                        if(array1[i, j] != array2[i, j])
                        {
                            return false;
                        }
                    }
                }
            }
            return true;
        }

        //Method to extract submatrix
        public static int[,] GetSubArray(int[,]array1, int startingRowIndex, int startingColIndex, int numberOfRows, int numberOfColumns)
        {
            if(numberOfRows <= 0 || numberOfColumns <= 0 || (startingRowIndex + numberOfRows > array1.GetLength(0)) || (startingColIndex + numberOfColumns > array1.GetLength(1)))
            {
                return null;
            }
            else
            {
                int[,] array2 = new int[numberOfRows, numberOfColumns];
                for(int i = startingRowIndex; i < startingRowIndex + numberOfRows; i++)
                {
                    for(int j = startingColIndex; j < startingColIndex + numberOfColumns; j++)
                    {
                        array2[i - startingRowIndex, j - startingColIndex] = array1[i, j];
                    }
                }
                return array2;
            }
        }
    }
}

Output
=======
7 2 8
6 7 3
8 9 8
----------------------------------------------------------
2 8 3
7 3 1
9 8 8
----------------------------------------------------------
8 3 4
3 1 1
8 8 2
----------------------------------------------------------
3 4 5
1 1 5
8 2 4
----------------------------------------------------------
4 5 5
1 5 8
2 4 2
----------------------------------------------------------
5 5 8
5 8 6
4 2 6
----------------------------------------------------------
5 8 6
8 6 1
2 6 4
----------------------------------------------------------
8 6 4
6 1 9
6 4 3
----------------------------------------------------------
6 7 3
8 9 8
3 8 3
----------------------------------------------------------
7 3 1
9 8 8
8 3 9
----------------------------------------------------------
3 1 1
8 8 2
3 9 5
----------------------------------------------------------
1 1 5
8 2 4
9 5 0
----------------------------------------------------------
1 5 8
2 4 2
5 0 5
----------------------------------------------------------
5 8 6
4 2 6
0 5 3
----------------------------------------------------------
8 6 1
2 6 4
5 3 2
----------------------------------------------------------
6 1 9
6 4 3
3 2 4
----------------------------------------------------------
8 9 8
3 8 3
9 5 0
----------------------------------------------------------
9 8 8
8 3 9
5 0 9
----------------------------------------------------------
8 8 2
3 9 5
0 9 5
----------------------------------------------------------
8 2 4
9 5 0
9 5 0
----------------------------------------------------------
2 4 2
5 0 5
5 0 5
----------------------------------------------------------
4 2 6
0 5 3
0 5 8
----------------------------------------------------------
2 6 4
5 3 2
5 8 1
----------------------------------------------------------
6 4 3
3 2 4
8 1 3
----------------------------------------------------------
3 8 3
9 5 0
3 8 4
----------------------------------------------------------
8 3 9
5 0 9
8 4 3
----------------------------------------------------------
3 9 5
0 9 5
4 3 8
----------------------------------------------------------
9 5 0
9 5 0
3 8 4
----------------------------------------------------------
5 0 5
5 0 5
8 4 5
----------------------------------------------------------
0 5 3
0 5 8
4 5 3
----------------------------------------------------------
5 3 2
5 8 1
5 3 8
----------------------------------------------------------
3 2 4
8 1 3
3 8 4
----------------------------------------------------------
9 5 0
3 8 4
6 4 7
----------------------------------------------------------
5 0 9
8 4 3
4 7 3
----------------------------------------------------------
0 9 5
4 3 8
7 3 5
----------------------------------------------------------
9 5 0
3 8 4
3 5 3
----------------------------------------------------------
Pattern Found!!! at index position (4, 3)
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s