Task Levels

Status: Completed
vWorker link: C# Algorithm, Task Levels
Competition start date: 2012.05.26
Competition end date: 2102.06.02 Extended till Monday 9:00AM 2012.06.04 Sydney time.
Download associated files. (Version 2.1)


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.05.29 - See the bottom of this post.
2012.05.30 - Just want to make it clear that the sequence must be preserved amongst a task type.
2012.05.31 - The last task in the input collection will never change.
2012.06.08 - The winning code can be found here.

Introduction:

In the process industry we often have to deal with tasks. A task can be either of two types. Either "producing" (i.e has a positive quantity), or "consuming" (i.e. has a negative quantity). A task also has a date range associated with it. (i.e. a task will start and finish at pre defined times.)

When we have a collection of tasks, we want to be able to keep track of the running quantities being produced or consumed.

The purpose of this competition is two fold:
- First you will have to implement an algorithm that determines whether a collection of tasks will stay within a certain range or not.
- If the level breaches the range, you have to return a collection of tasks that does not breach the range.

An illustration is shown below:

Requirements:

Write the code for:

- WillBreachMinLevel()

- WillBreachMaxLevel()

- TryToMakeTasksComply()

The first two are relatively easy the last method is more interesting. 

The stubs for these functions are found in the TaskCollectionExtensions.cs file.

The unit tests are defined in TaskCollectionExtensionTest.cs

Your tasks is to write the code to pass all tests defined in the file mentioned above. There are also a few secret tests to differentiate between competitors.

Assumptions:

- A collection of tasks can have multiple producing tasks and multiple consuming tasks.

Constraints:

- If a collection of tasks will go above the MAX level, only the producing tasks will move forward to try and keep the levels within the MIN-MAX range at all times. (The consuming tasks will stay where they are.)

- If a collection of tasks will go below the MIN level, only the consuming tasks will move forward to try and keep the levels within the MIN-MAX range at all times. (The producing tasks will stay where they are.)

- TryToMakeTasksComply() will return null if no suitable times can be found for the tasks so that the running level always stays in the range.
If a solution exists, the method will return a collection such that the running level always stays in the range and the sum of the starting times of all tasks is minimised. (i.e. only move a producing or consuming task forward to fit in the range ... but not more than is necessary.)

Hints:

The classes Task, DateRange and their extensions may have useful methods. (see the "Extensions" folder in the project.)

Notes:

If you have any questions, please post them as comments to this post. Please do not ask us questions on vWorker, as we do not have time to answer all of them individually.

The downloadable files also include a project called TaskLevelPlotter which may assist you in visualising the running levels in a given collection. (You need to have MSChart installed for .NET 3.5)
A picture is show below:

Finally, please check this post regularly as updates will be posted on this blog post, or in the comments.

All the best!

===============================================
2012.05.29

This is a response to Egor's comments below. Using the data he provided we obtain the following plot:

The solution the algorithm should provide is shown below:

The data for the correct collection is:

correctCollection.Add(task1.ChangeTimes(t5));

correctCollection.Add(task2.ChangeTimes(t6));

correctCollection.Add(task3.ChangeTimes(t7));

correctCollection.Add(task4);

correctCollection.Add(task5);

correctCollection.Add(task6);

correctCollection.Add(task7);

Combine() (or Collapse) DateRanges - WINNER

The winning code for the combine competition is shown below:

Feedback and improvements: 

During the course of the competition we made some changes to the libraries.
Changed the Combine() method to Collapse().
In the DateRange class the Overlap() method was changed to GetOverlap() and a new Overlaps() method was created, which returns a boolean.

Improvements on the winning code are only minor:
- Added a null check at the start
- Changed the code to use the new Overlaps() method

Possible Improvements:
- Would be great if there was a way of only traversing the collection of tasks once (after it has been sorted).
(There is a way.... We are leaving a $50 US for the next 2 people who can traverse the collection once and still get the same result.)

Combine() (or Collapse) DateRanges

Status: Completed
Competition start date: 2012.05.21
Competition end date: 2102.05.24
Download associated files. (once you are on the google docs page, click on the file tab and then download CTR + S)

Introduction:

In the manufacture or process industry we often have to deal with operations (or tasks) that have a certain duration.
The duration represents the time it takes to produce or consume a certain amount of product (i.e. quantity).

The aim of this competition is to implement an algorithm which will combine (or collapse) a collection of tasks that have date ranges that overlap. In other words tasks that overlap in time may have to be spliced, so that their overlapping parts are combined and their respective rates added up.

Please see below for an illustration of how the method should work as well as the existing classes which will assist you in writing your code.

======================================================================

UPDATE: 2012.05.24

Submissions:

- WINNER

Thank you to all the other contestants.

Outcome of the competition on the existing library:

- Renamed the Combine() method to Collapse()

- In the DateRange class, the method Overlap() has been renamed to GetOverlap(), and a new Overlaps() method was written which only returns a boolean.

- The DateRange class is now immutable, and implements IEquality, IComparable, and overloads the "==" and "!=" operators

- The Task class is now immutable and implements IEquality (Decided against implementing IComparable as there are too many variables. Most of the time defaulting to the DateRange comparer will suffice.)