Phone Plan Matchup: SQL Brute Force Method
A few days ago on CF-Talk Greg Morphis asked for a method to find the cheapest combination of phone plans that satisfy a customer's requirements for the number of lines being used and the amount of minutes to share between the plans. At first, I thought the answer could be derived directly, but since the plans and their relative price/minute values are essentially random, they create different price breaks that change as you add minutes and lines. This means one combination of plans might be the cheapest for 500 minutes, but once you increase that to 600 minutes, a completely different set of plans might come into play that are now the cheapest.
I offered a brute force method would mean calculating ALL POSSIBLE combination of plans and lines and then taking the cheapest one that matches the criteria. Feeling sightly obliged to explain the process, and growing continuously more curious abut the solution I pulled together a proof of concept. I will not promise that this is the fastest nor the best solution, but it does work.
Here is the setup. The poster gave 9 sample phone plans with a known price and number of minutes to choose from to create the customer's package:
- PLAN A $25.00, 0 minutes
- PLAN B $32.00, 200 minutes
- PLAN C $42.00, 500 minutes
- PLAN D $52.00, 750 minutes
- PLAN E $63.00, 900 minutes
- PLAN F $84.00, 1,400 minutes
- PLAN G $105.00, 2,100 minutes
- PLAN H $155.00, 4,000 minutes
- PLAN I $210.00, 6,000 minutes
The input parameters would simply be the number of phone lines desired by the customer as well as the number of minutes needed to share across the lines.
For example. 10 lines 9,500 minutes would be
1 @ PLAN I = 210.00 (6000 minutes)
7 @ PLAN C = 294.00 (3500 minutes)
2 @ PLAN A = 50.00 (0 minutes)
total = 554.00
Assumptions made are that if there are no plans that can be used in combination with the given number of lines to reach the required amount of minutes, nothing will be returned. Also, if the exact number of minutes cannot be reached, the cheapest plan that exceeds the minutes will be given.
Given an example requirement of 10 lines, I decided that the output of my code would always come in this form since it would be possible to not use a plan at all, or to use the same plan over and over for all 10 lines:
PLAN A 0-10 times
PLAN B 0-10 times
PLAN C 0-10 times
...
PLAN N 0-10 times
This means that there are 10+1 possible configurations of each plan. And since we need to find all possible combination of all possible plans configurations, and we have 9 plans, that means all our possible plan combinations looks like this:
10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 = 11^9 = 2,357,947,691
That's a lot. If we replace our example of 10 lines with numberOfLines and 9 plans with numberOfPlans, we can generically represent the possibilities as:
(numberOfLines+1)^numberOfPlans
That's about all the theory I can explain without just showing the code now. I tested this on SQL Server 2000, mostly because I didn't have anything else handy at the time.
The reason I decided to try a SQL server solution is because SQL server makes it easy to create a Cartesian Product by joining two tables on an always true statement thus returning a result set that represents every possible combination of all records in both tables. The last time I used this was when I was experimenting with Rainbow Tables and wanted to generate all possible passwords given a set of characters.
2
3 DECLARE @numLines AS int
4 DECLARE @numMinutes AS int
5 DECLARE @counter AS int
6
7
8 /* Set Parameters here */
9 SET @numLines = 10
10 SET @numMinutes = 9500
11 /* Set Parameters here */
12
13 SET @counter = 1
14
15 IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#plans'))
16 DROP TABLE #plans
17 IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#repeats'))
18 DROP TABLE #repeats
19 IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#combinations'))
20 DROP TABLE #combinations
21
22 CREATE TABLE #plans
23 (name varchar(10) PRIMARY KEY,
24 price money,
25 minutes int,
26 processed bit DEFAULT 0)
27
28 CREATE TABLE #repeats
29 (repeat int PRIMARY KEY)
30
31 CREATE TABLE #combinations
32 (planName varchar(10),
33 repeat int,
34 minutes int,
35 price money)
36
37 CREATE CLUSTERED INDEX #combo_plan_name ON #combinations (planName)
38
39
40 INSERT INTO #plans (name, price, minutes)
41 SELECT 'PLANA', 25.00, 0
42 UNION SELECT 'PLANB', 32.00, 200
43 UNION SELECT 'PLANC', 42.00, 500
44 UNION SELECT 'PLAND', 52.00, 750
45 UNION SELECT 'PLANE', 63.00, 900
46 UNION SELECT 'PLANF', 84.00, 1400
47 UNION SELECT 'PLANG', 105.00, 2100
48 UNION SELECT 'PLANH', 155.00, 4000
49 UNION SELECT 'PLANI', 210.00, 6000
50
51 SET @counter = 0
52 WHILE @counter <= @numLines
53 BEGIN
54 INSERT INTO #repeats VALUES (@counter)
55 SET @counter = @counter + 1
56 END
57
58 INSERT INTO #combinations (planName, repeat, minutes, price)
59 SELECT p.name, r.repeat, p.minutes * r.repeat as minutes, p.price * r.repeat as price
60 FROM #plans p
61 INNER JOIN #repeats r ON 1 = 1
62
63 SELECT TOP 1 a.repeat AS 'PlanA',
64 b.repeat AS 'PlanB',
65 c.repeat AS 'PlanC',
66 d.repeat AS 'PlanD',
67 e.repeat AS 'PlanE',
68 f.repeat AS 'PlanF',
69 g.repeat AS 'PlanG',
70 h.repeat AS 'PlanH',
71 i.repeat AS 'PlanI',
72 a.price + b.price + c.price + d.price + e.price + f.price + g.price + h.price + i.price AS price,
73 a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes + i.minutes AS minutes
74 FROM #combinations a
75 INNER JOIN #combinations b ON b.planName = 'PlanB'
76 AND a.repeat + b.repeat <= @numLines
77 AND a.minutes + b.minutes < @numMinutes + 100
78 INNER JOIN #combinations c ON c.planName = 'PlanC'
79 AND a.repeat + b.repeat + c.repeat <= @numLines
80 AND a.minutes + b.minutes + c.minutes < @numMinutes + 500
81 INNER JOIN #combinations d ON d.planName = 'PlanD'
82 AND a.repeat + b.repeat + c.repeat + d.repeat <= @numLines
83 AND a.minutes + b.minutes + c.minutes + d.minutes < @numMinutes + 500
84 INNER JOIN #combinations e ON e.planName = 'PlanE'
85 AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat <= @numLines
86 AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes < @numMinutes + 500
87 INNER JOIN #combinations f ON f.planName = 'PlanF'
88 AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat <= @numLines
89 AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes < @numMinutes + 500
90 INNER JOIN #combinations g ON g.planName = 'PlanG'
91 AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat <= @numLines
92 AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes < @numMinutes + 500
93 INNER JOIN #combinations h ON h.planName = 'PlanH'
94 AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat + h.repeat <= @numLines
95 AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes < @numMinutes + 500
96 INNER JOIN #combinations i ON i.planName = 'PlanI'
97 AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat + h.repeat + i.repeat = @numLines
98 AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes + i.minutes >= @numMinutes
99 WHERE a.planName = 'PlanA'
100 ORDER BY a.price + b.price + c.price + d.price + e.price + f.price + g.price + h.price + i.price
What this code essentially does is populates a temp table full of plans, another temp table with numbers 1 through the number of lines to represent how many times each plan MIGHT be repeated. Those tables are joined into a Cartesian product that shows the possible number of times each plan might be used. The resulting table of combinations is joined together once for each plan to generate all the possible plan combinations.
Note the redundant AND statements in each join. If I wanted, I could have just limited my result set once at the end, but you'll remember that our example of 10 lines and 9500 minutes has over 2 Billion combinations. Filtering down the result set as we build the combinations eliminates combinations that we know aren't going to work and there's no use keeping them around the result set any longer. This has a phenomenal increase in performance since it keeps the growth more linear than exponential. With this method, the final WHERE clause is only applied to 233,288 records. (I cheated and looked at the execution plan for this number)
Performance on my SQL Server 2000 box is about 1 second to calculate the 10 lines, 9,500 minutes example. It absolutely flies when you do something simple like 3 lines 1,000 minutes. I would definitely want to put a cap on it though. I believe it took about five minute to calculate 30 lines and 20,000 minutes. The numbers just start getting silly huge if you go crazy with it.
Now, one last thing. The number of plans could change at any time-- A plan could be added or removed. I gave the first bit of code with the final select hard-coded for readability. SQL is butt-ugly at making dynamic queries, but if you replace the final select with the following code, it will be dynamic based on how many plans there are. Frankly I recommend you do the dynamic part in CF and output it in a cfquery, but here's the SQL-only version:
2 DECLARE @SQLPriceAdd AS varchar(8000)
3 DECLARE @SQLRepeatAdd AS varchar(8000)
4 DECLARE @SQLMinutesAdd AS varchar(8000)
5 DECLARE @SQLRepeatColumns AS varchar(8000)
6 DECLARE @SQLWhere AS varchar(500)
7 DECLARE @SQLJoins AS varchar(8000)
8 DECLARE @SQLTotal AS varchar(8000)
9 DECLARE @position AS varchar(20)
10 SELECT @SQLPriceAdd = '', @SQLMinutesAdd = '', @SQLRepeatColumns = '', @SQLRepeatAdd = '', @SQLJoins = '', @position = 'FIRST', @SQLWhere = ''
11
12 WHILE EXISTS(SELECT 1 FROM #plans WHERE processed = 0)
13 BEGIN
14 SELECT TOP 1 @planNameCounter = name,
15 @SQLRepeatColumns = @SQLRepeatColumns + '
16 ' + name + '.repeat AS ''' + name + ''',',
17 @SQLMinutesAdd = @SQLMinutesAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.minutes',
18 @SQLPriceAdd = @SQLPriceAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.price',
19 @SQLRepeatAdd = @SQLRepeatAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.repeat',
20 @SQLJoins = @SQLJoins + CASE WHEN @position = 'FIRST' THEN '
21 FROM #combinations ' + name ELSE '
22 INNER JOIN #combinations ' + name + ' ON ' + name + '.planName = ''' + name + '''
23 AND ' + @SQLRepeatAdd + CASE WHEN @position = 'LAST' THEN ' = ' ELSE ' <= ' END + cast(@numLines as varchar(10)) + '
24 AND ' + @SQLMinutesAdd + CASE WHEN @position = 'LAST' THEN ' >= ' + cast(@numMinutes as varchar(10)) ELSE ' < ' + cast(@numMinutes + 100 as varchar(10)) END END,
25 @SQLWhere = CASE WHEN @position = 'FIRST' THEN 'WHERE ' + name + '.planName = ''' + name + '''' ELSE @SQLWhere END
26 FROM #plans
27 WHERE processed = 0
28 ORDER BY name
29
30 UPDATE #plans
31 SET processed = 1
32 WHERE name = @planNameCounter
33
34 SELECT @position = CASE WHEN count(1) = 1 THEN 'LAST' ELSE 'MIDDLE' END
35 FROM #plans WHERE processed = 0
36
37 END
38
39 SET @SQLTotal = ' SELECT TOP 1 ' + @SQLRepeatColumns +'
40 ' + @SQLPriceAdd + ' AS price,' + '
41 ' + @SQLMinutesAdd + ' AS minutes' + @SQLJoins + '
42 ' + @SQLWhere + '
43 ORDER BY ' + @SQLPriceAdd
44
45
46 EXEC (@SQLTotal)
Well, there you have it. I hope this is useful to the original poster, and at least entertaining for the rest of you. Let me know you have any questions or suggestions. I whipped most of this up late at night, so I'm sure there's some tweaking that could still be done.
There are no comments for this entry.
[Add Comment] [Subscribe to Comments]