7
\$\begingroup\$

Problem Statement

Given a list of items each having a type associated with it, group them by the below mentioned rule

  • The list should not contain consecutive items that violate the Group setting. For example. An item of "Type1" can have a group setting of 3. This means that there cannot be more than 3 consecutive items of "Type1"
  • Any items that violate the group setting (mentioned above) should be moved down the collection. The position of insertion is determined by the Skip setting for that type. For example, an item of "Type 1" can have a group setting of 3 and a skip setting of 2. This means that when we encounter more than 3 consecutive items of "Type 1" then the next available point of insertion can only be after two items (Skip = 2) of type that is not of type "Type 1"
  • Each item also has a weight associated with it. While moving down items by the above rule, ensure that weighting is respected except in cases where you have to break items because of grouping rule.

Models

public class Setting
    {
        public string Id { get; set; }
        public int GroupSize { get; set; }
        public int Skip { get; set; }
    }

    public class Entity
    {
        public string Id { get; set; }
        public string Type { get; set; }
        public int Skip { get; set; }
        public double Weight { get; set; }
    }
    public class TimelineViewModel
    {
        public TimelineViewModel()
        {
            this.Items = new List<Entity>();
        }

        public string SnapshotId { get; set; }
        public IList<Entity> Items { get; set; }
        public IList<Entity> UnmatchedItems { get; set; }
    }

Grouping Class

public class GroupingHelper
{
    private static Dictionary<string, int> GroupSizes;

    private List<Setting> settings;
    private List<Entity> input = new List<Entity>();
    private List<Entity> temp = new List<Entity>();
    private List<Entity> output = new List<Entity>();

    //Setting class. Contains group size for each type
    public GroupingHelper(List<Setting> systemSettings)
    {
        settings = systemSettings;
        GroupSizes = new Dictionary<string, int>();
        for (int i = 0; i < settings.Count; i++)
        {
            GroupSizes.Add(settings[i].Id, settings[i].GroupSize);
        }
    }

    public TimelineViewModel RearrangeTimeline(TimelineViewModel param)
    {
        try
        {
            input = new List<Entity>(param.Items);
            temp = new List<Entity>();
            output = new List<Entity>();
            string previous = "";
            while (input.Count != 0)
            {
                Entity item = input[0];
                var temp_item = temp.Where(x => (x.Skip <= 0) || (x.Type == item.Type && x.Weight >= item.Weight)).OrderByDescending(y => y.Weight).FirstOrDefault();
                if (temp_item != null)
                {
                    if (Validate(temp_item, ref previous))
                    {
                        if (temp_item.Type != previous)
                        {
                            Reset();
                        }
                        previous = temp_item.Type;
                        temp_item.Id = temp_item.Id + " - G"; //- G appeneded only to indicate this item was moved down
                        Add(temp_item);
                        temp.Remove(temp_item);
                        continue;
                    }
                }
                if (Validate(item, ref previous))
                {
                    if (item.Type != previous)
                    {
                        previous = item.Type;
                        Reset();
                    }
                    Add(item);
                }
                else
                {
                    previous = item.Type;
                    Setting setting = settings.Where(c => c.Id.Equals(item.Type)).FirstOrDefault();
                    item.Skip = setting.Skip;
                    temp.Add(item);
                    input.Remove(item);
                }

            }
            return new TimelineViewModel()
            {
                Items = output,
                SnapshotId = param.SnapshotId,
                UnmatchedItems = temp
            };
        }
        catch (Exception ex)
        {
            throw;
        }
        finally
        {
            Reset();
        }
    }

    #region Private Methods
    private void Add(Entity temp_item)
    {
        //decrement skip
        for (int i = 0; i < temp.Count; i++)
        {
            var k = temp[i].Skip--;
        }
        output.Add(temp_item);
        GroupSizes[temp_item.Type]--;
        input.Remove(temp_item);
    }

    private bool Validate(Entity entity, ref string previous)
    {
        if (entity.Type != previous)
        {
            return true;
        }
        if (GroupSizes[entity.Type] <= 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    private void Reset()
    {
        GroupSizes = new Dictionary<string, int>();
        for (int i = 0; i < settings.Count; i++)
        {
            GroupSizes.Add(settings[i].Id, settings[i].GroupSize);
        }
    }

    #endregion
}

Test Case

[TestMethod()]
public void RearrangeTimelineTest()
{
    List<Setting> setting = new List<Setting>() {
        new Setting() { Id="Type1", GroupSize = 3, Skip =2 },
        new Setting() { Id="Type2", GroupSize = 2, Skip =1 },
        new Setting() { Id="Type3", GroupSize = 1, Skip =1 },
        new Setting() { Id="Type4", GroupSize = 3, Skip =2 }
    };
    TimelineViewModel viewModel = new TimelineViewModel();
    viewModel.SnapshotId = "test_id";
    viewModel.Items = new List<Entity>() {
        new Entity() { Id = "1", Type = "Type1", Weight = 100 },
        new Entity() { Id = "2", Type = "Type1", Weight = 90 },
        new Entity() { Id = "3", Type = "Type2", Weight = 80 },
        new Entity() { Id = "4", Type = "Type2", Weight = 70 },
        new Entity() { Id = "5", Type = "Type2", Weight = 60 },
        new Entity() { Id = "6", Type = "Type2", Weight = 50 },
        new Entity() { Id = "7", Type = "Type3", Weight = 40 },
        new Entity() { Id = "8", Type = "Type3", Weight = 30 },
        new Entity() { Id = "9", Type = "Type4", Weight = 20 },
        new Entity() { Id = "10", Type = "Type3", Weight = 10 }
    };
    GroupingHelper g = new GroupingHelper(setting);
    TimelineViewModel output = g.RearrangeTimeline(viewModel);
    //This is how the final result would look
    List<Entity> output_items = new List<Entity>() {
        new Entity() { Id = "1", Type = "Type1", Weight = 100 },
        new Entity() { Id = "2", Type = "Type1", Weight = 90 },
        new Entity() { Id = "3", Type = "Type2", Weight = 80 },
        new Entity() { Id = "4", Type = "Type2", Weight = 70 },
        new Entity() { Id = "7", Type = "Type3", Weight = 40 },
        new Entity() { Id = "5", Type = "Type2", Weight = 60 },
        new Entity() { Id = "6", Type = "Type2", Weight = 50 },
        new Entity() { Id = "8", Type = "Type3", Weight = 30 },
        new Entity() { Id = "9", Type = "Type4", Weight = 20 },
        new Entity() { Id = "10", Type = "Type3", Weight = 10 }
    };

    CollectionAssert.AreEqual(output.Items.Select(x=>x.Id).ToList(), output_items.Select(x => x.Id).ToList());
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Nice first question. Hopefully you will get some good reviews. \$\endgroup\$ – Heslacher Aug 8 '16 at 9:04
  • \$\begingroup\$ It looks like the expected result is in the same order as the initial input of viewModel.Items. How can you tell the sort worked? \$\endgroup\$ – radarbob Aug 8 '16 at 17:29
2
\$\begingroup\$

Boolean overcomplication

Overcomplicating boolean expression is a very common beginner mistake, you can return boolean values directly without if statements:

private bool Validate(Entity entity, ref string previous) 
{ 
    return (entity.Type != previous) && (GroupSizes[entity.Type] > 0);
}

The code now has a better signal (information) / noise (sintactic / mechanical) ratio.

Duplication

GroupingHelper and Reset share an identical block of code, you should remove it from the former adding a call to the latter.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.