Cogslave Cogslave - 18 days ago 6
C# Question

Algorithm to match grids by the pattern of distinct cell contents

I am searching for an algorithm to match equal sized grids on the pattern of distinct cell contents, not the actual cell values themselves.
Grids would match on cells the having the same values at the same positions as possibly different values at the same positions within the other grid.

Examples:

A sucessful match:
Grid A:

0 1

3 0

Grid B:

25 17

23 25

Non matching grids:
Grid A:

0 1

3 0

Grid B:

25 17

23 17

Answer

I assume the pattern shape you refer to means having the same values within a grid at the same positions as possibly different values at the same positions within the pattern grid.

You can easily solve this problem by creating a pattern string representing a pattern in a grid by a string of characters. To create this string, we go through the grid. When we find a new value we have never seen before, we assign a new character to that value. When we find a value we have seen before, we use the character assigned to that value before.

So we get a string of characters from A to P (max 16 different values in the grid as specified).

In the examples in your question, both grids will produce the string "ABCA".

You can easily see whether two grids have the same pattern by comparing the pattern strings generated for the grids.

Here is a simple function to create such a pattern string:

// Calculates a code string representing the pattern in a grid 
// by a string of characters from A to P.
public static string CalculatePatternSignature(IEnumerable<IEnumerable<int>> grid)
{
    string result = "";

    // Here we remember what number represents what letter in the pattern
    Dictionary<int, char> symbolMap = new Dictionary<int, char>();


    // Going row by row and then column by column
    // we look at each number from top left to bottom right
    foreach (var row in grid)
    {
        foreach(var cell in row)
        {
            // For each number we try to map it to a letter from
            // A to P (16 different values possible)
            char mappedChar;

            // We look whether we have seen the integer value before
            // If yes, we can read its assigned mapped letter from the dictionary
            if (!symbolMap.TryGetValue(cell, out mappedChar))
            {
                // We haven't seen that integer value before,
                // so use the next free letter and map the 
                // value to that letter
                mappedChar = (char)((byte)'A' + symbolMap.Count());
                symbolMap.Add(cell, mappedChar);

                if (symbolMap.Count() > 16)
                {
                   throw new Exception("We have found more than 16 different values in the grid");
                }
            }

            // Add the mapped letter for the integer value in the current cell
            // to the code string
            result += mappedChar;
        }
    }

    return result;
}

Sample code to demonstrate that they produce the same pattern string:

var samplePattern = new int[][] {
    new int[] {0, 1},
    new int[] {3, 0}
};

var sampleInput = new int[][] {
    new int[] {25, 17},
    new int[] {23, 25}
};

textBox1.AppendText("samplePattern: " + CalculatePatternSignature(samplePattern) + Environment.NewLine);
textBox1.AppendText("sampleInput: " + CalculatePatternSignature(sampleInput) + Environment.NewLine);

Produces the following output:

samplePattern: ABCA
sampleInput: ABCA

Comments