Tackling problems with indefinite answers

In your programming career, have you ever faced a problem where there’s more than one answer? Or that you don’t even know if there is a right answer? Let me tell you one of mine.

Recently, one of my colleagues came to me for advice on a validation condition he faced. It turned out to be mathematical in nature. Wow! Anyway, in his database he stored number_of_days, month and prorated_fee. The stored data contains records of the results of prorating calculations.

What is prorating? Say a customer was charged a monthly fee for a service, and the customer had just signed up for the monthly service near the end of June. And he had the service for only 5 days, June has 30 days, and the monthly fee is $20. Prorating means he’d be charged 5 / 30 * $20 = $3.33. You will have noticed that prorating often has inexact results because the calculated values are rounded to 2 decimal places.

Back to my colleague’s problem. Suppose that the records from the database looked like this

days  month  prorated
5     30     3.33
8     30     5.33

I’ve translated the month into the number of days in that month for easier visualisation.

The problem was, given those records, could he prove that the prorated fee was calculated from the same monthly fee?

For this example, the monthly fee used was $20, so the results match. What he needed from me was, was there a way to programatically determine if there was a correct original monthly fee?

My initial instinctive answer was no, because all precision of the calculation was lost when the final value was rounded. Then he said, he’s not looking for precision. He just wanted to know if there was a possibility that the records were calculated using the same monthly fee. Aaahhhh, now we’re talking. So I told him to give me some time to work out an equation or something. Then I went to work.

Mathematically formulating the problem, I got:
Given d, m and p, where
d is the number of days in service
m is the number of days of that month in service
p is the calculated prorated value
find f, the original monthly fee, such that abs(fd/m - p) < 0.005

The equation is fd/m = p', where p' is the exact calculated value. Then p' is rounded to p.

The abs(fd/m - p) < 0.005 condition was because of the rounding. The difference between the calculated value and the stored value must be less than 0.005 for the rounding to be correct. And the error margin is 0.005 because 2 decimal place rounding means the value to be rounded is less than half of 0.01.

Rewriting the condition, we get
-0.005 < fd/m - p < 0.005
=> -0.005m < fd - pm < 0.005m
=> -0.005m + pm < fd < 0.005m + pm
=> (p - 0.005)m/d < f < (p + 0.005)m/d [d is always positive, so division is fine]

Substituting our first record's values into the inequality, we get
(3.33 - 0.005)(30)/(5) < f < (3.33 + 0.005)(30)/(5) => 19.95 < f < 20.01 Substituting our second record's values into the inequality, we get (5.33 - 0.005)(30)/(8) < f < (5.33 + 0.005)(30)/(8) => 19.96875 < f < 20.00625 Now if there were more records, we'd continue substituting, and we'll end up with a lot of inequality ranges. So what's the solution to the problem? If there was an f such that it satisfies all the inequalities, then the prorated values could have been calculated from the same monthly fee.

I went back to my colleague and told him that even if the inequalities could be solved, he might still have a range of values that could have contained the original monthly fee. So there's still no exact answer. He said that was fine. He rephrased his objective, that he wanted to know if the records from the database could have been calculated from the same monthly fee within reasonable limits.

Ohhh. Ok. I told him if he could find a range of values of f satisfying the set of inequalities from above, and that there was a value in that range with at most 2 decimal places, then he's done.

Example, a range of (19.956, 20.00) would be valid, because the original value could be 19.96 or 19.97.
But a range of (19.956, 19.959) would be invalid, because there were no values that had at most 2 decimal places. The reason for this was that the original monthly fee was at most 2 decimal places.

So, how do we find that range of values of f satisfying all the inequalities?

Let L be the set of the left hand values of the inequalities. Let R be the set of right hand values of the inequalities. Then there's a range of values of f satisfying the inequalities if and only if the maximum value in L is less than or equal to the minimum value in R. Stated mathematically,

max(L) <= min(R)

I gave him the piece of paper where I scribbled my notes, and he copied some of the important formulae. What about determining the solution programmatically? What, are you kidding? I wracked my brain for a mathematical solution, distilled it into understandable logic steps. How to implement this was up to him... *grin*