Skip to content

Instantly share code, notes, and snippets.

@ahanoff

ahanoff/gist:a79e58018ff714a34a93e7387ca8f861

Created September 26, 2017 15:54
Show Gist options
  • Save ahanoff/a79e58018ff714a34a93e7387ca8f861 to your computer and use it in GitHub Desktop.
Save ahanoff/a79e58018ff714a34a93e7387ca8f861 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ahanoff created this gist Sep 26, 2017.
    216 changes: 216 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,216 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;

    namespace hackertrail
    {
    public class Helper
    {
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count)
    {
    int i = 0;
    foreach (var item in items)
    {
    if (count == 1)
    yield return new T[] { item };
    else
    {
    foreach (var result in GetPermutations(items.Skip(i + 1), count - 1))
    yield return new T[] { item }.Concat(result);
    }

    ++i;
    }
    }
    }
    class Program
    {
    static void Main(string[] args)
    {
    var items = ReadItems();
    var palleteA = new Pallete();
    palleteA.FindBestCombination(items);
    palleteA.Items.Sort(new ItemComparer());

    items = items.Except(palleteA.Items).ToList();

    var palleteB = new Pallete();
    palleteB.FindBestCombination(items);
    palleteB.Items.Sort(new ItemComparer());

    items = items.Except(palleteB.Items).ToList();
    var palleteC = new Pallete();
    palleteC.FindBestCombination(items);
    palleteC.Items.Sort(new ItemComparer());

    SendOutput(palleteA.Items, "A");
    SendOutput(palleteB.Items, "B");
    SendOutput(palleteC.Items, "C");
    }

    private static void SendOutput(List<Item> items, string palletName)
    {
    if (items.Count > 0)
    {
    Console.WriteLine($"{palletName}:" + items.Select(x => x.Id.ToString()).Aggregate((current, next) => current + "," + next));
    }
    else
    {
    Console.WriteLine($"{palletName}:");
    }
    }

    private static List<Item> ReadItems()
    {
    string line = Console.ReadLine();
    List<Item> items = new List<Item>();
    while (!string.IsNullOrWhiteSpace(line))
    {
    var args = line.Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries);
    var id = Convert.ToInt32(args[0]);
    var width = Convert.ToInt32(args[1]);
    var weight = Convert.ToInt32(args[2]);
    items.Add(new Item { Id = id, Width = width, Weight = weight });

    line = Console.ReadLine();
    }

    return items;
    }
    }

    public class Pallete
    {
    public List<Item> Items { get; set; } = new List<Item>();
    private const int Dimension = 1100;
    private const int Capacity = 1000;

    public int TotalWidth => Items.Sum(x => x.Width);
    public int TotalCapacity => Items.Sum(x => x.Weight);

    private int CalculateTotalWeight(List<Item> items)
    {
    return items.Sum(x => x.Weight);
    }

    private int CalculateTotalWidth(List<Item> items)
    {
    return items.Sum(x => x.Width);
    }

    public void CheckItemSet(List<Item> set)
    {
    var width = CalculateTotalWidth(set);
    var weight = CalculateTotalWeight(set);

    // check if items can fit pallete
    if (IsValid(width, weight))
    {
    if (Items == null)
    {
    Items = set;
    }
    else
    {
    // if new set is more heavy, choose as best set
    if (width > TotalWidth)
    {
    Items = set;
    }
    else if (width == TotalWidth)
    {
    // otherwise compare by weight
    if (weight > TotalCapacity)
    {
    Items = set;
    }
    else if (weight == TotalCapacity)
    {
    // or by number of items
    if (set.Count > Items.Count)
    {
    Items = set;
    }
    // or by lowest id
    else if (set.Count == Items.Count)
    {
    if (set.Min(x => x.Id) < Items.Min(x => x.Id))
    {
    Items = set;
    }
    }
    }
    }
    }
    }
    }

    public void FindBestCombination(List<Item> items)
    {
    if (items.Count > 0)
    CheckItemSet(items);


    for (int i = 1; i <= items.Count; i++)
    {
    var permutations = Helper.GetPermutations(items, i);
    foreach (var permutation in permutations)
    {
    CheckItemSet(permutation.ToList());
    }
    }
    }

    private bool IsValid(int width, int weight)
    {
    return width <= Dimension && weight <= Capacity;
    }
    }

    public class Item
    {
    public int Id { get; set; }
    public int Weight { get; set; }
    public int Width { get; set; }
    }


    /// <summary>
    /// comparer to correctly sort items in pallete
    /// </summary>
    public class ItemComparer :IComparer<Item>
    {
    public int Compare(Item x, Item y)
    {
    if (x.Width > y.Width)
    return -1;
    else if (x.Width == y.Width)
    {
    if (x.Weight > y.Weight)
    {
    return -1;
    }
    else if (x.Weight == y.Weight)
    {
    if (x.Id < y.Id)
    {
    return -1;
    }
    else
    {
    return 1;
    }
    }
    else
    {
    return 1;
    }
    }
    else
    {
    return 1;
    }
    }
    }
    }