C# - Algorithm: AccountForEfficiencies()

Status: Running
vWorker link.
Competition start date: 2012.11.10
Competition end date: 2012.12.10
Download associated files from github (or fork the project)

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.11.11: Fixes to the unit test have been committed to github. (Thanks quicks01ver)
2012.11.12: New fixes to the unit test have been committed to github. (Thanks Moustafa)
2012.11.13: Fixes to the unit test have been committed to github. (Thanks quicks01ver)
2012.11.19: Added some Benchmarks and committed to github. Some submissions are now failing, please check your code against these benchmarks by running the unit tests.
2012.11.21: Fix to benchmarks committed to github. (Thanks thcristo)
2012.12.03: Added Performance results obtained with Nperf
2012.12.04: Updated Performance results (Removed memory plots)

Performance Results:

Click on the images to see the original size.

Introduction:

In the manufacturing industry we often have to schedule tasks that last for a certain duration.

Most of the time the assumption is the task is running at 100% efficiency.

This is not always the case, and the purpose of this competition is to account for periods of inefficiency ( less than 100%) or periods of super efficiencies (> 100%).

In other words the task can be affected by calendar periods that have different efficiencies. This will become clearer when looking at the examples below and the unit tests.

The purpose of this competition is to implement the AccountForEfficiences() method so that it passes all the unit tests defined at https://github.com/Orcomp/Orcomp/tree/AccountForEfficiencies/Orc.Tests/DateIntervalExtensionsAccountForEfficiencies

The winner of this competition will be chosen from the submissions that pass all unit tests, has the cleanest implementation and is fast (but not necessarily the fastest.)

Submissions will be open for review once the competition is completed.

There will be prize moneys for the 3 best submissions, which will be chosen at our discretion.
1st Prize: $300
2nd Prize: $100 (Paid as an instant bonus)
3rd Prize: $50 (Paid as an instant bonus)

In order to get the code, you can either download the attached zip file or fork the github project: https://github.com/Orcomp/Orcomp

Please only submit the DateIntervalExtensions.cs file.

Important Notice:

• More unit tests will be added, and some may be fixed during the length of the competition, so you must make sure you always have the latest code from the github repository.
• The winning code must pass all unit tests, even those that are added during the course of the competition.
• $10 will be awarded as an instant bonus to the first person who identifies a problem with a unit test. (i.e. $10 per unit test with a problem, but you have to be the first to report it by posting to https://groups.google.com/forum/#!forum/orcomps)
• $10 will be awarded as an intant bonus to anyone who submits a new unit test that deals a scenario that is not already covered by an existing unit test. (Again please post it on https://groups.google.com/forum/#!forum/orcomps)

Examples:

Here are a few examples which will explain what the method is supposed to do, but first here are a few conventions:

We will define efficiency intervals by a "pipe" at either end of the interval like this:

|------------------------|

We will define the duration of a task by "plus" signs at either end of the interval like this:

+-----------+

So if a task is meant to take one hour at 100% efficiency, the task will take one hour.

Example 1

        +----------+             Duration: 1 hour
|-----------------------------|  Efficiency: 100%

Result:

        +----------+            Duration: 1 hour

Example 2

        +----------+            Duration: 1 hour
|-----------------------------| Efficiency: 50%

Result:

        +--------------------+  Duration: 2 hours

Example 3

        +----------+            Duration: 1 hour
|-----------------------------| Efficiency: 200%

Result:

        +----+                  Duration: 0.5 hours

In the examples above we assumed the start time remained fixed. For this competition the AccountForEfficiency() method has a parameter which specifies whether the start or the end remain fixed.
If the end remained fixed then our examples would look like:
Example 4

        +----------+            Duration: 1 hour
|-----------------------------| Efficiency: 100%

Result:

        +----------+            Duration: 1 hour

Example 5

        +----------+            Duration: 1 hour
|-----------------------------| Efficiency: 50%

Result:

+-------------------+           Duration: 2 hours

Example 6

        +----------+            Duration: 1 hour
|-----------------------------| Efficiency: 200%

Result:

             +----+            Duration: 0.5 hours

The unit tests also cover the situation when an efficiency is 0%.

Where it becomes interesting is when the timeline has multiple efficiency intervals which may or may not overlap each other.

RULES:

• If efficiency intervals overlap then the one with the highest priority will be used for the calculation.
• If two efficiency intervals have the same priority the one with the lowest efficiency has precedence and will be used in the calculation.
• You are allowed 5 submissions.
• You are responsible to make sure your unit tests are in sync with https://github.com/Orcomp/Orcomp

C#, F# Algorithm: Faster than QuickSort Extended?

Status: Completed

vWorker link: C# or F# Algorithm: Faster than QuickSort?

Competition start date: 2012.10.03

Competition end date: 2012.10.16

Download associated files from github (or fork the project)

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

Introduction

The purpose of this competition is exactly the same as the one found here. So please read the details there. The only thing that has changed is the benchmark data, which is now a lot more realistic.

In order to participate in this competition you will need to download, clone or fork the Orcomp library on github, and work on the "FasterThanQuicksortExtended" branch.

Your code has to pass all the unit tests and the benchmark data is already in place. All you need to to is implement the GetSortedDateTimes() method in Orcomp\Extensions\DateRanceCollectionExtensions.cs file.

Once you are finished please only submit your implemented method GetSortedDateTimes() on vWorker.

Rules:

- There are none, as long as your code passes the unit test, it is a matter of coming up with the fastest implementation.

- All LINQ queries must be executed in the method body and cannot be deferred.

- The fastest code wins.

- Each contestant is allowed 5 entries.

C#, F# Algorithm: Faster than QuickSort?

Status: Completed

vWorker link: C# or F# Algorithm: Faster than QuickSort?

Competition start date: 2012.08.10

Competition end date: 2012.08.24

Download associated files (Version 1.5 with results)

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.08.10: Each competitor is allowed 5 entries.

2012.08.11: Notes on SD at the end of the post.

2012.08.12: More notes on SD at the end of the post.

2012.08.17: New ranking method explained at end of post.

2012.08.30: Tentative Leader Board posted. Follow the discusion on GoogleGroups 

2012.08.30: Updated download files with code for each participant

2012.10.03: Winner is "Zaher". Congratulations! The source code is now available on github

Final Leader Board:

1 - Zaher, AvgRatio: 18.167, SD: 0.804, WorstCase: 16.136
2 - Renze, AvgRatio: 16.415, SD: 0.036, WorstCase: 16.343
3 - V_Tom_R, AvgRatio: 14.073, SD: 0.114, WorstCase: 13.919
4 - SoftwareBender, AvgRatio: 12.829, SD: 0.058, WorstCase: 12.739
5 - c6c, AvgRatio: 12.526, SD: 0.069, WorstCase: 12.380
6 - ErwinReid, AvgRatio: 11.452, SD: 0.036, WorstCase: 11.372
7 - Mihai, AvgRatio: 10.425, SD: 3.642, WorstCase: 5.725
8 - MoustafaS, AvgRatio: 10.024, SD: 0.186, WorstCase: 9.761
9 - aus1, AvgRatio: 7.972, SD: 0.186, WorstCase: 7.489
10 - bawr, AvgRatio: 5.317, SD: 0.240, WorstCase: 4.835

There is quite a lot of difference between the tentative leader board and the final leader board due to the way the various submissions where run. Thanks go to Renze for pointing this out and providing the code to fix it.

Final tentative Leader Board:

1. bawr - AvgRatio: 23.303, SD: 0.062, WorstCase: 23.201

2. Zaher - AvgRatio: 17.245, SD: 0.556, WorstCase: 16.822

3. c6c - AvgRatio: 11.495, SD: 0.413, WorstCase: 10.428

4. SoftwareBender - AvgRatio: 10.259, SD: 0.033, WorstCase: 10.204

5. ErwinReid - AvgRatio: 9.879, SD: 0.052, WorstCase: 9.785

6. V_Tom_R - AvgRatio: 9.713, SD: 0.022, WorstCase: 9.666

7. Mihai - AvgRatio: 9.656, SD: 0.097, WorstCase: 9.425

8. Renze - AvgRatio: 9.219, SD: 0.303, WorstCase: 8.438

9. MoustafaS - AvgRatio: 9.069, SD: 0.368, WorstCase: 8.362

10. aus1 - AvgRatio: 5.025, SD: 0.025, WorstCase: 4.961

New Leader Board:

1. Zaher Al-Sibai - ratio: 13.846 (SD: 0.075) (Worst case: 13.742) entry 1

2. Renze - ratio: 11.870 (SD: 0.081) (Worst case: 11.768) entry: 5

3. bawr - ratio: 10.213 (SD: 0.070) (Worst case: 10.088) entry 1

4. Software_bender - ratio: 9.738 (SD: 0.068) (Worst case: 9.601) entry 2

5. Renze - ratio: 9.129 (SD: 0.074) (Worst case: 8.994) entry: 4
6. MoustafaS  - ratio: 9.107 (SD: 0.096) (Worst case: 8.996) entry: 4
7. Erwin Reid  - ratio: 7.957 (SD: 0.113) (Worst case: 7.787) entry: 2
8. aus1 - ratio: 4.956 (SD: 0.085) (Worst case: 4.765) entry: 4
9. V_Tom_R - ratio 3.643 (SD: 0.062) (Worst case: 3.498) entry: 2

Old Leader Board:

1. Software_bender - ratio: 7.165 (SD: 0.130) (Worst case: 7.008) entry 2
2. MoustafaS  - ratio: 7.085 (SD: 0.113) (Worst case: 6.950) entry: 3
3. Renze - ratio: 6.548 (SD: 0.063) (Worst case: 6.435) entry: 3
4. Renze - ratio: 5.907 (SD: 0.156) (Worst case: 5.731) entry: 2
5. aus1 - ratio: 4.100 (SD: 0.145) (Worst case: 3.891) entry: 4
6. MoustafaS - ratio: 3.833 (SD: 0.094) (Worst case: 3.744) entry: 2
7. V_Tom_R - ratio 3.392 (SD: 0.108) (Worst case: 3.203) entry: 2
8. V_Tom_R - ratio 3.271 (SD: 0.129) (Worst case: 3.164) entry: 1
9. Software_bender - ratio: 2.754 (SD: 0.121) (Worst case: 2.658) entry 1
10. aus1 - ratio: 2.537 (SD: 0.080) entry: 3
11. aus1 - ratio: 2.475 (SD: 0.076) entry: 2
12. MoustafaS - ratio: 2.396 (SD: 0.086)

13. Renze - ratio: 2.340 (SD: 0.074)

14. aus1 - ratio: 2.04 (SD: 0.11) entry: 1

Introduction:

The purpose of this competition is to extract the start and end times from a list of DateRanges (which has already been pre-sorted) as a sorted DateTime list.

A DateRange can be thought of as a period of time that has well defined start and end time. (Please have a look at the class Orcomp.Entities.DateRange to get a better understanding of how this class works.)

The DateRange class implements the IComparable Interface, such that the DateRanges with earliest start times come first.

If two DateRanges have the same start time, then the DateRange with the shortest duration comes first.

A pictural representation of a sorted list of DateRanges may look like this: (Each line represents a DateRange start and end time.)

+--------------------------------------+
          +--------+
          +-------------+
          +---------------------+
                +--+
                    +---------------------------------------------------------+
                               +------+

The simplest way to get a sorted list of DateTimes from a list of DateRanges is to use the following code:

In the example shown above the Sort() method is used to order the DateTime values. Internally Sort() uses a QuickSort implementation.

This approach does not take advantage of the fact that we already have a list of pre-ordered DateRanges.

Therefore the aim of this competition is to implement the GetSortedDateTimes() method in the Orcomp.Extensions.DateRangeCollectionExtensions.cs file, taking this fact into account.

The implementation must also pass the unit test defined in the Orcomp.Tests project defined in the DateRangeCollectionExtensionsTest.cs file.

Finally once you have an implementation that works you can run the Orcomp.Benchmarks project to find out if your code runs faster or slower than the standard implementation.

Ratios greater than one indicate your code runs faster than the standard implementation.

Rules:

- There are none, as long as your code passes the unit test, it is a matter of coming up with the fastest implementation.

- Your code will be benchmarked against the standard algorithm defined in the Orcomp.Benchmarks project.

- The fastest code wins.

Notes:

- A ranking of submitted solutions will be kept up to date at the top of this post. If you want to stay anonymous please let me know when you submit your code.

- Please only submit the DateRangeCollectionExtensions.cs file.

- As a guide the standard deviation after running the benchmark should be less than 0.15.

- For F# users please send me an F# file with the implementation in it.

Notes on SD:

- The Standard Deviation (SD) is only a number which indicates the consistency or reliability of your benchmark run. If the the time result for all 20 iterations of the benchmark are very similar then the SD will approach 0. If, on the other hand the time results vary a lot, the SD will approach 1.
- The SD is influenced by other processes running on your computer at the time you run the benchmark. You will see you will get a different SD value every time you run the benchmark, so just run it as many times as you need to get an average with an SD less than 0.15. (The lower the SD the better.)
- The average ratio value that people are getting on their computer is different from what I am getting on my computer. I am not sure why, but please do not be alarmed about this. Towards the end of this competition I will be comparing the top entries against each other.

More notes on SD:

- Even though it is not recommended collecting the garbage in general, it does help to do so before each stopwatch.Reset() in order to obtain more consistent results.
- As the code being submitted is getting faster and faster it is harder to keep the SD below 0.15, therefore the worst case ratio is also included in the ranking to give an appreciation of the  spread between the times of the various runs.
- I have also noticed that the ratios fluctuate most at the beginning of a benchmark and then become a lot more reliable towards the end, therefore I might change the calculation to only include the last 10 loops in the benchmark.
- Another approach may be to forget the SD and accept a benchmark such that:
worst case ratio > average ratio * 0.95
best case ratio < average ratio * 1.05
(i.e. we have a 5% window.) This is short of doing a full blown confidence or tolerance interval analysis, but is probably good enough for what we trying to achieve.

New ranking method:

The benchmark for 1,000,000 date ranges is run 20 times.
The QuickSort implementation times are recorded for each loop and the last 10 results are selected. Outlayers are removed and the average is calculated.
The competitors implementation times are also recorded for each loop and the last 10 results are selected. Outlayers are removed and the ratio (using the average value for the QuickSort) is calculated.
The Benchmark is run in detached debugger mode (CRL - F5).
The Benchmark data has NOT changed.

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.