Use LINQ to find complex combinations of items in two lists

Question

This question is very similar to a previous question of mine, Use LINQ to count the number of combinations existing in two lists, except with some further twists.

I have a list of CartItems that can receive a discount based on the items specified in the list of DiscountItems. I need to be able to pull out the items in the Cart that can receive a discount and apply the appropriate discount specfied in the DiscountItem. The discount is only applied for each combination that exists. Here's what the two lists might look like to 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 tricky part is that it's not simply a matter of joining the two lists together or counting the number of combinations. The discount is applied for all combinations of DiscountItems that appears in the list of CartItems. There are 3 such combinations in the above example and if you were to apply the discount for the 3 combinations iteratively across the list, the data would look like the following each time the 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, everything gets a discount except for the cheese and the extra bacon. The cheese doesn't get discounted because it's not a discounted item in the list. The extra bacon doesn't get a discount because it doesn't have a corresponding ham item to qualify for a discount combination. There are a total of 3 hams and 4 bacons, so one of the bacons is not going to get a discount.

I imagine I should be able to solve this problem using LINQ because it involves enumerating over 2 separate lists, but I can't think of what LINQ methods I would use to make this happen. The end result of the LINQ query should be the collection of CartItems with the discount having been applied.

Answer 1

// 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 2

EDIT: I just realized how old this question was.

I personally would use the following because it is the most readable to me. It doesn't use a whole lot of Linq, but I believe it's the least complex 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;
        }
    });
});

Answer 3

OK, just for fun, here's a sort-of-LINQ solution.

It's probably nowhere near as readable or efficient as the 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 wanted a single LINQ query with no side-effects then you could wrap it all up in an Aggregate call, but that would necessitate further depths of ugliness and inefficiency.)

Answer 4

To get exactly the result you want is bit difficult.You may have to store intermediate result - so need to introduce a new class. This was challenging so I did it as 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);
}
 };