Use LINQ to find complex combinations of items in two lists.

Question

This question is very similar to my previous question. Use LINQ to count the number of combinations existing in two lists , with the exception of some additional twists.

I have a CartItem list that can receive a discount based on the items specified in the DiscountItem s list. I need to remove items from the basket that can receive a discount and apply the corresponding discount specified in DiscountItem . The discount applies only to every combination that exists. Here's what the two lists look like before the discount is applied:

  BEFORE DISCOUNT:   

     CartItems DiscountItems
     ==================================================== =======
     SKU Qty DiscountApplied SKU DiscountAmount
     ==================================================== =======
     Ham 2 $ 0.00 Ham $ 0.33
     Bacon 1 $ 0.00 Bacon $ 2.00
     Ham 1 $ 0.00                 
     Bacon 2 $ 0.00
     Cheese 1 $ 0.00
     Bacon 1 $ 0.00 

The hard part is that it's not just a matter of combining two lists or counting the number of combinations. The discount applies to all DiscountItem combinations that appear in the CartItem s list. There are three combinations in the above example, and if you have to apply a discount for three combinations iteratively through the list, the data will look like this every time a discount is applied:

  After 1st Discount is applied:

     CartItems DiscountItems
     ==================================================== =======
     SKU Qty DiscountApplied SKU DiscountAmount
     ==================================================== =======
     Ham 2 $ 0.33 Ham $ 0.33
     Bacon 1 $ 2.00 Bacon $ 2.00
     Ham 1 $ 0.00                 
     Bacon 2 $ 0.00
     Cheese 1 $ 0.00
     Bacon 1 $ 0.00    

     After 2nd Discount is applied:

     CartItems DiscountItems
     ==================================================== =======
     SKU Qty DiscountApplied SKU DiscountAmount
     ==================================================== =======
     Ham 2 $ 0.66 Ham $ 0.33
     Bacon 1 $ 2.00 Bacon $ 2.00
     Ham 1 $ 0.00                 
     Bacon 2 $ 2.00
     Cheese 1 $ 0.00
     Bacon 1 $ 0.00        

     After 3rd Discount is applied:

     CartItems DiscountItems
     ==================================================== =======
     SKU Qty DiscountApplied SKU DiscountAmount
     ==================================================== =======
     Ham 2 $ 0.66 Ham $ 0.33
     Bacon 1 $ 2.00 Bacon $ 2.00
     Ham 1 $ 0.33                 
     Bacon 2 $ 4.00
     Cheese 1 $ 0.00
     Bacon 1 $ 0.00 

In the end, everyone gets a discount, with the exception of cheese and extra bacon. Cheese does not receive a discount because it is not a discount on the list. Extra bacon does not receive a discount because it does not have the corresponding ham subject to qualify for the discount. A total of 3 ham and 4 bacon, so one of the bacon will not receive a discount.

I assume that I will be able to solve this problem with LINQ, since it involves listing more than two separate lists, but I cannot figure out which LINQ methods I will use to make this happen. The end result of a LINQ query should be a CartItem set with a discount applied.

Answer 1

Well, just for fun, here is a LINQ type solution.

It is probably nowhere near as readable or efficient as equivalent iterative code, but it works!

 var discountedCart = CartItems.Select(c => c); var combinations = DiscountItems.Any() ? DiscountItems.GroupJoin(CartItems, d => d.SKU, c => c.SKU, (d, g) => g.Sum(c => c.Qty)).Min() : 0; if (combinations > 0) { var map = DiscountItems.ToDictionary(d => d.SKU, d => combinations); discountedCart = CartItems.Select(c => { int mul; map.TryGetValue(c.SKU, out mul); if (mul < 1) return c; decimal amt = DiscountItems.Single(d => d.SKU == c.SKU).DiscountAmount; int qty = Math.Min(mul, c.Qty); map[c.SKU] = mul - qty; return new CartItem { SKU = c.SKU, Qty = c.Qty, DiscountApplied = amt * qty }; }); } foreach (CartItem item in discountedCart) { Console.WriteLine("SKU={0} Qty={1} DiscountApplied={2}", item.SKU, item.Qty, item.DiscountApplied); } 

(I suspect that if you need one LINQ query without side effects, then you can wrap it in Aggregate , but this will require additional depths of ugliness and inefficiency.)

Answer 2

 // Here we get all items have discounted, and gets minimal count of items // This value is number of full combinations of items discounted var minimalNumberOfItemsDiscounted = CartItems.Where(ci => DiscountItems.Any(di => ci.SKU == di.SKU)) .GroupBy(ci => ci.SKU) .Min(g => g.Count()); // Now we can apply discount to each item in cart, and we know how many // times (== minimalNumberOfItemsDiscounted) discount is applied return CartItems .Select(ci => new { CartItem = ci, Discount = DiscountItems.FirstOrDefault(di => di.SKU == ci.SKU) }) .Select(k => { if (k.Discount != null) { k.CartItem.Discount = minimalNumberOfItemsDiscounted * k.Discount.DiscountAmount; } return k.CartItem; }); 

Answer 3

It’s hard for you to get exactly the result you need. You may need to keep the intermediate result - so you need to introduce a new class. It was complicated, so I did it as shown below - it seems to work

 class Program { public class CartItem { public string sku { get; set; } public int qty {get;set;} public decimal DiscountApplied { get; set; } public CartItem(string sku,int qty,decimal DiscountApplied) { this.sku=sku; this.qty=qty; this.DiscountApplied=DiscountApplied; } } public class DiscountItem{ public string sku {get;set;} public decimal DiscountAmount {get; set;} } static List<CartItem> carts=new List<CartItem>(){ new CartItem("Ham",2,0.0m ), new CartItem("Bacon",1,0.00m ), new CartItem("Ham",1,0.00m ), new CartItem("Bacon",2 ,0.00m), new CartItem("Cheese",1,0.00m), new CartItem("Bacon" , 1 , 0.00m )}; static List<DiscountItem> discounts=new List<DiscountItem>() { new DiscountItem(){ sku="Ham", DiscountAmount=0.33m}, new DiscountItem(){sku="Bacon",DiscountAmount=2.0m}}; class cartsPlus { public CartItem Cart { get; set; } public int AppliedCount { get; set; } } public static void Main(string[] args){ int num = (from ca in discounts join cart in carts on ca.sku equals cart.sku group cart by ca.sku into g select new { Sku = g.Key, Num = g.Sum(x => x.qty) }).Min(x => x.Num); var cartsplus = carts.Select(x => new cartsPlus { Cart = x, AppliedCount = 0 }).ToList(); discounts.SelectMany(x => Enumerable.Range(1, num).Select(y => x)).ToList().ForEach(x=>{cartsPlus c=cartsplus. First(z=> z.Cart.sku==x.sku&&z.AppliedCount<z.Cart.qty);c.AppliedCount++;c.Cart.DiscountApplied+=x.DiscountAmount;}); foreach (CartItem c in carts) Console.WriteLine("{0} {1} {2}", c.sku,c.qty, c.DiscountApplied); } }; 

Answer 4

EDIT: I just realized how old this question was.

I personally would use the following because it is the most readable for me. It doesn't use a lot of Linq, but I find this the least difficult answer.

 // For each discount that can be applied foreach(var discount = DiscountedItems.Where(c => CartItems.Any(d => d.SKU == c.SKU))) { var discountLimit = 3; // how many items are allowed to have a discount. foreach(var item in CartItems.Where(d => d.SKU == item.SKU)) { if(discountLimit < item.Quantity) { // update the discount applied item.DiscountApplied = discountLimit * discount.DiscountAmount; discountLimit = 0; // causes the rest of the items to not get a discount } else { // update the discount applied item.DiscountApplied = item.Qty * discount.DiscountAmount; discountLimit -= item.Qty; } } } 

If you have MoreLinq or LinqKit, you can also do the following:

 // For each discount that can be applied DiscountedItems.Where(c => CartItems.Any(d => d.SKU == c.SKU)).foreach(discount => { var discountLimit = 3; // how many items are allowed to have a discount. CartItems.Where(d => d.SKU == item.SKU).foreach(item => { if(discountLimit < item.Quantity) { // update the discount applied item.DiscountApplied = discountLimit * discount.DiscountAmount; discountLimit = 0; // causes the rest of the items to not get a discount } else { // update the discount applied item.DiscountApplied = item.Qty * discount.DiscountAmount; discountLimit -= item.Qty; } }); });