tags:

views:

98

answers:

5
+3  Q: 

Need help with credit expiration algorithm

So I'm stuck. I am working on a credit system with expirations. Similar to credit card miles but not exactly. By the way I am sorry for the book ahead but I needed to add enough detail to help get the whole picture.

What I need is a system where a user accumulates credits for doing activities. But they can also spend these credits on activities. The credits should expire after 30 days if they are not used. I seem to be stuck on how to accurately calculate this in a batch that will run every night. Any ideas in any language would be greatly appreciated as I seem to be stuck on just one minor detail that I can't get around. Here is an example of the data:

7/1: +5 - user signs up
7/2: +5 - user interacts with system
7/2: -3 - user purchases activity
7/3: +5 - user interacts with system

So at this point the user has received 15 credits and has spent 3. Leaving him with a total of 12 credits. (At least I got basic math down :P)

I should add that currently we are playing with the idea of having two fields: last processed, next processed. So these values at this time assuming it was a new sign up are:

Last Processed Date: 7/1
Next Process Date: 8/1

So now 8/1 comes around. The batch starts and looks at all credits that are older than 30 days. Which at this point is 5.

This is where it starts to get fuzzy.

Then the system should look at all the credits that have been spent in the last 30 days to see if they are using any credits. Because they should only expire if they haven't been used. So there are 3. So I then deduct the user 2 credits because that is the difference of credits earned older than 30 days and what has been spent. So I finish the batch and set the dates accordingly for the next day. Now assuming they haven't spent anymore I start the calculation over of credits earned older than 30, which is 5 and credits spent which again is 3. But I obviously don't want to consider the 3 credits that I considered yesterday. What is a good approach to not include those 3 credits again for consideration.

That is where I am stuck.

We are thinking about writing a debit record for the expired credits so we can track them but having a hard time seeing how I can use it in this calculation.

If you read this far thank you. If you even make a somewhat effort in the answer I will at a minimum give you an up vote for effort.

EDIT:
Ok @Greg mentioned something that I forgot to address. The idea of putting a flag on the credits considered. A valid point but not one that can work because of the following scenario:

Let's say that on a particular day a user spends 10 credits. But the expired credits that the batch is considering only accumulated to 5. Well he should still have 5 more credits left over to not have expired because he spent more than a single expiration. So the flag wouldn't work because we would have skipped those 5 extra credits. Hope that makes sense?

+1  A: 

How about adding a flag to the expenditures? If the flag is not set, then you can include that expenditure in the batch, if necessary. If you do use the expenditure to offset an expiration, then you set the flag. Next time through, you'll ignore that expenditure because the flag is set.

Greg Harman  2010-07-07 22:25:41
@Greg thanks for mentioning that I think I left one bit of detail out of my post. Let me add that now.
spinon  2010-07-07 22:28:48
+2  A: 

I wouldn't consider trying to process the data as you present it. Instead, you should keep track of how many credits the user has, and when they expire. That way you keep track of which credits were used when the purchase is made, instead of trying to work it all out later.

So when the user signs up, they have:

5 credits expiring on 8/1

After interacting with the system the next day:

5 credits expiring on 8/1
5 credits expiring on 8/2

After purchasing something:

2 credits expiring on 8/1
5 credits expiring on 8/2

And so on.

Anon.  2010-07-07 22:28:50
A great UI idea, but this is a bad way to actually store the data; you want an audit trail in case one has a bug to correct
Heath Hunnicutt  2010-07-07 22:30:32
@Heath: Indeed, this is not a replacement for a proper transaction log. However, using something like this primarily, and treating the transaction log as basically append-only unless something isn't right, is, IMO, the best way to go forward.
Anon.  2010-07-07 22:36:25
@Heath I have to agree. I don't want to touch the records that indicate how many credits were earned. I have considered this idea but I think for the purposes of what Heath mentioned in regards to an audit trail I just can't see how I could implement this cleanly in a storage system.
spinon  2010-07-07 22:37:28
@Anon I am not completely opposed to the idea if you have a good way to implement this and not add too much overhead. This table will already be quite large as we are dealing with nearly 100,000 users. So keeping track of their daily activity like this will get big. Adding another table to track nearly duplicate data just doesn't seem like the right approach. But I could be missing something.
spinon  2010-07-07 22:39:14
@spinon: The transaction logs will be essentially write-only - instead of a record of all transactions within the last 30 days, you can maintain a mere 30 integers per-user and still have all the information you need to calculate expiration times, balances and the like. Write the logs out to disk, and keep the user data in-memory (the credit totals will only be on the order of megabytes for your expected user count).
Anon.  2010-07-07 22:48:41
So if I understand correctly. You're saying that for each user I would be storing a record for all the credits that are expiring on a given day. (We consider 30 days thus the 30 records per user right?) So in my scenario up top I would have the following records:8/1 = 58/2 = 58/3 = 5Now when they purchase the activity for 3 credits I would subtract from the oldest record the amount of the activity, right?If that's the case what happens if the activity costs more than the credits for that day? I would need to loop through each expiration record until it reaches the total I need, right?
spinon  2010-07-07 23:01:09
@spinon: Yes, you'd loop through them from expiring-soonest to expiring-latest until you'd taken off enough credits to cover the cost.
Anon.  2010-07-07 23:03:59
+1  A: 

Use a debit record to record normal expenditures. When the monthly batch job runs, it can calculate the total debits which are less than or equal to the expiring credits. If there are credits to expire, simply insert an appropriate debit record (appropriate == to cancel the excess, in your application). In this way, any 'running total' code which examines only credits and debits will reach the same balance that your batch code intended.

Heath Hunnicutt  2010-07-07 22:29:15
@Heath I agree and I did mention that a little bit. But that still doesn't solve my problem, at least I can't see how right now, as to how not to consider the 3 credits that been spent in the batch the following day. Though I think there is something with that.Also we are writing the debit record to the table and we are updating the aggregate column with this information as well.
spinon  2010-07-07 22:35:55
+2  A: 

For every user of the system keep an array, that stores information about the amount of credits available to the user for the next 30 consecutive days

For example the data for some user might look like this

8  | 
7  | | 
6  | | | | 
5  | | | | | | | | | | |
4  | | | | | | | | | | | | | | | | |
3  | | | | | | | | | | | | | | | | | | | | | | | | 
2  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
  -------------------------------------------------------------
  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
   ^ ^                           ^          
   |  \_                         |
  today tomorrow             in 15 days

Every time the user earns some credits, You increase amounts for all days by the number of credits earned. For example if the user earns 2 credits the table changes as follows. It's like rising the whole graph up.

10 | 
9  | | 
8  | | | | 
7  | | | | | | | | | | |
6  | | | | | | | | | | | | | | | | |
5  | | | | | | | | | | | | | | | | | | | | | | | | 
4  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
3  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
2  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
  -------------------------------------------------------------
  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
   ^ ^                           ^          
   |  \_                         |
  today tomorrow             in 15 days

If The user has x credits today and spends y credits, You decrease the amount of credits available to him to x - y, for every day he has an amount greater than x - y. For days he has no more than x - y, the amount stays the same. It's like cutting the top of the graph off. For example if the user spends 3 credits the graph changes to

7  | | | | | | | | | | |
6  | | | | | | | | | | | | | | | | |
5  | | | | | | | | | | | | | | | | | | | | | | | | 
4  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
3  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
2  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
  -------------------------------------------------------------
  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
   ^ ^                           ^          
   |  \_                         |
  today tomorrow             in 15 days

Every day You shift the graph to the left to model expiring credits. The user will have the following amounts tomorrow

7  | | | | | | | | | |
6  | | | | | | | | | | | | | | | |
5  | | | | | | | | | | | | | | | | | | | | | | | 
4  | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
3  | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
2  | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
1  | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
  -------------------------------------------------------------
  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
   ^ ^                           ^          
   |  \_                         |
  today tomorrow             in 15 days
Maciej Hehl  2010-07-07 23:09:28
I would give you +1 just for the amount of effort that it looks like you put into this. Let me look it over for a few minutes to make sense of what you said. But quickly in just reading it you mentioned having a table for every user. Was that a typo or is that what you meant? Because we have nearly 100k users and a table for each one would be a little out of control. So just want to make sense of that piece right away.
spinon  2010-07-07 23:21:41
@spinon Ok, thanks for the remark. table is a bad word. An artefact of my poor English. I didn't mean a database table but just some structure that holds amounts and enables to associate them with days. It could be a simple array outside the database. I'll try to rephrase it in an edit. In case of a database, just use 30 columns for 30 days and store the data for one user in one row.
Maciej Hehl  2010-07-07 23:35:08
Ok I understand that. Let me continue my tests against it.
spinon  2010-07-07 23:39:15
@spinon Sorry, I made a mistake in the description of spending credits. I meant "greater" instead of "no greater". It's fixed.
Maciej Hehl  2010-07-07 23:46:07
+1  A: 

Assuming you run this batch on a daily basis, you can have a table that keeps track of all the credits they earned, and the credits they used (negative credits).

At the beginning of the next month, your job is simply to find out which of the credits earned on the first day were not spent during the month.

The number of credits earned on the first day - the credits they spent all of last month. If the number is positive, they have some credits that need to expired. So simple add a record in the table with a negative credit. This will zero-out the unused credits.

The next day, repeat the process by seeing how many credits they earned on the second day minus the sum of all the credits they earned in the last month, taking into account the record with the negative credits you created the previous day.

Andy  2010-07-08 15:11:22
I feel like this is the approach I have been trying to work with and it just doesn't seem to be working. Can you work out an example to demonstrate this?
spinon  2010-07-08 15:35:16

related questions

How do I find the Excel column name that corresponds to a given integer?
Calculating a cutting list with the least amount of off cut waste.
Red-Black Trees
How to maintain a recursive invariant in a MySQL database?
RFC calculation in Java need help with algorithm
Best word wrap algorithm?
How do you separate game logic from display?
Most effective way for float and double comparison
Choosing a multiplier for a (string) hash function
Optimizing a search algorithm in C
Find the best combination from a given set of multiple sets
What "already invented" algorithm did you invent?
Designing a Calendar system like Google Calendar
How to overload std::swap()
Looking for algorithm that reverses the sprintf() function output
Merge Sort a Linked List
Puzzle: Find largest rectangle (maximal rectangle problem)
graph serialization
Peak detection of measured signal
Big O, how do you calculate/approximate it?
What problems can be solved, or tackled more easily, using graphs and trees?
Followup: "Sorting" colors by distinctiveness
Efficiently get sorted sums of a sorted list
Function for creating color wheels
Fastest way to get value of pi