locked
Simple c# math puzzle RRS feed

  • Question

  • I'm trying to solve a simple math problem in c# but I'm not sure what is the best method to resolve it:

    • I have 3 datasets (each dataset represent a distinct day of data)
    • Each dataset contains 3 persons and 3 mac address
    • I'm trying to find which address belongs to each person

    Here is an example:

    1. Day 1 => Person: { Rick, Steve, Jo } Address: { 12, 25, 30 }
    2. Day 2 => Person: { Rick, Bob, Jo } Address: { 7, 25, 12 }
    3. Day 3 => Person: { Rick, Simon, Peter } Address {25, 9, 40}

    On paper, it is easy to know that the address of Steve is 30 because he is only in day 1 and the address 30 appear only in day 1. Using the same logic, I also know that the address of Rick is 25 and Jo is 12. We don't know the address of Simon and Peter, could be 9 or 40.

    Can I automate this kind of logic using Infer.Net?

    Thursday, April 16, 2015 2:08 PM

Answers

  • Is there any uncertainty in this problem? That is, why do you need to apply any machine learning? Or is it possible that there are errors in the input data?

    If not, consider the following simple solution. Create a mapping from a person's name to a set of allowed mac addresses: IDictionary<string, ISet<string>>. Iterate over the rows/days. The first time you see a new person name, assign his/her set of allowed mac addresses to the current set of 3. Any next time you encounter the same person, assign their set to the intersection of the current set and the new set of 3. So for example, Rick will start off with { 12, 25, 30 }. The next time this will be updated to { 12, 25, 30 } /\ { 7, 25, 12 } = { 12, 25 }, and the third time the set will be updated to { 12, 25 } /\ { 25, 9, 40 } = { 25 }.

    -Y-

    • Marked as answer by guejon Thursday, April 16, 2015 3:01 PM
    Thursday, April 16, 2015 2:47 PM

All replies

  • Is there any uncertainty in this problem? That is, why do you need to apply any machine learning? Or is it possible that there are errors in the input data?

    If not, consider the following simple solution. Create a mapping from a person's name to a set of allowed mac addresses: IDictionary<string, ISet<string>>. Iterate over the rows/days. The first time you see a new person name, assign his/her set of allowed mac addresses to the current set of 3. Any next time you encounter the same person, assign their set to the intersection of the current set and the new set of 3. So for example, Rick will start off with { 12, 25, 30 }. The next time this will be updated to { 12, 25, 30 } /\ { 7, 25, 12 } = { 12, 25 }, and the third time the set will be updated to { 12, 25 } /\ { 25, 9, 40 } = { 25 }.

    -Y-

    • Marked as answer by guejon Thursday, April 16, 2015 3:01 PM
    Thursday, April 16, 2015 2:47 PM
  • Thanks for your reply. You are right. Your solution is simple and seems to work really well.
    Thursday, April 16, 2015 2:59 PM
  • This solution, however, is incomplete - it won't figure out Jo, for whom it needs to take into account that Rick is { 25 } and reduce { 12, 25 } to { 12 }. Tom will give you the optimal algorithm.
    Thursday, April 16, 2015 5:04 PM
  • Infer.NET is very well suited to this kind of problem.  Here is the code:

            public void GuejonPuzzle()
            {
                string[] names = { "Rick", "Steve", "Jo", "Bob", "Simon", "Peter" };
                int[][] addressData = { new int[] { 12, 25, 30 }, new int[] { 7, 25, 12 }, new int[] { 25, 9, 40 } };
                string[][] personData = { new string[] { "Rick", "Steve", "Jo" }, new string[] { "Rick", "Bob", "Jo" }, new string[] { "Rick", "Simon", "Peter" } };
    
                int numPeople = names.Length;
                int maxAddress = 100;
                Range person = new Range(numPeople).Named("person");
                VariableArray<int> addressOfPerson = Variable.Array<int>(person).Named("addressOfPerson");
                addressOfPerson[person] = Variable.DiscreteUniform(maxAddress).ForEach(person);
                Range day = new Range(personData.Length).Named("day");
                VariableArray<int> instanceCount = Variable.Array<int>(day);
                instanceCount.ObservedValue = Util.ArrayInit(personData.Length, d => personData[d].Length);
                Range instance = new Range(instanceCount[day]);
                VariableArray<Vector> personDistribution = Variable.Array<Vector>(day);
                personDistribution.SetValueRange(person);
                personDistribution.ObservedValue = Util.ArrayInit(personData.Length, d =>
                    Vector.FromArray(Util.ArrayInit(numPeople, i => personData[d].Contains(names[i]) ? 1.0 : 0.0), Sparsity.Sparse));
                var observedAddress = Variable.Array(Variable.Array<int>(instance), day);
                observedAddress.ObservedValue = addressData;
                using (Variable.ForEach(day))
                {
                    using (Variable.ForEach(instance))
                    {
                        var selectedPerson = Variable.Discrete(personDistribution[day]);
                        using (Variable.Switch(selectedPerson))
                            observedAddress[day][instance] = Variable.Copy(addressOfPerson[selectedPerson]);
                    }
                }
    
                InferenceEngine engine = new InferenceEngine();
                var inferredAddressOfPerson = engine.Infer<IList<Discrete>>(addressOfPerson);
                for (int i = 0; i < inferredAddressOfPerson.Count; i++)
                {
                    Console.Write("{0}: ", names[i]);
                    var inferredAddress = inferredAddressOfPerson[i];
                    for (int j = 0; j < inferredAddress.Dimension; j++)
                    {
                        if (inferredAddress[j] > 1e-2)
                            Console.Write("{0} ", j);
                    }
                    Console.WriteLine();
                }
            }
    

    The result is:

    Rick: 25
    Steve: 30
    Jo: 12
    Bob: 7
    Simon: 9 40
    Peter: 9 40

    Thursday, April 16, 2015 5:41 PM
    Owner