Skip to content

Instantly share code, notes, and snippets.

@ahanoff
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.
Hackertrail assignment
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;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment