TSQL Challenge 11: Calculating the lowest price of an item by applying discount coupons

TSQL Challenge 11 was a practical problem. Given a a list of products and a list of discount coupons, we needed to find the minimum price for all the products based on certain rules. Here are those rules:

  • Maximum two coupons can be applied on the same product
  • The discount price can not be less than 70% of the original price
  • The total amount of the discount can not exceed 30$

Also, note that coupons are applied in a cumulative way. So the second coupon is applied on the result of the original price + first coupon.

Sample Data:
Here is some sample products data:

ID NAME    PRICE
-- ------- ---------
1  PROD 1  100,00
2  PROD 2  220,00
3  PROD 3  15,00
4  PROD 4  70,00
5  PROD 5  150,00

Here are the coupons to be applied

ID NAME         VALUE  IS_PERCENT
-- -----------  ------ ----------
1  CP 1 : -15$  15     0
2  CP 2 : -5$   5      0
3  CP 3 : -10%  10     1
4  CP 4 : -12$  12     0

And here’s the required output:

ID NAME    PRICE    DISC_PRICE  TOT_DISC  RATE    COUPON_NAMES
2.-- ------  -------- ----------- --------- ------- -------------------------
3.1  PROD 1  100.00$  73.00$      27.00$    27.00%  CP 4 : -12$ + CP 1 : -15$
4.2  PROD 2  220.00$  193.00$     27.00$    12.27%  CP 4 : -12$ + CP 1 : -15$
5.3  PROD 3  15.00$   13.50$      1.50$     10.00%  CP 3 : -10%
6.4  PROD 4  70.00$   49.50$      20.50$    29.28%  CP 1 : -15$ + CP 3 : -10%
7.5  PROD 5  150.00$  120.00$     30.00$    20.00%  CP 3 : -10% + CP 1 : -15$

Solution

Interesting enough… So lets attempt to find a solution. Here’s an script to populate the above sample data:

DECLARE @T TABLE (ID INT IDENTITY, NAME NVARCHAR(20),PRICE MONEY)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 1',100)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 2',220)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 3',15)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 4',70)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 5',150)

DECLARE @C TABLE (ID INT IDENTITY, NAME NVARCHAR(20), VALUE INT, IS_PERCENT BIT)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 1 : -15$',15,0)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 2 : -5$',5,0)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 3 : -10%',10,1)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 4 : -12$',12,0)

Here’s a simple approach to address the problem.

  • We will start with the products table
  • have a cross join to apply all the coupons and get a result
  • have a cross join of this intermediate result with all the coupons (except the one that has already been applied in the previous join)
  • pick up the mininum prices

Lets start coding the above approach with a series of CTEs:

Step 1: Products with no coupons applied (We may need to start with the base products table because there can exist some products for which no discount can be applied).

--some products can not have any discount at all
;With NoDiscount As
(
	Select P.ID, P.NAME, P.PRICE, P.PRICE as DiscPrice, 0 as TotDisc, 0/P.PRICE as Rate,
		'' as Coupons, 0 as CouponsApplied, '' as CouponIDsApplied
	From @T P
)

Products with no discount applied

Step 2: Apply all coupons on the result of Step 1 using a cross Join and filter rows to meet the business rules (described in the beginning of the post). Notice that we have populated a CouponIDsApplied column that contains the IDs of all the coupons applied on a particular row. This column will help us ensuring we don’t apply the same coupon twice.

--product prices with one coupon applied
,OneCoupon As
(
	Select * from NoDiscount

	union all

	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE - P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		--derived table gives us better readability, otherwise the query would be filled up with lot of "case when" clauses
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.Coupons<>N'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied

		From NoDiscount P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
	) P
	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice <= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 <= 30
)

Products with one coupon applied

Step 3: Apply all coupons on the those rows of Step 2 that have one coupon applied (The result of Step 1 will also contain rows from the base product table with no discount applied and so we do not want to re-apply coupons on them).

--product prices with two coupons applied
,TwoCoupon As
(
	Select * from OneCoupon

	union all

	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE-P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.Coupons<>N'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied

		From OneCoupon P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
		--only apply second coupon on rows with 1 coupon applied
		where P.CouponsApplied=1
	) P
	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice <= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 <= 30

)

Products with two coupons applied

Step 4: Apply row number to sort the resulting prices. Notice that this is the point where we can define the criteria which rows to pick when multiple combinations yield same output, e.g. pick the rows that have higher order coupon applied first (CP4 then CP1 is preferred over CP1 then CP4), or pick the rows with lowest number of coupons applied first.

,SortedPrices As
(
	Select *, ROW_NUMBER() over (partition by ID order by DiscPrice,CouponsApplied,CouponIDsApplied desc ) as rowNumber
	From TwoCoupon
)

This is the output of the above step for product 2. Notice that there are 3 combinations that give us the least price. We are about to pickup the combination with highest order coupon applied first, i.e. CP4 then CP1.

Sorted result for product 2

Step 5: Pick up the minimum prices and format according to desired output.

Select ID, NAME, Cast(PRICE as varchar) + '$' as PRICE,
	Cast(DiscPrice as varchar) + '$' as DISC_PRICE, Cast(TotDisc as varchar) + '$' as TOT_DISC,
	Cast(Rate as varchar) + '%' as RATE, Coupons as COUPON_NAMES
from SortedPrices
Where rowNumber=1

Thats all. Here’s the final result that complies with the expected output of the challenge.

Result

Notice that we are applying the same operation in steps 2 and 3. This makes a perfect scenario to use recursive CTEs, so lets build one. The base case (anchor) would be to select all rows from the product table and then apply coupons on each iteration. Here’s the same approach using a recursive CTE.

;With ProductDiscounts AS
(
	--some products can not have any discount at all
	Select P.ID, P.NAME, P.PRICE, P.PRICE as DiscPrice,P.PRICE*0 as TotDisc, 0/P.PRICE as Rate,
			Cast(N'' as nvarchar(MAX)) as Coupons, 0 as CouponsApplied, Cast('' as varchar(MAX)) as CouponIDsApplied
	From @T P

	union all

	--recursively apply discount coupons until maximum (in this case 2) reached
	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE-P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		--derived table gives us better readability, otherwise the query would be filled up with lot of "case when" clauses
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.Coupons<>N'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied
		From ProductDiscounts P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
		--maximum 2 coupons can be applied
		where P.CouponsApplied<2
	) P

	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice <= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 <= 30
)

/*
Now we need to select top rows order by discount, grouped by product so we assign a row number based on the price
Note that this is the place where we define the criteria which rows to pick when multiple combinations yield same output,
e.g. pick the rows that have higher order coupon applied first (CP4 then CP1 is preferred over CP1 then CP4),
     pick the rows with lowest number of coupons applied first
*/
,SortedPrices As
(
	Select *, ROW_NUMBER() over (partition by ID order by DiscPrice,CouponsApplied,CouponIDsApplied desc ) as rowNumber
	From ProductDiscounts
)

--Result
Select ID, NAME, Cast(PRICE as varchar) + '$' as PRICE,
	Cast(DiscPrice as varchar) + '$' as DISC_PRICE, Cast(TotDisc as varchar) + '$' as TOT_DISC,
	Cast(Rate as varchar) + '%' as RATE, Coupons as COUPON_NAMES
from SortedPrices
Where rowNumber=1

Comparison of the two solutions
We have seen two solutions to the above problem. The first one would be efficient for large number of rows since it is an static solution. To increase the no. of coupons that can be applied, we need to add one CTE per increase in the no. of allowed coupons.
The second one, on the other hand, is much scalable and flexible. To change it to three or more coupons, we just need to change the where P.CouponsApplied<2 condition inside the recursive part.

To play with, here is complete solution script for both the versions:

DECLARE @T TABLE (ID INT IDENTITY, NAME NVARCHAR(20),PRICE MONEY)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 1',100)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 2',220)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 3',15)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 4',70)
INSERT INTO @T (NAME,PRICE) VALUES ('PROD 5',150)

DECLARE @C TABLE (ID INT IDENTITY, NAME NVARCHAR(20), VALUE INT, IS_PERCENT BIT)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 1 : -15$',15,0)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 2 : -5$',5,0)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 3 : -10%',10,1)
INSERT INTO @C (NAME,VALUE,IS_PERCENT) VALUES ('CP 4 : -12$',12,0)

/*
Solution 1: Simple solution that gives fair speed

To increase the no. of coupons that can be applied, we need to add one CTE per increase in no. of allowed coupons.
*/

--some products can not have any discount at all
;With NoDiscount As
(
	Select P.ID, P.NAME, P.PRICE, P.PRICE as DiscPrice, 0 as TotDisc, 0/P.PRICE as Rate,
		'' as Coupons, 0 as CouponsApplied, '' as CouponIDsApplied
	From @T P
)
--product prices with one coupon applied
,OneCoupon As
(
	Select * from NoDiscount

	union all

	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE - P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		--derived table gives us better readability, otherwise the query would be filled up with lot of "case when" clauses
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.Coupons<>N'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied

		From NoDiscount P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
	) P
	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice <= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 <= 30
)
--product prices with two coupons applied
,TwoCoupon As
(
	Select * from OneCoupon

	union all

	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE-P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.Coupons<>N'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied

		From OneCoupon P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
		--only apply second coupon on rows with 1 coupon applied
		where P.CouponsApplied=1
	) P
	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice <= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 <= 30

)

/*
Now we need to select top rows order by discount, grouped by product so we assign a row number based on the price
Note that this is the place where we define the criteria which rows to pick when multiple combinations yield same output,
e.g. pick the rows that have higher order coupon applied first (CP4 then CP1 is preferred over CP1 then CP4),
     pick the rows with lowest number of coupons applied first
*/
,SortedPrices As
(
	Select *, ROW_NUMBER() over (partition by ID order by DiscPrice,CouponsApplied,CouponIDsApplied desc ) as rowNumber
	From TwoCoupon
)

--Result
Select ID, NAME, Cast(PRICE as varchar) + '$' as PRICE,
	Cast(DiscPrice as varchar) + '$' as DISC_PRICE, Cast(TotDisc as varchar) + '$' as TOT_DISC,
	Cast(Rate as varchar) + '%' as RATE, Coupons as COUPON_NAMES
from SortedPrices
Where rowNumber=1

/*
Solution 2: Solution using recursive CTE
Gives us high flexibility and scalability (to change it to three or more coupons,
  we just need to change the "where P.CouponsApplied&lt;2&quot; condition inside the recursive part)
*/

;With ProductDiscounts AS
(
	--some products can not have any discount at all
	Select P.ID, P.NAME, P.PRICE, P.PRICE as DiscPrice,P.PRICE*0 as TotDisc, 0/P.PRICE as Rate,
			Cast(N'' as nvarchar(MAX)) as Coupons, 0 as CouponsApplied, Cast('' as varchar(MAX)) as CouponIDsApplied
	From @T P

	union all

	--recursively apply discount coupons until maximum (in this case 2) reached
	Select P.ID, P.NAME, P.PRICE, P.DiscPrice,
		P.Price - P.DiscPrice as TotDisc,
		(P.PRICE-P.DiscPrice)/P.PRICE * 100 as Rate,
		P.Coupons,
		P.CouponsApplied,
		P.CouponIDsApplied
	From
	(
		--derived table gives us better readability, otherwise the query would be filled up with lot of &quot;case when&quot; clauses
		Select P.ID, P.NAME, P.PRICE,
			Case
				When C.IS_PERCENT=0 Then P.DiscPrice-C.VALUE
				Else P.DiscPrice-(P.DiscPrice/100*C.VALUE)
			END as DiscPrice,
			Cast(P.Coupons + Case when P.CouponsN'' Then N' + ' Else N'' END + C.NAME as nvarchar(MAX)) as Coupons,
			P.CouponsApplied+1 as CouponsApplied,
			P.CouponIDsApplied + '(' + Cast(C.ID as varchar) + ')' as CouponIDsApplied
		From ProductDiscounts P
		inner join @C C on CHARINDEX('(' + Cast(C.ID as varchar) +  ')', P.CouponIDsApplied) = 0
		--maximum 2 coupons can be applied
		where P.CouponsApplied&lt;2
	) P

	Where
		--the total amount of the discount can not exceed 30$.
		P.Price - P.DiscPrice &lt;= 30
		--the discount price can not be less than 70% of the original price (i.e. the discount itself cant be greater than 30%)
		and (P.PRICE-P.DiscPrice)/P.PRICE * 100 &lt;= 30
)

/*
Now we need to select top rows order by discount, grouped by product so we assign a row number based on the price
Note that this is the place where we define the criteria which rows to pick when multiple combinations yield same output,
e.g. pick the rows that have higher order coupon applied first (CP4 then CP1 is preferred over CP1 then CP4),
     pick the rows with lowest number of coupons applied first
*/
,SortedPrices As
(
	Select *, ROW_NUMBER() over (partition by ID order by DiscPrice,CouponsApplied,CouponIDsApplied desc ) as rowNumber
	From ProductDiscounts
)

--Result
Select ID, NAME, Cast(PRICE as varchar) + '$' as PRICE,
	Cast(DiscPrice as varchar) + '$' as DISC_PRICE, Cast(TotDisc as varchar) + '$' as TOT_DISC,
	Cast(Rate as varchar) + '%' as RATE, Coupons as COUPON_NAMES
from SortedPrices
Where rowNumber=1
Advertisements

One Response to “TSQL Challenge 11: Calculating the lowest price of an item by applying discount coupons”

  1. I Heart Recursive Subquery Factoring « So Many Oracle Manuals, So Little Time Says:

    […] Mehroz Alam provided an elegant solution to the above problem using recursive common table […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: