How do we calculate promotions in the cart?

In this article, I am going to explain how we calculate promotions in cart which is a complex problem that causes performance issues and requires executing business rules step by step.

Business rules are sometimes quite complicated and challenging. As the rules getting bigger and more complex, bugs and forgotten cases are imminent. Although it becomes a situation where bugs will be unavoidable, the purpose is to cover every case and never give up. ☺

I would like to talk about the most complex business problem we encountered during this period when we decided to re-platform our Promotion service and have worked for several months. Promotion is divided into two parts which are free shipping promotion and instant discount promotion. In free shipping promotions, if the user has at least one product in the basket with a free shipping promotion, then the user pays no shipping cost in the basket. To clarify the disadvantages of this situation, when you add both a sweater and a fridge in the basket, the free shipping promotion which supposed to be applied to the sweater also covers the shipping fee of the fridge. As a result of the changes, we have decided to apply this logic and free shipping promotion will only be applied to the sweater.

Instant Discount is another type of promotion. Let’s say we have two promotions applicable to the basket and the first promotion makes discounts to two sweaters, and the second promotion makes discounts to two shoes. We distribute the discount on the first promotion according to the weight of two sweaters (unit price).

There are many rules under this summary, for example, more than one free shipping and more than one instant discount promotions can be applied to the basket, but a product in the basket can only have one instant discount promotion and one free shipping promotion.

How do we decide that a promotion can be applied to the basket?

Although there is a big process to do this, I will try to give a brief and general overview. Some conditions determine whether a promotion can or cannot be applicable, but what are these conditions? For example, all criteria like category, brand, campaign, user segment, bin number, email extension, etc. are the conditions of a promotion. For instance, when there is a promotion like a 20 percent discount in category A, this ‘category A’ is a condition of promotion. In this case, we decide which promotions can be applied to the basket with comparing conditions.

Of course, the only decision mechanism is not the conditions of the promotion. There may be other restrictions that require a check, such as limitations. For example, we can set a usage restriction on a promotion to limit the usage three times and prevent the user from using this promotion on the fourth-order. To determine how much discount will be applied to the basket, ‘apply endpoint’ of the promotion API is called. In this, most advantageous promotions are calculated and applied to the basket. At this point, the question is that, which promotions are applicable for the basket? And how most advantageous combinations of these are selected? Below, we tried to outline some of the selection criteria in applying for promotions but how do we create the combination or find the most advantageous?

Combination
Combination
Combination
……

I can feel the bumps of a programmer reading the combination lines. ☺ Furthermore, there can be 100 instant discount promotions that can be applied to a basket, so how can the combination of these 100 promotions be found? Moreover, each sequence of work can have different results. This means that the A and B promotions that we apply to the basket can produce different results when applying in order like A-B and B-A. This difference arises from the fact that when we apply a promotion to the basket, we eliminate the products which have already a promotion on it. By eliminating the products from the basket, we prevent applying the next promotion from using the same products and from applying multiple instant discount promotions to one product. In this case, ranking is an important point for us, but doesn’t this create a very large combination? Considering only two promotions that can be applied to the basket, we have to apply the following combinations one by one.

Promotion A can be applied alone
Promotion B can be applied alone
Promotions A-B can be applied in order
Promotions B-A can be applied in order

It cannot be an empty set because it has passed the selection phase if it came in the application phase. Passing through the selection phase means that at least 1 promotion can be applied. Let’s think of 3 promotions.

1. A
2. B
3. C
4. A-B
5. A-C
6. B-A
7. B-C
8. C-A
9. C-B
10. A-B-C
11. A-C-B
12. B-A-C
13. B-C-A
14. C-A-B
15. C-B-A

If the sorting was something insignificant and A-B was no different from B-A, we could immediately calculate a probability with 2 ^ 3–1 (not counting the empty set) as we would calculate the subset number of a 3-element set but in this case, ranking is also important for us because there are 15 different possibilities and calculations. Only for 3 promotions. So how can we handle this situation in giant baskets or when the number of promotions that can be applied is huge?

This is where the tree structure comes in. Depth First Search (DFS) or Breadth-First Search (BFS) may have come to mind when we said tree structure. Although the solution is similar, you realize that there are no rules such as the first node should be larger than the branch on the left and smaller than the right one. Each promotion represents an object, and each object is a node in the tree. There should be four promotions that we can apply to the basket, so there must be four roots among trees. Below you can see the example.

This image shows the tree for promotion 1 (P1) only. There are four trees in total including promotion 2 (P2), promotion 3 (P3), and promotion 4 (P4). Tree’s length is the number of promotions minus one. Promotions that don’t have any branches (childtree) are called a leaf. P1 is applied to the basket, the products used by P1 are eliminated from the basket and the new version of the basket is sent to P2 and operated. The items used by P2 are eliminated from the basket and the new version of the basket is sent to P3 and so on. The process discontinues sub-branches if there is no product left in the basket or the next P3 cannot be applied to the basket and combinations of promotions applied to the basket added to the combination list like (P1, P2) then continue to proceeding with P3, another subtree of P1. When we could not apply P3 after applying P1 and P2, it does not go on with P4 and this logic provides a great advantage by avoiding over-processing. This provides a significant benefit when considering the number of combinations.

Here we have created branches of the tree using recursive function. In fact, each branch is a tree, we called them subtree. Thanks to the greatness of Recursive, we created trees with a few lines of code. ☺

So far, everything is fine, I thought we were going through the hardest part. Then, when it was time to walk through in the tree and apply for promotions and find the appropriate combinations, I realized that the most difficult part was not to produce trees. In other words, it will implement P1, implement P2, will not be able to implement P3, and will not be able to move to its sub-branch, P4 and add the combination of {P1, P2}. After that, another branch of P1, P3, should continue, P1 should not make a calculation again.

As a result of the rotating combinations, we find the most advantageous promotions for the user when we sort the according to discount and priority and get the first combination. I hope you like the article. Thank you for reading.