Find distinct versions in a list of versions with wildcards included


Category: Data Structure And Algorithms Tags: C#

Hi,

    I came across a requirement in my office where we have versions in format like 1.1, 2.0.0.0, 1.*, 3.4.* etc. here 1.* includes all the version from 1.0-1.99 similarly 3.4.* includes all the versions from 3.4.0-3.4.99. We can have maximum of 4 parts in version.
Now I have given a list of versions and I have to write a function which returns distinct versions from list. Suppose the list is given to me is:

1.*

1.1.7

2.2

2.2

2.2

2.2.2

2.3.*

3.1

3.1.*

3.5.2

7.0.0.0
And output should be:

1.*        -> 1.* and 1.1.7 are included in 1.*

2.2       -> 2.2 and 2.2 are duplicates so added only one entry

2.2.2    -> 2.2.2 is only distinct version

2.3.*     -> 2.3.* is only distinct version

3.1.*     -> 3.1.* and 3.1 is included in 3.1.*

3.5.2    -> 3.5.2 is only distinct version

7.0.0.0 -> 7.0.0.0 is only distinct version

Thanks in advance.


Like 0 People
Asked on 12 April 2020
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 135
Questions: 12
Given Best Solutions: 12 *

Answers:

Nikhil Joshi

I have found the answer myself, I have used divide method to split the problem and solved it. Let's see how I solved this. Look at two versions below:
 versions
In above picture we can see two versions 1.1.* and 1.1, we know 1.1 is part of 1.1.* since first two parts of versions are same and the third one is * in one of them so distinct version out of above two is 1.1.* . Now similarly any version like 1.1.3.4, 1.1.2.4, 1.1.3 all would come under 1.1.* . In above picture we have columns 0,1,2 which are indexes of version parts. We will follow same in our logic.


Lets write a function as below.

/// <summary>
/// Returns distinct versions
/// </summary>
/// <param name="versionsSplit">Splitted Versions</param>
/// <param name="versions">Versions as string</param>
/// <param name="min">min row index</param>
/// <param name="max">max row index</param>
/// <param name="column">column in row(version part)</param>
/// <param name="distinctVersions">Distinct versions list</param>
static void GetDistinctVersions(string[][] versionsSplit, string[] versions, int min, int max, int column, List<string> distinctVersions)
{
    //if min and max is same then only one version is available to add in list
    if (min == max)
    {
        distinctVersions.Add(versions[min]);
        return;
    }

    //Assuming version can have maximum 4 parts i.e. a.b.c.d
    //if column is 0 then version part is a
    if (column < 4)
    {
        string lastVersionPart = ((versionsSplit[min].Length - 1) < column) ? "none" : versionsSplit[min][column];
        int lastVersionRow = min;

        //going over all rows
        for (int row = min; row <= max; row++)
        {
            string versionPart = ((versionsSplit[row].Length - 1) < column)? "none" : versionsSplit[row][column];

            //if version has * means all the versions are included in wildcart
            if (versionPart == "*")
            {
                distinctVersions.Add(versions[row]);
                return;
            }

            //partitioning rows i.e. {1.2, 1.3 3.4} => {1.2, 1.3}, {3.4}
            if (lastVersionPart != versionPart)
            {
                //recursive call by clustering similar versions i.e. 1.2, 1.3
                GetDistinctVersions(versionsSplit, versions, lastVersionRow, row - 1, column + 1, distinctVersions);
                lastVersionPart = versionPart;
                lastVersionRow = row;
            }
        }
        //last cluser in list
        if (lastVersionRow != min)
            GetDistinctVersions(versionsSplit, versions, lastVersionRow, max, column + 1, distinctVersions);
        else                    //if all the versions are same i.e 1.1, 1.1, 1.1 then only take first one
            GetDistinctVersions(versionsSplit, versions, min, min, column + 1, distinctVersions);
    }
}

Call above method from main method.

static void Main(string[] args)
{
    List<string> distinctVersions = new List<string>();

    string[] versions = new string[] { "1.*", "3.1", "2.3.*", "3.1.*", "3.5.2", "2.2", "2.2", "2.2", "1.1.7", "7.0.0.0", "2.2.2" };
    //Sorting versions
    Array.Sort(versions);

    //Splitting versions. i.e. 1.0.0 in {1, 0, 0}
    string[][] versionsSplit = new string[versions.Length][];
    for (int i = 0; i < versionsSplit.Length; i++)
    {
        string[] versionSplit = versions[i].Split(".");
        versionsSplit[i] = versionSplit;
    }

    //Printing all versions
    Console.WriteLine("All versions:");
    foreach (string version in versions)
        Console.WriteLine(version);

    //Calling method
    GetDistinctVersions(versionsSplit, versions, 0, versions.Length - 1, 0, distinctVersions);

    //Printing distinct versions
    Console.WriteLine("Distinct versions:");
    foreach (string version in distinctVersions)
        Console.WriteLine(version);

    Console.ReadLine();
}

Output

All versions:

1.*

1.1.7

2.2

2.2

2.2

2.2.2

2.3.*

3.1

3.1.*

3.5.2

7.0.0.0

Distinct versions:

1.*

2.2

2.2.2

2.3.*

3.1.*

3.5.2

7.0.0.0

Like 1 Person on 12 April 2020

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x