ListWeaver - Adjacency Matrix

Status: Completed
vWorker link: C# Algorithm: Adjacency Matrix
Competition start date: 2012.06.27
Competition end date: 2012.07.10
Download associated files (version 1.4)

Please make sure to read the Welcome page for general competition guidelines.
If you would like to participate in this competition please register an account on vWorker.com

Update:

2012.07.09: Corrected Example 2. Added workings

2012.07.09: Added more explanation to the matrix approach, under the "Matrix representation" section.
2012.07.09: Updated files to version 1.4
2012.11.30: Looks like this problem should be easy to solve now with csparse library

This competition is based on the ListWeaver competition. The problem description, unit tests and benchmarks are exactly the same, however the solution has to use an adjacency matrix representation of the problem and find a transformation matrix which will return the correct result.

Some useful links are:

- Wikipeida - Adjacency matrix

- Search for Adjacency matrix and eigenvalues.

3rd party, open source .NET libraries can be used if required. If you do use a 3rd party library please let me know which one it is when submitting your solution.

Extra Example 1:

Input:
Purple
Green
Orange,Purple
Green,Purple

Result:
Green, Orange, Purple

Extra Example 2:

Input:
Blue
Bronze, Yellow, Purple
Black, Orange
Red, Blue, Gold
Silver, Blue
Bronze, Blue

Shown below is the working of the solution by adding one yarn at a time. When the final yarn "Bronze, Blue" is added, the "Bronze" colour gets promoted the first element, since "Bronze" already appears in the second list, therefore takes precedence over colours in subsequent lists.

Result:
Bronze, Red, Silver, Blue, Yellow, Purple, Black, Orange, Gold

Extra Example 3:

Input:
Blue
Bronze, Yellow, Purple
Black, Orange
Red, Blue, Gold
Silver, Blue

Result:
Red, Silver, Blue, Bronze, Yellow, Purple, Black, Orange, Gold

Matrix Representation:

If we look at example 2, and represent it in matrix form, we will get the following:

We obtain this matrix by taking the colours as they appear in each list but we remove duplicates.

The "1" value represents an edge connecting one colour to another. So we can see Bronze is connected to Blue in one list, and that Bronze is connected to Yellow in another list. Yellow in turn is connected to Purple. etc...

In order to get the correct sequence we process each column in order as they appear. We start with Blue.

If there are any "1"s in the column we process the rows in order and add the colour of the column at the end.

Which means that after column "Blue" we get:

Bronze, Red, Silver, Blue

We now move onto the second column "Bronze". There is nothing in this column and Bronze is already contained in the resulting list so we can skip it.

Column "Yellow" has a "1" on the "Bronze" row, but "Bronze" is already contained in the resulting list, so we add "Yellow" to the end of the list:

Bronze, Red, Silver, Blue, Yellow

Column "Purple" is similar. It has a "1" in the yellow row, but yellow is already contained in the resulting list so we just add Purple to the end:

Bronze, Red, Silver, Blue, Yellow, Purple

The "Black" column has no entries so "Black" simply gets added to the end of the list:

Bronze, Red, Silver, Blue, Yellow, Purple, Black

The "Orange" column has a "Black" entry, but black is already in the list, so add Orange to the end of the list:

Bronze, Red, Silver, Blue, Yellow, Purple, Black, Orange

The "Red" column has no entries but it is already contained in the list, so we can skip it.

The "Gold" column has a "Blue" entry, but "Blue" is already contained in the list, so Gold goes to the end of the list:

Bronze, Red, Silver, Blue, Yellow, Purple, Black, Orange, Gold

Finally we get to the "Silver" column, which has not entries and is already contained in the list, so the final results is:

Bronze, Red, Silver, Blue, Yellow, Purple, Black, Orange, Gold 

Reformatting the result in matrix form we get:

The aim of this competition is to find a transformation matrix which will take the first matrix shown above, and return an upper triangular matrix as illustrated here.

This is a typical matrix decomposition problem and must be solved using matrix functions. (such as inverse, transpose etc...)

ListWeaver - WINNER

The winning code is shown below:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Orcomp 
{ 
    public class ListWeaver<T>
    { 
        public ListWeaver() 
        { 
            Yarns = new List<IList<T>>(); 
        } 

        public List<IList<T>> Yarns { get; set; }

        public bool CanWeave(IList<T> yarn)
        { 
            if (yarn == null)
                return false;

            List<IList<T>> yarns = Yarns.ToList(); 
            yarns.Add(yarn); 

            if (Walk(yarns) != null)
                return true;
            else 
                return false;
        } 

        public List<T> Weave() 
        { 
            return Walk(Yarns); 
        } 

        private List<T> Walk(List<IList<T>> yarns)
        { 
            var edges = new Dictionary<T, HashSet<T>>(); 
            foreach (var yarn in yarns)
            { 
                for (int i = 1; i < yarn.Count; i++)
                { 
                    if (!edges.ContainsKey(yarn[i])) 
                        edges[yarn[i]] = new HashSet<T>(); 
                    edges[yarn[i]].Add(yarn[i - 1]); 
                } 
            } 

            var path = new List<T>(edges.Count); 
            var seen = new HashSet<T>(); 

            var valid = yarns.Where(yarn => yarn.Count > 0).Select(yarn => yarn.Last()).All(node => Walk(node, path, edges, seen));
            if (valid) 
                return path; 
            else 
                return null;
        } 

        private bool Walk(T root, List<T> path, Dictionary<T, HashSet<T>> edges, HashSet<T> seen_all)
        { 
            var seen_now = new HashSet<T>(); 
            var to_visit = new LinkedList<KeyValuePair<T, bool>>(); 
            to_visit.AddLast(new KeyValuePair<T, bool>(root, false)); 

            while (to_visit.Count > 0)
            { 
                var last = to_visit.Last.Value; 
                var node = last.Key; 
                var drop = last.Value; 
                to_visit.RemoveLast(); 

                if (drop) 
                { 
                    path.Add(node); 
                    seen_now.Remove(node); 
                    continue; 
                } 

                if (seen_now.Contains(node)) 
                    return false;

                if (seen_all.Contains(node)) 
                    continue; 

                seen_all.Add(node); 
                seen_now.Add(node); 

                to_visit.AddLast(new KeyValuePair<T, bool>(node, true)); 
                if (edges.ContainsKey(node)) 
                    foreach (var edge in edges[node].Reverse())
                        to_visit.AddLast(new KeyValuePair<T, bool>(edge, false)); 
            } 

            return true; 
        } 
    } 
}

Feedback and Improvement:

The winning code runs efficiently in O(V+E) and makes very good use of HashSets and Dictionaries. (i.e. the time it takes to solve all benchmark tests is the same whether the lists are reversed or not, and the last two highly connected graphs solve efficiently in the same amount of time.) Well Done!

There is actually not much I can think of to improve on the code, however I would like to introduce another approach and start a new competition  for anyone who can solve this problem efficiently using an adjacency matrix representation of the graph using sparse matrices.

Some preliminary work suggests that if the adjacency matrix can be transformed into an upper triangular matrix a solution exists to the ListWeaver problem.

The following wikipedia page is a good starting point:
- Wikipeida - Adjacency matrix

You are allowed to use 3rd party open source libraries to represent the sparse matrices, if required.

ListWeaver

Status: Completed - Winning code can be found here.
vWorker link: C# Algorithm: ListWeaver
Competition start date: 2012.06.09
Competition end date: 2012.06.23
Download associated files. (Version 1.4)

Please make sure to read the Welcome page for general competition guidelines.
If you would like to participate in this competition please register an account on vWorker.com

Update:

2012.06.09: Clarified Example 3. Also Note that all elements in the final sequence must be unique.
2012.06.09: Fixed error in unit tests. Uploaded new files version 1.1
2012.06.10: Added extra example5 and "Method Explanation" section. Added one of the secret tests to the public unit tests. Uploaded files are now version 1.2
2012.06.18: Updated competition with a benchmark project, which can be downloaded from the link above (Download associate files version 1.3). All the secret unit tests are also included. The best submissions so far run in O(V+E).
2012.07.09: Added "as much as possible" to the Rules section.
2012.07.09: Updated files to version 1.4. Added Renze's unit tests

Task:

Sort a collection of lists respecting their "natural order", as well as the order in which lists are processed. (i.e. elements in the first list take precedence over elements in the second list etc...)

Here are a few examples:

Example1:

List1: Green, Blue, Yellow

List2: Blue, Orange, Red

Result: Green, Blue, Yellow, Orange, Red. (Note that elements in List1 will take precedence on elements in List2.)

Example 2:

List1: Green, Blue, Yellow

List2: Blue, Green, Red

Result: Not possible to weave. since you have a circular reference between "Green" and "Blue" in List 1 and 2.

Example 3:

List1: Yellow, Orange, Gray

List2: Purple, Yellow, Green, Red

List3: Orange, Red, Cyan

List4: Black, Brown, Cyan

Result: Purple, Yellow, Orange, Gray, Green, Red, Black, Brown, Cyan.

List1:            Yellow, Orange, Gray
List2: Purple, Yellow,                       Green, Red
List3:                        Orange,                     Red,                       Cyan
List4:                                                                 Black, Brown, Cyan

Example 4:

List1: Yellow, Orange, Gray, Cyan

List2: Purple, Yellow, Red, Brown, Gray, Green

List3: Black, Gold

Result: Purple, Yellow, Orange, Red, Brown, Gray, Cyan, Green, Black, Gold

Note: Elements in List3 don't have a match, so they simply get appended to the end of the sequence.

Example 5:

List1: Beige
List2: Yellow, Orange, Gray
List3: Yellow, Brown, Cyan
List4: Gold, Silver, Bronze
List5: Purple, Yellow, Green, Red, Black
List6: Orange, Red, Cyan, Aqua
         

List1: Beige
List2:                        Yellow, Orange, Gray
List3:                        Yellow,                       Borwn,                   Cyan
List4:                                                                                                   Gold, Silver, Bronze
List5:             Purple, Yellow,                                  Green, Red                                            Black
List6:                                     Orange,                               Red, Cyan                                             Aqua

Result: Beige, Purple, Yellow, Orange, Gray, Brown, Green, Red, Cyan, Gold, Silver, Bronze, Black, Aqua

Method Explanation:

The "CanWeave()" method is used before adding a new list to the list of Yarns, to make sure the list can be weaved with the lists already contained in Yarns.

In other words the code would be used like:

if(listWeaver.CanWeave(newList))
{
       listWeaver.Yarns.Add(newList);
}

Rules:

The entries will be judged on (in no particular order):

- Simplicity and clarity

- Performance

This competition is based on topological sort, with the following restrictions:

- Each node in a list only has one descendant (except for the last element, which has none), and

- If there is a possible solution, only one sequence is valid. (i.e. The order in which the lists are added to the ListWeaver must be respected, as much as possible.)

Notes:

You can also submit your own unit tests, which will be used to test other entries. Which means if you know your code can handle a tricky situation, then you can submit a test to eliminate other entries.

You are only allowed 3 entries.

Good Luck!

Task Levels - WINNER

The winning code is shown below: 


There is a $100 prize for simplifying the code as well as implementing the points mentioned below.

Feedback and improvements:
The winning code passed all tests and actually gave better results on two of them. Well done!


All the tests and code can be found here.


The code correctly checks whether there is indeed a solution with the following code:

There is actually more to it. We also need to check that the rates for each tasks also balance out. For example if a producing task has a rate per hour of 10,000 and lasts one hour, and there is a consuming task with a rate per hour of -1,000 and lasts 10 hours. The quantities balance out, however if the MIN and MAX levels are respectively 0 and 2,000, the levels will still be breached.

Possible improvements would be:

- Include a check for the rates.

- Use Queues. One for producing tasks and another for consuming tasks if they need to be moved forward, then dequeue them in the correct order.

- Use an algorithm, which will get the first few tasks which balance out. (i.e. Get the firsts tasks such that 

ABS(SUM of producing tasks + SUM of consuming tasks + initialValue) < MAX level - MIN level. 

Once we have these tasks we need to check their rates will also balance out. If it does then we are guaranteed a solution for these tasks. We can then find their new starting times if there was a breach. Once the new start times are found, select some more tasks in the original collection such that 

ABS(SUM of producing tasks + SUM of consuming tasks + initialValue) < MAX level - MIN level, 

and repeat the process until the whole collection is processed.)

- Remove the need for a "private static" variable (which in this code is private static int MAX_ITER = 1000) (There shouldn't be a need for this as the problem is deterministic.)

Possible new methods which could be implemented are:

- GetBalancedTaskCollection(IEnumerable<ITask> taskCollection, double initialValue) : IEnumerable<ITask>

- AreRatesCompatible(IEnumerable<ITask> taskCollection): bool

Even if the rates for the first few tasks are not compatible, there still could be a solution to the problem. You will have to get the next few tasks that balance out, and then add them to the first subset of tasks, and then check AreRatesCompatible() again, until you have reached the end of the original task collection, at which point you can be certain there is no solution to the problem.