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);