Friday 8 June 2012

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!

Posted by at
Labels:

29 comments:

  1. Moustafa El-Sayed8 June 2012 at 18:22

    Can you give more details about the natural order and the order of lists, do you mean order in each list or order of the containing lists ?

    If you can explain example 3 it will be very good

    ReplyDelete
    Replies
    1. orc8 June 2012 at 22:29

      I have clarified example 3. If you look at List1 in Example 3 you could also have the following sequence (with "Gray" right at the end):

      Purple, Yellow, Orange, Green, Red, Black, Brown, Cyan, Gray

      But because Gray is in the first list it takes priority over elements in subsequent lists, so the correct order can only be:

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

      Delete
  2. angzam789 June 2012 at 05:48

    In test method 'CanWeave_CollectionOfLists_ReturnsCorrectSequence2' "Orange" is repeated twice. Is this output correct given that we need to produce a sorted list?

    If the output is correct, why is the second "Orange" entry necessary?

    ReplyDelete
    Replies
    1. orc9 June 2012 at 07:15

      That is a mistake. Orange should only be included once. I have fixed the test. Please see version 1.1 of the files.

      Delete
  3. Anton10 June 2012 at 10:47

    Test method CanWeave_SecondListIsNOTWeaveable_ReturnsFalse() checks only two lists. But we have to avoid loops at all. Maybe it's better to modify this test or to add another one, for instance:
    public void CanWeave_ThirdListIsNOTWeaveable_ReturnsFalse()
    {
    // Arrange
    var lw = new ListWeaver();
    var list1 = new List { "Blue", "Gray" };
    var list2 = new List { "Blue", "Orange", "Green" };
    var list3 = new List { "Green", "Blue" };

    // Act
    lw.Yarns.Add(list1);
    lw.Yarns.Add(list2);
    bool result = lw.CanWeave(list3);

    // Assert
    Assert.False(result);
    }

    ReplyDelete
    Replies
    1. orc10 June 2012 at 16:32

      Hi Anton,

      You are absolutely correct. That is the reason why I am encouraging competitors to submit unit tests as well. Please see the "Notes" section towards the end of the competition post.

      Delete
  4. Renze11 June 2012 at 03:55

    Another suggestion for a test case (not compiled, so there may be a typo). This test case is new because:
    1) list3 will weave with list1
    2) list3 will weave with list2, but
    3) list3 will not weave with list1 and list2 combined.

    Kind regards,
    Renze de Waal

    public void CanWeave_ThirdListIsNOTWeaveable_ReturnsFalse()
    {
    // Arrange
    var lw = new ListWeaver();
    var list1 = new List { "Blue", "Gray" };
    var list2 = new List { "Gray", "Orange" };
    var list3 = new List { "Orange", "Blue" };

    // Act
    lw.Yarns.Add(list1);
    lw.Yarns.Add(list2);
    bool result = lw.CanWeave(list3);

    // Assert
    Assert.False(result);
    }

    ReplyDelete
  5. Anton11 June 2012 at 10:37

    Hello!
    Could you explain the expected result of CanWeave_CollectionOfLists_ReturnsCorrectSequence3().
    Input lists are:

    var list0 = new List { "Beige" };
    var list1 = new List { "Yellow", "Orange", "Gray" };
    var list2 = new List { "Purple", "Yellow", "Green", "Red" };
    var list3 = new List { "Orange", "Red", "Cyan" };
    var list4 = new List { "Gold", "Silver", "Bronze" };
    var list5 = new List { "Yellow", "Brown", "Cyan" };

    and expected result is:
    "Beige", "Purple", "Yellow", "Orange", "Gray", "Green", "Red", "Brown", "Cyan", "Gold", "Silver", "Bronze"

    But sequence "Gold", "Silver", "Bronze" stands before "Yellow", "Brown", "Cyan".

    Maybe the correct result should be:
    "Beige", "Purple", "Yellow", "Orange", "Gray", "Green", "Red", "Gold", "Silver", "Bronze", "Brown", "Cyan"

    Thanks in advance!

    Regards,
    Anton

    ReplyDelete
    Replies
    1. orc11 June 2012 at 14:48

      The unit test solution is correct.

      List3 and List5 have the "Cyan" color in common. Since List4 comes after list3, and list4 has nothing in common with any of the other lists, its colors will be go after "Cyan".

      The correct sequence is: "Beige", "Purple", "Yellow", "Orange", "Gray", "Green", "Red", "Brown", "Cyan", "Gold", "Silver", "Bronze"

      Delete
    2. Anton13 June 2012 at 09:48

      I see. Thanks for the explanation!

      Where can I post my decision? I have an account on vWorker.com and posted the bid to start the competition. My vWorker.com account name is 'antklim'. Thanks in advance!

      Regards,
      Anton

      Delete
    3. orc13 June 2012 at 15:42

      All you need to do is go back to the page where you posted your bid on vWorker and upload the files you have changed. There should be something on the page that allows you to upload files. I will then be notified and can check your code.

      Delete
  6. Anton14 June 2012 at 12:27

    Hello!
    I've found one more case to check. We have to avoid the loop within the adding list. So, I've added one more test CanWeave_LoopInListIsNOTWeaveable_ReturnsFalse() to check such list: var list1 = new List { "Blue", "Gray", "Blue", "Orange" };

    ReplyDelete
  7. Moustafa El-Sayed17 June 2012 at 11:03

    Hi Ben,

    One question : What memory limit are you talking about?

    I managed to get it reduce all the time limits (for instance in one case it became 1 second instead of 160 seconds before!)

    But the last 2 cases crash out of memory here (may be because it's getting 1.5g memory out of 3g in this PC).

    I will improve it now before I submit the solution, but it will be better if you can tell me what is your memory limit.

    Thanks

    ReplyDelete
  8. orc18 June 2012 at 15:29

    I can't really say. There are some submissions that already pass the last two tests, and others will run out of memory, so there is a memory efficient solution.

    ReplyDelete
    Replies
    1. Moustafa El-Sayed18 June 2012 at 18:28

      And the time ?, my algorithms takes more than 8 minutes.

      Delete
  9. Rajesh Gautam21 June 2012 at 00:27

    A suggestion: It will be a good idea to share release mode binaries of submissions. This will help coder's to have evaluate/improve cycles at their end without waiting for inputs from you.

    ReplyDelete
    Replies
    1. Renze21 June 2012 at 13:53

      If this is done, some obfuscation tool will be needed. Otherwise, reverse engineering a .NET binary is much too easy.

      Delete
    2. Rajesh Gautam21 June 2012 at 23:48

      Hmm! Correct.

      Delete
  10. Rajesh Gautam21 June 2012 at 22:53

    This comment has been removed by the author.

    ReplyDelete
  11. Rajesh Gautam21 June 2012 at 23:25

    In Following Test: To preserve natural order, Green, Red of List4 should come after Bronze which is in List3, unlike what is mentioned in the test. Please clarify.

    public void CanWeave_CollectionOfLists_ReturnsCorrectSequence4()

    var list0 = new List { "Beige" };
    var list1 = new List { "Yellow", "Orange", "Gray" };
    var list2 = new List { "Yellow", "Brown", "Cyan" };
    var list3 = new List { "Gold", "Silver", "Bronze" };
    var list4 = new List { "Purple", "Yellow", "Green", "Red", "Black" };
    var list5 = new List { "Orange", "Red", "Cyan", "Aqua" };

    var correct = new List { "Beige", "Purple", "Yellow", "Orange", "Gray" ,"Brown", "Green", "Red", "Cyan", "Gold", "Silver", "Bronze", "Black", "Aqua" };

    ReplyDelete
    Replies
    1. Renze22 June 2012 at 01:31

      I hope you do not mind if I attempt to clarify. As I am also in this competition, this is my interpretation of the problem and not an authorative answer.

      In list5, Cyan is after Red. If you move Green and Red back, Cyan will move back as well. Cyan is in list2, so we don't move it back in favor of the items in list3.

      In general, to determine whether solution A is better than solution B:

      1) Create a list ORDEREDITEMS of all the items in the input lists, which:
      1A) contains all items in the input lists exactly once (duplicates are removed)
      1B) contains items in the order in which they first occur in the input lists. In this particular case, the list would be: Beige, Yellow, Orange, Gray, Brown, Cyan, Gold, Silver, Bronze, Purple, Green, Red, Black, Aqua.

      2) Find the first item in ORDEREDITEMS for which the index in solution A is different from the index in solution B. The solution for which the index is smallest is the best solution of the two.

      In this specific example, your suggested solution may be "Beige", "Purple", "Yellow", "Orange", "Gray" ,"Brown", "Gold", "Silver", "Bronze", "Green", "Red", "Cyan", "Black", "Aqua".

      The first item in ORDEREDITEMS for which the index differs is "Cyan". The index of "Cyan" in the "correct" list is smaller than the index of "Cyan" in your suggested solution.

      Good luck,

      Renze.

      Delete
    2. Rajesh Gautam22 June 2012 at 07:02

      Dear Renze,

      Thanks for the explanation.
      List5 cannot be weaved in the first 4 lists. After weaving first 4 lists, the Weaved list will be:
      "Beige", "Purple", "Yellow", "Orange", "Gray" ,"Brown", "Cyan", "Gold", "Silver", "Bronze", "Green", "Red", "Black"

      The natural order has to be preserved, so "Green" and "Red" will come after "Brown". Note that this weaved list has "Red" after "Cyan" in.

      Requirements says that in target usage that a list is checked for weavability (canWeave) before addition (Yarns.Add).

      Now look at List5: Which has "Orange", "Red", "Cyan", "Aqua". It has "Cyan" after "Red" which means is cannot be weaved with the previous weaved list. So after adding first four list, the CanWeave for List5 should return false.

      I hope my reasoning is clear.

      Cheers,
      gautam

      Delete
    3. Renze22 June 2012 at 14:41

      Dear Rajesh Gautam,

      I feel that I should leave the answer to this post to Ben. I do not agree with your interpretation of the requirements, but it is not up to me to determine this.

      Good luck with the competition.

      Cheers,
      Renze.

      Delete
    4. orc25 June 2012 at 14:46

      Renze is correct.

      When weaving yarns together you must always start from the individual yarns, and look at them as a whole.
      I am currently working on the submissions. Stay tuned to see what the winning solution is

      Delete
    5. Rajesh Gautam26 June 2012 at 00:51

      I believe the testcase CanWeave_CollectionOfLists_ReturnsCorrectSequence4 is incorrect because it does not preserve the natural order. As mentioned in my previous post, "Green" & "Red" cannot come before "Bronze". Please clarify.

      Delete
    6. orc26 June 2012 at 08:22

      The result shown in the test is correct.
      The yarns were purposely setup this way. The last list has "Cyan", which links to "Cyan" in list2.
      The last list also has red before cyan. so the Red in the last list will anchor the Red in list4.
      The important concept is that list2 and list5 have Cyan in common, which cause the other colours to come before bronze.

      Delete
    7. Rajesh Gautam26 June 2012 at 20:57

      var list3 = new List { "Gold", "Silver", "Bronze" };
      var list4 = new List { "Purple", "Yellow", "Green", "Red", "Black" };

      I am confused about the natural order mentioned in requirements, please clarify.

      From the above two lists: Can Green,Red come before Bronze by merging? Will that not breach the natural order of items? I believe the natural order should be preserved in the future merges also, or that is not a requirement?

      Delete
  12. Rajesh Gautam22 June 2012 at 07:13

    A potential test for others to verify.

    [TestMethod]
    public void FifthListIsNOTWeaveable_ReturnsFalse()
    {
    // Arrange
    var lw = new ListWeaver();
    var list0 = new List { "Beige" };
    var list1 = new List { "Yellow", "Orange", "Gray" };
    var list2 = new List { "Yellow", "Brown", "Cyan" };
    var list3 = new List { "Gold", "Silver", "Bronze" };
    var list4 = new List { "Purple", "Yellow", "Green", "Red", "Black" };
    var list5 = new List { "Orange", "Red", "Cyan", "Aqua" };


    // Beige
    // Yellow, Orange, Gray
    // Yellow, Borwn, Cyan
    // Gold, Silver, Bronze
    // Purple, Yellow, Green, Red, Black

    // Act
    lw.Yarns.Add(list0);
    lw.Yarns.Add(list1);
    lw.Yarns.Add(list2);
    lw.Yarns.Add(list3);
    lw.Yarns.Add(list4);
    bool result = lw.CanWeave(list5);
    Assert.False(result);
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)